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

Revision as of 15:06, 25 July 2016

Latest revision as of 18:49, 13 December 2023

(5 intermediate revisions by 5 users not shown)

Line 1:

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

{{useUse dmy dates|date=JanuaryDecember 20122023}}

{{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 [[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 [[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.

==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) [[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) |accessdateaccess-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 |accessdateaccess-date=26 January 2011}}</ref> and the [[Visual C++]] (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=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==

Line 18 ⟶ 20:

|-

!

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

|-

Line 171 ⟶ 173:

==Usage example==

<sourcesyntaxhighlight lang="cpp">

#include <iostream>

#include <string>

Line 197 ⟶ 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

<sourcesyntaxhighlight lang="cpp">

#include <unordered_map>

Line 211 ⟶ 213:

}

};

</syntaxhighlight>

</source>

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

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

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

<sourcesyntaxhighlight lang="cpp">

namespace std {

template <>

Line 230 ⟶ 232:

//...

std::unordered_map<X,int> my_map;

</syntaxhighlight>

</source>

==References==

{{Reflist}}

{{use dmy dates|date=January 2012}}

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