Unordered associative containers (C++): Difference between revisions

Revision as of 12:50, 6 December 2011

Latest revision as of 18:49, 13 December 2023

(32 intermediate revisions by 25 users not shown)

Line 1:

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

{{DISPLAYTITLE:unordered_map (C++)}}

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

{{C++ Standard library}}

{{C++ Standard Library}}

'''<code>unordered_map</code>''' is a class template representing a [[hash table]] in the [[C++ Technical Report 1]] (TR1)<ref>{{Citation |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}}</ref> and the [[C++11]] standard<ref name="n3126">{{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=2010-08-21 |id=n3126}}</ref>. It is similar to the <code>[[hash map (C++ class)|hash_map]]</code> class template of the original [[Standard Template Library|STL]]<ref>{{cite web |url= http://www.sgi.com/tech/stl/hash_map.html |title=hash_map<Key, Data, HashFcn, EqualKey, Alloc> |publisher=[[Silicon Graphics|SGI]] |accessdate=26 January 2011}}</ref> which was also included in several implementations of the C++ Standard Library (e.g. in the [[GNU Compiler Collection|GCC's]] [[libstdc++]]<ref>{{cite web |url=http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/class____gnu__cxx_1_1hash__map.html |title=libstdc++: hash_map Class Template Reference |accessdate=26 January 2011}}</ref> or with [[Visual C++|MSVC]]).

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 [[Template (programming)|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: <code>unordered_set</code>, <code>unordered_map</code>, <code>unordered_multiset</code>, <code>unordered_multimap</code>. Each of these containers differ only on constraints placed on their elements.

It is similar to the <code>[[map (C++ container)|map]]</code> class in the [[C++ Standard Library|C++ standard library]] but has different constraints. As its name implies, unlike the <code>map</code> class, the elements of an <code>unordered_map</code> are not [[well ordering|ordered]]. This is due to the use of hashing to store objects. <code>unordered_map</code> can still be [[iterator|iterated]] through like a regular map.

The unordered associative containers are similar to the [[associative containers (C++)|associative containers]] in the C++ Standard Library but have different constraints. As their name implies, the elements in the unordered associative containers are not [[well ordering|ordered]]. This is due to the use of hashing to store objects. The containers can still be [[iterator|iterated]] through like a regular associative container.

In the TR1, <code>unordered_map</code> is available from the <code><tr1/unordered_map></code> [[header file]] as <code>std::tr1::unordered_map</code>. In C++11, it is available from the <code><unordered_map></code> header file as <code>std::unordered_map</code>. An implementation is also available in the [[Boost C++ Libraries]] as <code><boost/unordered_map.hpp></code><ref>{{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 |accessdate=26 January 2011}}</ref>.

==History==

It is closely related to <code>[[unordered_multimap]]</code> (available in the same header file), which is an implementation of [[multimap]] using hashing. It is also similar to <code>[[unordered_set]]</code> and <code>[[unordered_multiset]]</code>, implementations of the [[set (computer science)|set]] and [[multiset]] containers respectively and available in the <code><tr1/unordered_set></code> or <code><unordered_set></code> headers.

The first widely used implementation of hash tables in the C++ language was <code>hash_map</code>, <code>hash_set</code>, <code>hash_multimap</code>, <code>hash_multiset</code> class templates of the [[Silicon Graphics]] (SGI) [[Standard Template Library]] (STL).<ref>{{cite web |url= http://www.sgi.com/tech/stl/hash_map.html |title=hash_map<Key, Data, HashFcn, EqualKey, Alloc> |publisher=[[Silicon Graphics]] (SGI) |access-date=26 January 2011}}</ref> 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++]]<ref>{{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}}</ref> and the [[Visual C++]] (MSVC) standard library).

==Design==

{{expand section|date=October 2011}}

The <code>hash_*</code> class templates were proposed into [[C++ Technical Report 1]] (C++ TR1) and were accepted under names <code>unordered_*</code>.<ref>{{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}}</ref> Later, they were incorporated into the [[C++11]] revision of the C++ standard.<ref name="n3126">{{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}}</ref> An implementation is also available in the [[Boost C++ Libraries]] as <code><boost/unordered_map.hpp></code>.<ref>{{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}}</ref>

===Overview of functions===

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map unordered_map]</code> (constructor) - Constructs the unordered map from variety of sources.

==Overview of functions==

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/~unordered_map ~unordered_map]</code> (destructor) - Destructs the unordered map and the contained elements

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/operator= operator=]</code> - Assigns values to the unordered map

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

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/get_allocator get_allocator]</code> - Returns the allocator used to allocate memory for the elements

*Iterators

{| class="wikitable" style="font-size:0.85em"

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/begin begin]</code> - Returns an iterator to the beginning of the unordered map

|-

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/end end]</code> - Returns an iterator to the end of the unordered map

!

* Capacity

! <code>unordered_set</code><br />([[C++11]])

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/empty empty]</code> - Checks whether the unordered map is empty

