Unordered associative containers (C++)

In computing, unordered associative containers refer to a group of class templates in the standard library of the C++ programming language that implement variations of hash table. Being templates, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard: unordered_set, unordered_map, unordered_multiset, unordered_multimap. Each of these containers differ only on constraints placed on their elements.

The unordered associative containers are similar to the associative containers in C++ standard library but has different constraints. As their name implies, the elements in the unordered associative containers are not ordered. This is due to the use of hashing to store objects. The containers can still be iterated through like a regular associative containers.

History

The first widely used implementation of hash tables in the C++ language was hash_map, hash_set, hash_multimap, hash_multiset class templates of the SGI STL.. Due to its usefulness it was later included in several other implementations of the C++ standard library, e.g. in the GCC's libstdc++ or in MSVC standard library.

The hash_* class templates were proposed into C++ TR1 and were accepted under names unordered_*. Later, they were incorporated into the C++11 revision of the C++ standard.. An implementation is also available in the Boost C++ Libraries as <boost/unordered_map.hpp>.

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

Usage 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;
}