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

Revision as of 13:36, 6 December 2011

Latest revision as of 18:49, 13 December 2023

(31 intermediate revisions by 25 users not shown)

Line 1:

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

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

{{C++ Standard Library}}

In computingthe programming language [[C++]], '''unordered associative containers''' refer toare a group of class templates in the [[C++ Standard Library|standard library]] of the [[C++|C++ programming language]] that implement variations of [[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.

The unordered associative containers are similar to the [[Associativeassociative containers (C++)|associative containers]] in [[the C++ standardStandard library]]Library but hashave 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 containerscontainer.

==History==

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]] (SGI) [[Standard Template Library|STL]] (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]] (SGI) |accessdateaccess-date=26 January 2011}}</ref>. Due to itstheir usefulness, itthey waswere later included in several other implementations of the [[C++ standardStandard library]],Library (e.g. in, the [[GNU Compiler Collection|GCC]]'s]] (GCC) [[libstdc++]]<ref>{{cite web |url=httphttps://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.1/class____gnu__cxx_1_1hash__map.html |title=libstdc++: hash_map Class Template Reference |accessdateaccess-date=26 January 2011}}</ref> orand inthe [[Visual C++|MSVC]] (MSVC) standard library).

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=2010-08-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 |accessdateaccess-date=26 January 2011}}</ref>.

==Overview of functions==

==Design==

{{expand section|date=October 2011}}

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.

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

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

!

**<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_set</code><br />([[C++11]])

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

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

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

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

*Iterators

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

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

! Description

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

! rowspan=4 |

**<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::| [http://en.cppreference.com/w/cpp/container/unordered_mapunordered_set/sizeunordered_set size(constructor)]</code> - Returns the number of elements in the unordered map.

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

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

*Modifiers

**<code>unordered_map::| [http://en.cppreference.com/w/cpp/container/unordered_mapunordered_multimap/clearunordered_multimap clear(constructor)]</code> - Clears the contents

| Constructs the container from variety of sources

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

|-

**<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/emplace~unordered_set emplace_hint(destructor)]</code> - Constructs elements in-place using a hint

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

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

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

*Lookup

| Destructs the set and the contained elements

**<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_rangeoperator= equal_rangeoperator=]</code> - Returns a range of elements matching specific key

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

*Bucket interface

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

*Hash policy

| Assigns values to the container

** ...

|-

*Observers

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

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

| <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 73 ⟶ 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]]