Hash Table v/s STL map in C++

Question

Hi,

I am trying to learn C++ maps. Was just wondering about the implementation of STL map. I read it employs Binary search tree.

1. Is there a implementation of hash table in STL?

2. How exactly do STL map stores Key Value pairs?

Answer 1

Typical STL implementations are based on Red-Black trees. C++ TR1 provides std::tr1::unordered_map which uses a hash table implementation. Boost also provides an unordered_map hash table implementation.

Answer 2

1. Some libraries implement stdext::hash_map which has almost the same interface as std::map but uses a hash table instead of a binary tree.

2. The binary tree nodes are arranged in the tree according the key, and each key has a value attached, either in whole in the same node, or as a pointer.

Answer 3

The key-value pairs are stored in an std::pair. Its a templated struct; an element called first stores the key, and an element called second stores the value. Some info.