Unordered map

unordered_map is the proposed C++ TR1 name for a hash table, accessible as std::tr1::unordered_map. unordered_map works very similarly to the existing map class in the C++ STL. It will replace the various incompatible implementations of the hash table (called hash_map by GCC and MSVC).

Until TR1 is officially accepted into the upcoming C++0x standard, unordered_map is available from the header file, and from in MSVC [ [http://msdn.microsoft.com/en-us/library/bb983026.aspx ] ] .

As its name implies, unlike the map class, the elements of an unordered_map are not ordered. This is due to the use of hashing to store objects. unordered_map can still be iterated through like a regular map.

It is closely related to unordered_multimap (available in the same header file), which is an implementation of multimap using hashing. It is also similar to unordered_set and unordered_multiset, implementations of the set and multiset containers respectively and available in the or headers.

unordered_map takes at least two and at most five template parameters, called Key, Data, Hash (or Hasher), Compare and Alloc. unordered_map will associate elements of type Key to elements of type Data; keys are unique in the map (for duplicate keys, unordered_multimap is used). Hash is a hash function which takes elements of type Key and produces an integer. Compare is a function which compares two keys for equality: this is needed for custom data types to resolve hash collisions, which occur when two elements hash to the same value but are actually different. Finally, Alloc is a function which allocates new elements.

References