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.

Bautista

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.

Grandfather

So close. The ext::unordered_map could be anything and is totally unrelated to the std. It may or may not be the same interface, which would be VERY important for anyone interested in keeping client code ready for the new standard instead of adapted to a particular implementation. Also, the tr1 namespace is where unordered_map exists in TR1, not std::namespace. Some of the things in tr1 are different from those that will end up being released in the std. Since the std doesn't exist yet, it's hard to say what the std::unordered_map actually is in relation to that std, if there's any diff. – Skinny

This will be used in a library so What macro(s) would be used to guard against using std::unordered_map being incorrectly included where std::map should be used? – Bautista

What compilers that have released new stuff in the std:: namespace have done is try to anticipate what those new things will look like. In some ways they'll be wrong, in others they'll be right. Chances of unordered_map being changed are not great but other things already have since, for instance, MSVC was released. – Skinny

@user - there's no chance of mixing map and unordered_map. They're totally different, in different headers, etc... You'd have to try really hard to confuse them. – Skinny

Noah Roberts> I didn't make it clear but that's what I meant for ext::unordered_map. I'll modify the explaination. – Grandfather

@Noah: Sorry, I forgot <map> was sorted!! – Bautista

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.

Spasm

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.

Tynishatynwald