Unordered associative containers (C++)

unordered_map is a class template representing a hash table in the C++ Technical Report 1 (TR1) and the upcoming C++0x standard. It is similar to the hash_map class template of the original STL which was also included in several implementations of the C++ Standard Library (e.g. in the GCC's libstdc++ or with MSVC).

It is similar to the map class in the C++ standard library but has different constraints. 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.

In the TR1 unordered_map is available from the <tr1/unordered_map> header file as std::tr1::unordered_map. In the upcoming C++0x standard it is available from the <unordered_map> header file as std::unordered_map. An implementation is also available in the Boost C++ Libraries as <boost/unordered_map.hpp>.

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 <tr1/unordered_set> or <unordered_set> headers.

Usage

  template<class Key,
           class T,
           class Hash = hash<Key>,
           class Pred = std::equal_to<Key>,
           class Alloc = std::allocator<std::pair<const Key, T> > >
  class unordered_map;

unordered_map takes at least two and at most five template parameters, called Key, T, Hash, Pred and Alloc.

unordered_map will associate elements of type

Key

the type of the unique identifier for an element in the map (for duplicate keys, unordered_multimap is used).

T

the type of the element stored in the map

[Hash]

a hash function object. With Hash h; Key k; the call h(k) should return an integer of type size_t. The probability that h(k1) == h(k2) for two different keys k1, k2 should be minimal. See section 20.2.4 in the C++0x proposal. C++0x comes with a hash function object std::hash<Key> which is implemented for standard types.

[Pred]

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.

[Alloc]

a function which allocates new elements.

Example with GNU C++

#include <iostream>
#include <unordered_map>
#include <cstring>
namespace std {
    using namespace tr1;
}


struct eqstr{
    bool operator()(const char* s1, const char* s2) const {
        return strcmp(s1,s2)==0;
    }
};

int main()
{
    std::unordered_map<const char*, int, std::hash<const char*>, eqstr> months;
    months["january"] = 31;
    months["february"] = 28;
    months["march"] = 31;
    months["april"] = 30;
    months["may"] = 31;
    months["june"] = 30;
    months["july"] = 31;
    months["august"] = 31;
    months["september"] = 30;
    months["october"] = 31;
    months["november"] = 30;
    months["december"] = 31;
    std::cout << "september -> " << months["september"] << std::endl;
    std::cout << "april     -> " << months["april"] << std::endl;
    std::cout << "june      -> " << months["june"] << std::endl;
    std::cout << "november  -> " << months["november"] << std::endl; 
    return 0;
}

External links

• C++ reference for std::unordered_map