Unordered associative containers (C++)

unordered_map is a class template representing a hash table in the C++ Technical Report 1 (TR1) and the C++11 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 C++11, 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.

Design

Overview of functions

• • unordered_map::unordered_map (constructor) - Constructs the unordered map from variety of sources.
  • unordered_map::~unordered_map (destructor) - Destructs the unordered map and the contained elements
  • unordered_map::operator= - Assigns values to the unordered map
  • unordered_map::get_allocator - Returns the allocator used to allocate memory for the elements
• Iterators
  • unordered_map::begin - Returns an iterator to the beginning of the unordered map
  • unordered_map::end - Returns an iterator to the end of the unordered map
• Capacity
  • unordered_map::empty - Checks whether the unordered map is empty
  • unordered_map::size - Returns the number of elements in the unordered map.
  • unordered_map::max_size - Returns the maximum possible number of elements in the unordered map.
• Modifiers
  • unordered_map::clear - Clears the contents
  • unordered_map::insert - Inserts elements
  • unordered_map::emplace - Constructs elements in-place
  • unordered_map::emplace_hint - Constructs elements in-place using a hint
  • unordered_map::erase - Erases elements
  • unordered_map::swap - Swaps the contents with another unordered map
• Lookup
  • unordered_map::count - Returns the number of elements matching specific key
  • unordered_map::find - Finds an element with specific key
  • unordered_map::equal_range - Returns a range of elements matching specific key
• Bucket interface
  • ...
• Hash policy
  • ...
• Observers
  • unordered_map::hash_function - Returns the function used to create hash of a key
  • unordered_map::key_eq - Returns key comparison function

Description

  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

#include <iostream>
#include <string>
#include <unordered_map>
 
int main()
{
    std::unordered_map<std::string, int> 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 << "december  -> " << months["december"] << std::endl;
    std::cout << "february  -> " << months["february"] << std::endl;
    return 0;
}

External links

• C++ reference for std::unordered_map