Content deleted Content added
→Example: -> Usage |
Tom.Reding (talk | contribs) m →top: Confirm {{Use dmy dates}} from 2012 |
||
| (37 intermediate revisions by 27 users not shown) | |||
Line 1:
{{Short description|Group of class templates in the C++ Standard Library}}
{{Use dmy dates|date=December 2023}}
{{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) |access-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 |access-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 |access-date=26 January 2011}}</ref>
==Overview of functions==
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"
|-
!
! <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/unordered_set (constructor)]
| [http://en.cppreference.com/w/cpp/container/unordered_map/unordered_map (constructor)]
| [http://en.cppreference.com/w/cpp/container/unordered_multiset/unordered_multiset (constructor)]
| [http://en.cppreference.com/w/cpp/container/unordered_multimap/unordered_multimap (constructor)]
| Constructs the container from variety of sources
|-
| [http://en.cppreference.com/w/cpp/container/unordered_set/~unordered_set (destructor)]
| [http://en.cppreference.com/w/cpp/container/unordered_map/~unordered_map (destructor)]
| [http://en.cppreference.com/w/cpp/container/unordered_multiset/~unordered_multiset (destructor)]
| [http://en.cppreference.com/w/cpp/container/unordered_multimap/~unordered_multimap (destructor)]
| Destructs the set and the contained elements
|-
| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/operator= operator=]</code>
| <code>[http://en.cppreference.com/w/cpp/container/unordered_map/operator= operator=]</code>
| <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>
| Assigns values to the container
|-
| <code>[http://en.cppreference.com/w/cpp/container/unordered_set/get_allocator get_allocator]</code>
| <code>[http://en.cppreference.com/w/cpp/container/unordered_map/get_allocator get_allocator]</code>
| <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==
<syntaxhighlight lang="cpp">
#include <iostream>
#include <string>
Line 87 ⟶ 199:
return 0;
}
</syntaxhighlight>
==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==
{{
[[Category:Articles with example C++ code]]
[[Category:C++ Standard Library]]
| |||