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

Revision as of 14:01, 7 December 2011

Latest revision as of 18:49, 13 December 2023

(29 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 |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 |accessdate=26 January 2011}}</ref>.

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

The containers are defined in headers named after the names of the containers, e.g., <code>unordored_setunordered_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"

|-

!

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

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

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

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

! Description

|-

! rowspan=4 |

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

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

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

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

| Constructs the container from variety of sources

|-

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

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

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

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

| Destructs the set and the contained elements

|-

Line 175 ⟶ 173:

==Usage example==

<sourcesyntaxhighlight lang="cpp">

#include <iostream>

#include <string>

Line 201 ⟶ 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]]