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.

Answer 2

The headers in <tr1/*> are things which were specified in TR1 'draft'. I believe a lot of these are likely to progress into C++0x (although this isn't guaranteed and there is scope for incompatible changes too). <ext/*> is non-standard (i.e. vendor specific) extensions as I understand it. Boost also provides an unordered_map which may be handy if you're trying to target compilers which provide none of the headers you mentioned.

Answer 3

If you're talking about the ext/unordered_map then this is the old SGI/HP STL component. It is very similar to the other unordered_maps. I would use std::unordered_map as a standard component - that's the future.

I understand that the old SGI/HP hash containers barely missed being included in the C++98 standard for some reason.