UnorderedAssociativeContainer
C++概念：UnorderedAssociativeContainer
无序关联容器是Container斯提供基于键的对象快速查找。最坏的情况复杂性是线性的，但对于大多数操作来说，平均速度要快得多。
无序关联容器被Key；Hash，一Hash函数对象，充当散列函数。Key；和Pred，一BinaryPredicate评价等价性KeyS.std::unordered_map和std::unordered_multimap也有映射类型。T与Key...
如果两个KeyS是平等的Pred，，，Hash必须为两个键返回相同的值。
std::unordered_map和std::unordered_set最多可以包含一个具有给定键的元素，std::unordered_multiset和std::unordered_multimap相反，可以有多个具有相同键%28的元素，而在迭代%29时，这些元素必须总是相邻的。
为std::unordered_set和std::unordered_multiset值类型与键类型相同，两者都是iterator和const_iterator是常量迭代器。为std::unordered_map和std::unordered_multimap值类型是std::pair<const Key, T>...
无序关联容器中的元素被组织成桶，具有相同哈希的键将在同一个桶中结束。当容器的大小增加时，桶的数量会增加，以将每个桶中的元素的平均数量保持在一定的值以下。
重哈希会使迭代器无效，并可能导致元素在不同的桶中重新排列，但它不会使对元素的引用无效。
无序关联容器满足AllocatorAwareContainer.为std::unordered_map和std::unordered_multimap对...的要求value_type在AllocatorAwareContainer适用于key_type和mapped_type%28未调至value_type29%。
所需
传说
*。
X容器型
X型对象
B型对象
阿[医]当X支持唯一键时，X中的Uniq对象
阿[医]当X支持多个等价键时，X中的EQ对象
i，j表示有效范围的输入器
P，Q2有效Const[医]迭代器到
q，q1可解除引用的常数[医]表示有效范围的迭代器
STD的IL对象：：初始化器[医]列表<X：：值[医]类型>
类型为X：：value的T对象[医]类型
类型为X：：Key的K对象[医]类型
X型HF Const对象：：Hasher
类型为X：：Key的EQConst对象[医]平等
X型N值：：大小[医]类型
浮子型Z值
| expression | return type | pre/requirements | post/effects | complexity |
|---|---|---|---|---|
| X::key_type | Key | | | compile time |
| X::mapped_type | T | std::unordered_map and std::unordered_multimap only | | compile time |
| X::value_type | Key | std::unordered_set and std::unordered_multiset only. Erasable in X | | compile time |
| X::value_type | std::pair<const Key, T> | std::unordered_map and std::unordered_multimap only. Erasable in X | | compile time |
| X::hasher | Hash | Hash | | compile time |
| X::key_equal | Pred | BinaryPredicate taking two arguments of type Key and expressing an equivalence relation. | | compile time |
| X::local_iterator | An Iterator whose category and types are the same as X::iterator | | Can be used to iterate through a single bucket | compile time |
| X::const_local_iterator | An Iterator whose category and types are the same as X::const_iterator | | Can be used to iterate through a single bucket | compile time |
| X(n,hf,eq) | X | hasher and key_equal CopyConstructible | Constructs an empty container with at least n buckets, using the given hash function and equality predicate | linear in n |
| X(n,hf) | X | hasher CopyConstructible, key_equal DefaultConstructible | Constructs an empty container with at least n buckets, using the given hash function and key_equal() as equality predicate | linear in n |
| X(n,hf) | X | hasher and key_equal DefaultConstructible | Constructs an empty container with at least n buckets, using hasher() as hash function and key_equal() as equality predicate | linear in n |
| X() | X | hasher and key_equal DefaultConstructible | Constructs an empty container with an unspecified number of buckets, using hasher() as hash function and key_equal() as equality predicate | constant |
| X(i,j,n,hf,eq) | X | hasher and key_equal CopyConstructible, value_type EmplaceConstructible into X from *i | Constructs an empty container with at least n buckets, using the given hash function and equality predicate, and inserts elements from [i,j) into it. | average linear, worst quadratin (on the distance between i and j) |
| X(i,j,n,hf) | X | key_equal DefaultConstructible | As above, with eq=key_equal() | see above |
| X(i,j,n) | X | hasher DefaultConstructible | As above, with hf=hasher() | see above |
| X(i,j) | X | | As above, with an unspecified number of buckets | see above |
| X(il) | X | | X(il.begin(),il.end() | see above |
| X(il,n) | X | | X(il.begin(),il.end(),n | see above |
| X(il,n,hf) | X | | X(il.begin(),il.end(),n,hf | see above |
| X(il,n,hf,eq) | X | | X(il.begin(),il.end(),n,hf,eq | see above |
| X(b) | X | | Copy constructors, also copies the hash function, predicate and maximum load factor | average linear, worst quadratic (in b.size()) |
| a = b | X& | | Copy assignment, also copies the hash function, predicate and maximum load factor | average linear, worst quadratic (in b.size()) |
| a = il | X& | value_type CopyAssignable and CopyInsertable into X | a = X(il) | see above |
标准库中的UnorderedAssociativeContainer
| unordered_set (since C++11) | collection of unique keys, hashed by keys (class template) |
|---|---|
| unordered_multiset (since C++11) | collection of keys, hashed by keys (class template) |
| unordered_map (since C++11) | collection of key-value pairs, hashed by keys, keys are unique (class template) |
| unordered_multimap (since C++11) | collection of key-value pairs, hashed by keys (class template) |
© cppreference.com
在CreativeCommonsAttribution下授权-ShareAlike未移植许可v3.0。
http：//en.cppreference.com/w/cpp/Concept/UnorderedAssociativeContainer
