Unordered associative containers (C++)

In the programming language C++, unordered associative containers are a group of class templates in the C++ Standard Library that implement hash table variants. 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 the C++ Standard Library but have 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 container.

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 Silicon Graphics (SGI) Standard Template Library (STL).^[1] Due to their usefulness, they were later included in several other implementations of the C++ Standard Library (e.g., the GNU Compiler Collection's (GCC) libstdc++^[2] and the Visual C++ (MSVC) standard library).

The hash_* class templates were proposed into C++ Technical Report 1 (C++ TR1) and were accepted under names unordered_*.^[3] Later, they were incorporated into the C++11 revision of the C++ standard.^[4] An implementation is also available in the Boost C++ Libraries as <boost/unordered_map.hpp>.^[5]

Overview of functions

The containers are defined in headers named after the names of the containers, e.g., unordered_set is defined in header <unordered_set>. All containers satisfy the requirements of the Container concept, which means they have begin(), end(), size(), max_size(), empty(), and swap() methods.

	unordered_set (C++11)	unordered_map (C++11)	unordered_multiset (C++11)	unordered_multimap (C++11)	Description
	(constructor)	(constructor)	(constructor)	(constructor)	Constructs the container from variety of sources
	(destructor)	(destructor)	(destructor)	(destructor)	Destructs the set and the contained elements
	operator=	operator=	operator=	operator=	Assigns values to the container
	get_allocator	get_allocator	get_allocator	get_allocator	Returns the allocator used to allocate memory for the elements
Element access	N/A	at	N/A	N/A	Accesses specified element with bounds checking.
	N/A	operator[]	N/A	N/A	Accesses specified element without bounds checking.
Iterators	begin	begin	begin	begin	Returns an iterator to the beginning of the container
	end	end	end	end	Returns an iterator to the end of the container
Capacity	empty	empty	empty	empty	Checks whether the container is empty
	size	size	size	size	Returns number of elements in the container.
	max_size	max_size	max_size	max_size	Returns the maximum possible number of elements in the container
Modifiers	clear	clear	clear	clear	Clears the contents.
	insert	insert	insert	insert	Inserts elements.
	emplace	emplace	emplace	emplace	Constructs elements in-place (C++11)
	emplace_hint	emplace_hint	emplace_hint	emplace_hint	Constructs elements in-place using a hint (C++11)
	erase	erase	erase	erase	Erases elements.
	swap	swap	swap	swap	Swaps the contents with another container.
Lookup	count	count	count	count	Returns the number of elements matching specific key.
	find	find	find	find	Finds an element with specific key.
	equal_range	equal_range	equal_range	equal_range	Returns a range of elements matching specific key.
Bucket interface	...
Hash policy	...
Observers	hash_function	hash_function	hash_function	hash_function	Returns the function used to create hash of a key
	key_eq	key_eq	key_eq	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;
}

Custom hash functions

To use custom objects in std::unordered_map, a custom hash function must be defined. This function takes a const reference to the custom type and returns a size_t

struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
  }
};

The user defined function can be used as is in std::unordered_map, by passing it as a template parameter

 std::unordered_map<X,int,hash_X> my_map;

Or can be set as the default hash function by specializing the std::hash function

namespace std {
    template <>
        class hash<X>{
        public :
        size_t operator()(const X &x ) const{
            return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
        }
    };
}

//...
 std::unordered_map<X,int> my_map;

References

1. "hash_map<Key, Data, HashFcn, EqualKey, Alloc>". Silicon Graphics (SGI). Retrieved 26 January 2011.
2. "libstdc++: hash_map Class Template Reference". Retrieved 26 January 2011.
3. WG21 (9 April 2003). "A Proposal to Add Hash Tables to the Standard Library (revision 4)". n1456.
4. WG21 (21 August 2010), Working Draft, Standard for Programming Language C++ (PDF), n3126
5. "Class template unordered_map". Boost. Retrieved 26 January 2011.