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

Revision as of 12:50, 6 December 2011

Revision as of 13:36, 6 December 2011

Line 1:

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

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

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

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.

'''<code>unordered_map</code>'''The isfirst awidely classused templateimplementation representingof a [[hash table]]tables in the [[C++ Technicallanguage Reportwas 1]] (TR1)<refcode>{{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}}hash_map</refcode>, and the [[C++11]] standard<ref name="n3126"code>{{citation|url=http:hash_set<//www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf |title=Working Draftcode>, Standard for Programming Language C++ |author=WG21 |date=2010-08-21 |id=n3126}}<code>hash_multimap</refcode>. It is similar to the, <code>[[hash map (C++ class)|hash_map]]hash_multiset</code> class templatetemplates of the original[[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]] |accessdate=26 January 2011}}</ref>. Due to its usefulness whichit was alsolater included in several other implementations of the [[C++ Standardstandard Librarylibrary]], (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 within [[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=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}}

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