C++ <map> vs <unordered_map> vs <tr1/unordered_map> vs <ext/unordered_map>

Question

I'm currently looking for a better alternative to std::map and have come across classes mentioned in the post title. Could someone clarify the differences between them, not in terms of performance/API, but in terms of where they beleong in relation to the current and forthcomnig standard.

Answer 1

• std::map : the current C++ standard associative container (key/value), that works as a tree behind;
• std::unordered_map : the next standard(C++0x -- or in the Technical Report 1) hash-map container, that works as an... hash map.
• std::tr1::unordered_map : the same as the previous one but in the tr1 namespace, often found in compilers wishing to provide TR1 extensions but in another namespace than std.
• ext::unordered_map : still the same idea but compiler-specific implementation, so it's not guaranteed to be exactly the same as std::unordered_map, on interface and implementation.

If you can, use std::unordered_map as it's the final name of the hash map implementation (if you need a hash map). The others names are there in case your compiler provide them but in a separate namespace (as C++0x is not yet available officially).

There is boost::unordered_map too by the way, but it's almost all the same idea and interface.