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

Revision as of 06:17, 12 February 2015

Revision as of 15:21, 7 March 2016

Line 1:

{{C++ Standard libraryLibrary}}

In the programming language [[C++ programming language]], '''unordered associative containers''' are a group of class templates in the [[C++ Standard Library]] that implement variations of [[hash table]]s variaints. 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++ standardStandard library]]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]] (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) |accessdate=26 January 2011}}</ref> Due to their usefulness, they were later included in several other implementations of the [[C++ standardStandard library]]Library (e.g., the [[GNU Compiler Collection|GCC's]]'s (GCC) [[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> and the [[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=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 |accessdate=26 January 2011}}</ref>

==Overview of functions==

Line 19:

!

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

==Custom hash functions==

In order toTo 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

<source lang="cpp">

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

Line 231:

==References==

{{reflistReflist}}

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