Hash Table v/s STL map in C++

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 开发者_如何学Cimplementation of hash table in STL?

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

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.

C++11 now has std::unordered_map

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.

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.