! <code>unordered_map</code><br />(C++11)

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/size size]</code> - Returns the number of elements in the unordered map.

! <code>unordered_multiset</code><br />(C++11)

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/max_size max_size]</code> - Returns the maximum possible number of elements in the unordered map.

! <code>unordered_multimap</code><br />(C++11)

*Modifiers

! Description

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/clear clear]</code> - Clears the contents

|-

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/insert insert]</code> - Inserts elements

! rowspan=4 |

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/emplace emplace]</code> - Constructs elements in-place

**<code>unordered_map::| [http://en.cppreference.com/w/cpp/container/unordered_mapunordered_set/emplaceunordered_set emplace_hint(constructor)]</code> - Constructs elements in-place using a hint

**<code>unordered_map::| [http://en.cppreference.com/w/cpp/container/unordered_map/eraseunordered_map erase(constructor)]</code> - Erases elements

**<code>unordered_map::| [http://en.cppreference.com/w/cpp/container/unordered_mapunordered_multiset/swapunordered_multiset swap(constructor)]</code> - Swaps the contents with another unordered map

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

*Lookup

| Constructs the container from variety of sources

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/count count]</code> - Returns the number of elements matching specific key

|-

**<code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/find find]</code> - Finds an element with specific key

**<code>unordered_map::| [http://en.cppreference.com/w/cpp/container/unordered_mapunordered_set/equal_range~unordered_set equal_range(destructor)]</code> - Returns a range of elements matching specific key

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

*Bucket interface

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

** ...

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

*Hash policy

| Destructs the set and the contained elements

** ...

|-

*Observers

**| <code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_mapunordered_set/hash_functionoperator= hash_functionoperator=]</code> - Returns the function used to create hash of a key

**| <code>unordered_map::[http://en.cppreference.com/w/cpp/container/unordered_map/key_eqoperator= key_eqoperator=]</code> - Returns key comparison function

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

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

| Assigns values to the container

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/get_allocator get_allocator]</code>

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

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

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

| Returns the allocator used to allocate memory for the elements

|-

! rowspan=2 | Element access

| {{n/a}}

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

| {{n/a}}

| {{n/a}}

| Accesses specified element with bounds checking.

|-

| {{n/a}}

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

| {{n/a}}

| {{n/a}}

| Accesses specified element without bounds checking.

|-

! rowspan=2 | Iterators

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

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

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

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

| Returns an iterator to the beginning of the container

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/end end]</code>

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

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

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

| Returns an iterator to the end of the container

|-

! rowspan=3 | Capacity

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

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

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

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

| Checks whether the container is empty

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/size size]</code>

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

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

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

| Returns number of elements in the container.

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/max_size max_size]</code>

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

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

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

| Returns the maximum possible number of elements in the container

|-

! rowspan=6 | Modifiers

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

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

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

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

| Clears the contents.

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/insert insert]</code>

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

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

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

| Inserts elements.

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/emplace emplace]</code>

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

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

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

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

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/emplace_hint emplace_hint]</code>

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

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

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

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

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/erase erase]</code>

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

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

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

| Erases elements.

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/swap swap]</code>

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

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

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

| Swaps the contents with another container.

|-

! rowspan=3 | Lookup

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

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

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

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

| Returns the number of elements matching specific key.

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/find find]</code>

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

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

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

| Finds an element with specific key.

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/equal_range equal_range]</code>

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

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

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

| Returns a range of elements matching specific key.

|-

! rowspan=1 | Bucket interface

| colspan=5 | ...

|-

! rowspan=1 | Hash policy

| colspan=5 | ...

|-

! rowspan=2 | Observers

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

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

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

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

| Returns the function used to create hash of a key

|-

| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/key_eq key_eq]</code>

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

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

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

| Returns key comparison function.

|}

==Usage example==

<sourcesyntaxhighlight lang="cpp">

#include <iostream>

#include <string>

Line 69 ⟶ 199:

return 0;

}

</syntaxhighlight>

</source>

==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

<syntaxhighlight lang="cpp">

#include <unordered_map>

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

struct hash_X{

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

return std::hash<int>()(x.i) ^ std::hash<int>()(x.j) ^ std::hash<int>()(x.k);

}

};

</syntaxhighlight>

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

<syntaxhighlight lang="cpp"> std::unordered_map<X,int,hash_X> my_map;</syntaxhighlight>

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

<syntaxhighlight lang="cpp">

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;

</syntaxhighlight>

==References==

{{reflistReflist}}

[[Category:Articles with example C++ code]]

[[Category:C++ Standard Library]]