Login
Login

Unordered associative containers (C++)

{{Short description|Group of class templates in the C++ Standard Library}}

{{Use dmy dates|date=December 2023}}

{{C++ Standard Library}}

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).{{cite web |url= http://www.sgi.com/tech/stl/hash_map.html |title=hash_map |publisher=Silicon Graphics (SGI) |access-date=26 January 2011}} 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++{{cite web |url=https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/class____gnu__cxx_1_1hash__map.html |title=libstdc++: hash_map Class Template Reference |access-date=26 January 2011}} 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_*.{{cite web |title=A Proposal to Add Hash Tables to the Standard Library (revision 4) |author=WG21 |date=9 April 2003 |url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html |id=n1456}} Later, they were incorporated into the C++11 revision of the C++ standard.{{citation|url=http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf |title=Working Draft, Standard for Programming Language C++ |author=WG21 |date=21 August 2010 |id=n3126}} An implementation is also available in the Boost C++ Libraries as .{{cite web |publisher=Boost |title=Class template unordered_map |url=http://www.boost.org/doc/libs/1_45_0/doc/html/boost/unordered_map.html |access-date=26 January 2011}}

Overview of functions

The containers are defined in headers named after the names of the containers, e.g., unordered_set is defined in header . All containers satisfy the requirements of the [http://www.sgi.com/tech/stl/Container.html Container] concept, which means they have begin(), end(), size(), max_size(), empty(), and swap() methods.

class="wikitable" style="font-size:0.85em"
! unordered_set
(C++11)

! unordered_map
(C++11)

! unordered_multiset
(C++11)

! unordered_multimap
(C++11)

! Description

rowspan=4 |

| [http://en.cppreference.com/w/cpp/container/unordered_set/unordered_set (constructor)]

| [http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map (constructor)]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/unordered_multiset (constructor)]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/unordered_multimap (constructor)]

| Constructs the container from variety of sources

[http://en.cppreference.com/w/cpp/container/unordered_set/~unordered_set (destructor)]

| [http://en.cppreference.com/w/cpp/container/unordered_map/~unordered_map (destructor)]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/~unordered_multiset (destructor)]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/~unordered_multimap (destructor)]

| Destructs the set and the contained elements

[http://en.cppreference.com/w/cpp/container/unordered_set/operator= operator=]

| [http://en.cppreference.com/w/cpp/container/unordered_map/operator= operator=]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/operator= operator=]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/operator= operator=]

| Assigns values to the container

[http://en.cppreference.com/w/cpp/container/unordered_set/get_allocator get_allocator]

| [http://en.cppreference.com/w/cpp/container/unordered_map/get_allocator get_allocator]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/get_allocator get_allocator]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/get_allocator get_allocator]

| Returns the allocator used to allocate memory for the elements

rowspan=2 | Element access

| {{n/a}}

| [http://en.cppreference.com/w/cpp/container/unordered_map/at at]

| {{n/a}}

| {{n/a}}

| Accesses specified element with bounds checking.

{{n/a}}

| [http://en.cppreference.com/w/cpp/container/unordered_map/operator_at operator[]]

| {{n/a}}

| {{n/a}}

| Accesses specified element without bounds checking.

rowspan=2 | Iterators

| [http://en.cppreference.com/w/cpp/container/unordered_set/begin begin]

| [http://en.cppreference.com/w/cpp/container/unordered_map/begin begin]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/begin begin]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/begin begin]

| Returns an iterator to the beginning of the container

[http://en.cppreference.com/w/cpp/container/unordered_set/end end]

| [http://en.cppreference.com/w/cpp/container/unordered_map/end end]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/end end]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/end end]

| Returns an iterator to the end of the container

rowspan=3 | Capacity

| [http://en.cppreference.com/w/cpp/container/unordered_set/empty empty]

| [http://en.cppreference.com/w/cpp/container/unordered_map/empty empty]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/empty empty]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/empty empty]

| Checks whether the container is empty

[http://en.cppreference.com/w/cpp/container/unordered_set/size size]

| [http://en.cppreference.com/w/cpp/container/unordered_map/size size]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/size size]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/size size]

| Returns number of elements in the container.

[http://en.cppreference.com/w/cpp/container/unordered_set/max_size max_size]

| [http://en.cppreference.com/w/cpp/container/unordered_map/max_size max_size]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/max_size max_size]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/max_size max_size]

| Returns the maximum possible number of elements in the container

rowspan=6 | Modifiers

| [http://en.cppreference.com/w/cpp/container/unordered_set/clear clear]

| [http://en.cppreference.com/w/cpp/container/unordered_map/clear clear]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/clear clear]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/clear clear]

| Clears the contents.

[http://en.cppreference.com/w/cpp/container/unordered_set/insert insert]

| [http://en.cppreference.com/w/cpp/container/unordered_map/insert insert]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/insert insert]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/insert insert]

| Inserts elements.

[http://en.cppreference.com/w/cpp/container/unordered_set/emplace emplace]

| [http://en.cppreference.com/w/cpp/container/unordered_map/emplace emplace]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/emplace emplace]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/emplace emplace]

| Constructs elements in-place (C++11)

[http://en.cppreference.com/w/cpp/container/unordered_set/emplace_hint emplace_hint]

| [http://en.cppreference.com/w/cpp/container/unordered_map/emplace_hint emplace_hint]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/emplace_hint emplace_hint]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/emplace_hint emplace_hint]

| Constructs elements in-place using a hint (C++11)

[http://en.cppreference.com/w/cpp/container/unordered_set/erase erase]

| [http://en.cppreference.com/w/cpp/container/unordered_map/erase erase]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/erase erase]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/erase erase]

| Erases elements.

[http://en.cppreference.com/w/cpp/container/unordered_set/swap swap]

| [http://en.cppreference.com/w/cpp/container/unordered_map/swap swap]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/swap swap]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/swap swap]

| Swaps the contents with another container.

rowspan=3 | Lookup

| [http://en.cppreference.com/w/cpp/container/unordered_set/count count]

| [http://en.cppreference.com/w/cpp/container/unordered_map/count count]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/count count]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/count count]

| Returns the number of elements matching specific key.

[http://en.cppreference.com/w/cpp/container/unordered_set/find find]

| [http://en.cppreference.com/w/cpp/container/unordered_map/find find]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/find find]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/find find]

| Finds an element with specific key.

[http://en.cppreference.com/w/cpp/container/unordered_set/equal_range equal_range]

| [http://en.cppreference.com/w/cpp/container/unordered_map/equal_range equal_range]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/equal_range equal_range]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/equal_range equal_range]

| Returns a range of elements matching specific key.

rowspan=1 | Bucket interface

| colspan=5 | ...

rowspan=1 | Hash policy

| colspan=5 | ...

rowspan=2 | Observers

| [http://en.cppreference.com/w/cpp/container/unordered_set/hash_function hash_function]

| [http://en.cppreference.com/w/cpp/container/unordered_map/hash_function hash_function]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/hash_function hash_function]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/hash_function hash_function]

| Returns the function used to create hash of a key

[http://en.cppreference.com/w/cpp/container/unordered_set/key_eq key_eq]

| [http://en.cppreference.com/w/cpp/container/unordered_map/key_eq key_eq]

| [http://en.cppreference.com/w/cpp/container/unordered_multiset/key_eq key_eq]

| [http://en.cppreference.com/w/cpp/container/unordered_multimap/key_eq key_eq]

| Returns key comparison function.

Usage example

  1. include
  2. include
  3. include

int main()

{

std::unordered_map 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

  1. include

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

struct hash_X{

size_t operator()(const X &x) const{

return std::hash()(x.i) ^ std::hash()(x.j) ^ std::hash()(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 my_map;

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

namespace std {

template <>

class hash{

public :

size_t operator()(const X &x ) const{

return hash()(x.i) ^ hash()(x.j) ^ hash()(x.k);

}

};

}

//...

std::unordered_map my_map;

References

{{Reflist}}

Category:Articles with example C++ code

Category:C++ Standard Library