C++ named requirements: UnorderedAssociativeContainer (since C++11)
无序关联容器是 容器 ，能够基于键值快速查找对象。 最坏情况下的时间复杂度为线性，但对于大多数操作而言平均速度要快得多。
无序关联容器通过以下参数进行配置：
Key
；
Hash
，一个作为
Key
哈希函数的
Hash
函数对象；以及
Pred
，一个用于判断
Key
间等价关系的
BinaryPredicate
。
std::unordered_map
和
std::unordered_multimap
还具有与
Key
关联的映射类型
T
。
如果两个
Key
根据
Pred
判断相等，则
Hash
必须为这两个键返回相同的值。
|
若
|
(since C++20) |
std::unordered_map 和 std::unordered_set 最多只能包含一个具有给定键的元素，而 std::unordered_multiset 和 std::unordered_multimap 则可以包含多个具有相同键的元素（在迭代时这些元素必须始终相邻）。
对于
std::unordered_set
和
std::unordered_multiset
，值类型与键类型相同，且
iterator
和
const_iterator
均为常量迭代器。
对于
std::unordered_map
和
std::unordered_multimap
，值类型为
std::
pair
<
const
Key, T
>
。
无序关联容器中的元素被组织到多个桶中，具有相同哈希值的键会被放入同一个桶。 当容器大小增加时，桶的数量也会增加，以确保每个桶中元素的平均数量维持在特定值以下。
重新哈希会使迭代器失效，并可能导致元素被重新排列到不同的桶中，但不会使对元素的引用失效。
无序关联容器满足
分配器感知容器
的要求。
对于
std::unordered_map
和
std::unordered_multimap
，
分配器感知容器
中关于
value_type
的要求适用于
key_type
和
mapped_type
（而非
value_type
）。
目录 |
要求
图例说明 |
|
X
|
无序关联容器类 |
| a |
类型为
X
的值
|
| a2 |
具有与类型
X
节点兼容
的类型的值
|
| b |
类型为
X
或
const X
的值
|
| a_uniq |
当
X
支持唯一键时的类型
X
值
|
| a_eq |
当
X
支持等价键时的类型
X
值
|
| a_tran |
当限定标识符
X::key_equal::is_transparent
和
X::hasher::is_transparent
均有效且表示
类型
时，类型为
X
或
const
X
的值
|
| i , j |
指向
value_type
的输入迭代器
|
[
i
,
j
)
|
有效范围 |
| rg (C++23 起) |
类型
R
的值，需满足
container-compatible-range
<value_type>
概念
|
| p , q2 | 指向 a 的有效常量迭代器 |
| q , q1 | 指向 a 的有效可解引用常量迭代器 |
| r | 指向 a 的有效可解引用迭代器 |
[
q1
,
q2
)
|
a 中的有效范围 |
| il | 类型为 std:: initializer_list < value_type > 的值 |
| t |
类型为
X::value_type
的值
|
| k |
类型为
key_type
的值
|
| hf |
类型为
hasher
或
const
hasher
的值
|
| eq |
类型为
key_equal
或
const
key_equal
的值
|
| ke |
满足以下条件的值：
其中 r1 和 r2 是 a_tran 中元素的键 |
| kx (C++23 起) |
满足以下条件的值：
其中 r1 和 r2 是 a_tran 中元素的键 |
| n |
类型为
size_type
的值
|
| z | 类型为 float 的值 |
| nh (C++17 起) | 类型为 X :: node_type 的右值 |
成员类型
| 名称 | 类型 | 要求 | 备注 |
|---|---|---|---|
X::key_type
|
Key
|
||
X::mapped_type
|
T
|
仅限 std::unordered_map 和 std::unordered_multimap | |
X::value_type
|
Key
|
仅限
std::unordered_set
和
std::unordered_multiset
。在
X
中需满足
Erasable
要求
|
|
| std:: pair < const Key, T > |
仅限
std::unordered_map
和
std::unordered_multimap
。在
X
中需满足
Erasable
要求
|
||
X::hasher
|
Hash
|
需满足 Hash 要求 | |
X::key_equal
|
Pred
|
需满足
CopyConstructible
要求；需为接受两个
Key
类型参数并表达等价关系的
BinaryPredicate
|
|
X::local_iterator
|
LegacyIterator |
类别和类型与
X::iterator
相同
|
可用于遍历单个桶，但不能跨桶遍历 |
X::const_local_iterator
|
LegacyIterator |
类别和类型与
X::const_iterator
相同
|
|
X::node_type
(C++17起)
|
node-handle 类模板的特化 |
公共嵌套类型与
X
中的对应类型相同
|
成员函数与运算符
| Expression | Result | Preconditions | Effects | Returns | Complexity |
|---|---|---|---|---|---|
| X ( n, hf, eq ) | Constructs an empty container with at least n buckets, using hf as the hash function and eq as the key equality predicate | O ( n ) | |||
| X ( n, hf ) |
key_equal
is
DefaultConstructible
|
Constructs an empty container with at least n buckets, using hf as the hash function and key_equal ( ) as the key equality predicate | O ( n ) | ||
| X ( n ) |
hasher
and
key_equal
are
DefaultConstructible
|
Constructs an empty container with at least n buckets, using hasher ( ) as the hash function and key_equal ( ) as the key equality predicate | O ( n ) | ||
|
X a
=
X
(
)
;
X a ; |
hasher
and
key_equal
are
DefaultConstructible
|
Constructs an empty container with an unspecified number of buckets, using hasher ( ) as the hash function and key_equal ( ) as the key equality predicate | Constant | ||
| X ( i, j, n, hf, eq ) |
value_type
is
EmplaceConstructible
into
X
from
*
i
|
Constructs an empty container with at least
n
buckets, using
hf
as the hash function and
eq
as the key equality predicate, and inserts elements from
[
i
,
j
)
into it
|
Average case O(N) ( N is std:: distance ( i, j ) ), worst case O(N 2 ) | ||
| X ( i, j, n, hf ) |
key_equal
is the
DefaultConstructible
.
value_type
is
EmplaceConstructible
into
X
from
*
i
|
Constructs an empty container with at least
n
buckets, using
hf
as the hash function and
key_equal
(
)
as the key equality predicate, and inserts elements from
[
i
,
j
)
into it
|
Average case O(N) ( N is std:: distance ( i, j ) ), worst case O(N 2 ) | ||
| X ( i, j, n ) |
hasher
and
key_equal
are
DefaultConstructible
.
value_type
is
EmplaceConstructible
into
X
from
*
i
|
Constructs an empty container with at least
n
buckets, using
hasher
(
)
as the hash function and
key_equal
(
)
as the key equality predicate, and inserts elements from
[
i
,
j
)
into it
|
Average case O(N) ( N is std:: distance ( i, j ) ), worst case O(N 2 ) | ||
| X ( i, j ) |
hasher
and
key_equal
are
DefaultConstructible
.
value_type
is
EmplaceConstructible
into
X
from
*
i
|
Constructs an empty container with an unspecified number of buckets, using
hasher
(
)
as the hash function and
key_equal
(
)
as the key equality predicate, and inserts elements from
[
i
,
j
)
into it
|
Average case O(N) ( N is std:: distance ( i, j ) ), worst case O(N 2 ) | ||
|
X
(
std::
from_range
,
rg, n, hf, eq ) (since C++23) |
value_type
is
EmplaceConstructible
into
X
from
*
ranges::
begin
(
rg
)
|
Constructs an empty container with at least n buckets, using hf as the hash function and eq as the key equality predicate, and inserts elements from rg into it | Average case O(N) ( N is ranges:: distance ( rg ) ), worst case O(N 2 ) | ||
|
X
(
std::
from_range
,
rg, n, hf ) (since C++23) |
key_equal
is
DefaultConstructible
.
value_type
is
EmplaceConstructible
into
X
from
*
ranges::
begin
(
rg
)
|
Constructs an empty container with at least n buckets, using hf as the hash function and key_equal ( ) as the key equality predicate, and inserts elements from rg into it | Average case O(N) ( N is ranges:: distance ( rg ) ), worst case O(N 2 ) | ||
|
X
(
std::
from_range
,
rg, n ) (since C++23) |
hasher
and
key_equal
are
DefaultConstructible
.
value_type
is
EmplaceConstructible
into
X
from
*
ranges::
begin
(
rg
)
|
Constructs an empty container with at least n buckets, using hasher ( ) as the hash function and key_equal ( ) as the key equality predicate, and inserts elements from rg into it | Average case O(N) ( N is ranges:: distance ( rg ) ), worst case O(N 2 ) | ||
|
X
(
std::
from_range
,
rg ) (since C++23) |
hasher
and
key_equal
are
DefaultConstructible
.
value_type
is
EmplaceConstructible
into
X
from
*
ranges::
begin
(
rg
)
|
Constructs an empty container with an unspecified number of buckets, using hasher ( ) as the hash function and key_equal ( ) as the key equality predicate, and inserts elements from rg into it | Average case O(N) ( N is ranges:: distance ( rg ) ), worst case O(N 2 ) | ||
| X ( il ) | X ( il. begin ( ) , il. end ( ) ) | ||||
| X ( il, n ) | X ( il. begin ( ) , il. end ( ) , n ) | ||||
| X ( il, n, hf ) | X ( il. begin ( ) , il. end ( ) , n, hf ) | ||||
| X ( il, n, hf, eq ) | X ( il. begin ( ) , il. end ( ) , n, hf, eq ) | ||||
| X ( b ) | Container ; Copies the hash function, predicate, and maximum load factor | Average case linear in b. size ( ) , worst case O(N 2 ) | |||
| a = b |
X&
|
Container ; copies the hash function, predicate, and maximum load factor | Average case linear in b. size ( ) , worst case O(N 2 ) | ||
| a = il |
X&
|
value_type
is
CopyInsertable
into
X
and
CopyAssignable
|
Assigns the range
[
il.
begin
(
)
,
il.
end
(
)
)
into
a
. All existing elements of
a
are either assigned to or destroyed
|
Average case linear in il. size ( ) , worst case O(N 2 ) | |
| b. hash_function ( ) |
hasher
|
b 's hash function | Constant | ||
| b. key_eq ( ) |
key_equal
|
b 's key equality predicate | Constant | ||
| a_uniq. emplace ( args ) |
std::
pair
<
iterator, bool > |
value_type
is
EmplaceConstructible
into
X
from
args
|
Inserts a
value_type
object
t
constructed with
std::
forward
<
Args
>
(
args
)
...
if and only if there is no element in the container with key equivalent to the key of
t
|
The bool component of the returned pair is true if and only if the insertion takes place, and the iterator component of the pair points to the element with key equivalent to the key of t | Average case O(1) , worst case O ( a_uniq. size ( ) ) |
| a_eq. emplace ( args ) |
iterator
|
value_type
is
EmplaceConstructible
into
X
from
args
|
Inserts a
value_type
object
t
constructed with
std::
forward
<
Args
>
(
args
)
...
|
An iterator pointing to the newly inserted element | Average case O(1) , worst case O ( a_eq. size ( ) ) |
| a. emplace_hint ( p, args ) |
iterator
|
value_type
is
EmplaceConstructible
into
X
from
args
|
a.
emplace
(
std:: forward < Args > ( args ) ... ) |
An iterator pointing to the element with the key equivalent to the newly inserted element. The
const_iterator
p
is a hint pointing to where the search should start. Implementations are permitted to ignore the hint
|
Average case O(1) , worst case O ( a. size ( ) ) |
| a_uniq. insert ( t ) |
std::
pair
<
iterator, bool > |
If
t
is a non-const rvalue,
value_type
is
MoveInsertable
into
X
; otherwise,
value_type
is
CopyInsertable
into
X
|
Inserts t if and only if there is no element in the container with key equivalent to the key of t |
The
bool
component of the returned pair indicates whether the insertion takes place, and the
iterator
component points to the element with key equivalent to the key of
t
|
Average case O(1) , worst case O ( a_uniq. size ( ) ) |
| a_eq. insert ( t ) |
iterator
|
If
t
is a non-const rvalue,
value_type
is
MoveInsertable
into
X
; otherwise,
value_type
is
CopyInsertable
into
X
|
Inserts t | An iterator pointing to the newly inserted element | Average case O(1) , worst case O ( a_eq. size ( ) ) |
| a. insert ( p, t ) |
iterator
|
If
t
is a non-const rvalue,
value_type
is
MoveInsertable
into
X
; otherwise,
value_type
is
CopyInsertable
into
X
|
a. insert ( t ) . The iterator p is a hint pointing to where the search should start. Implementations are permitted to ignore the hint | An iterator pointing to the element with the key equivalent to that of t | Average case O(1) , worst case O ( a. size ( ) ) |
| a. insert ( i, j ) | void |
value_type
is
EmplaceConstructible
into
X
from
*
i
. Neither
i
nor
j
are iterators into
a
|
a.
insert
(
t
)
for each element in
[
i
,
j
)
|
Average case O(N) , where N is std:: distance ( i, j ) , worst case O ( N· ( a. size ( ) + 1 ) ) | |
|
a.
insert_range
(
rg
)
(since C++23) |
void |
value_type
is
EmplaceConstructible
into
X
from
*
ranges::
begin
(
rg
)
.
rg
and
a
do not overlap
|
a. insert ( t ) for each element t in rg | Average case O(N) , where N is ranges:: distance ( rg ) , worst case O ( N· ( a. size ( ) + 1 ) ) | |
| a. insert ( il ) | a. insert ( il. begin ( ) , il. end ( ) ) | ||||
|
a_uniq.
insert
(
nh
)
(since C++17) |
insert_return_type
|
nh
is empty or
a_uniq.
get_allocator
(
)
|
If nh is empty, has no effect. Otherwise, inserts the element owned by nh if and only if there is no element in the container with a key equivalent to nh. key ( ) . Ensures: If nh is empty, inserted is false , position is end ( ) , and node is empty. Otherwise if the insertion took place, inserted is true , position points to the inserted element, and node is empty; if the insertion failed, inserted is false , node has the previous value of nh , and position points to an element with a key equivalent to nh. key ( ) | Average case O(1) , worst case O ( a_uniq. size ( ) ) | |
|
a_eq.
insert
(
nh
)
(since C++17) |
iterator
|
nh
is empty or
a_eq.
get_allocator
(
)
|
If nh is empty, has no effect and returns a_eq. end ( ) . Otherwise, inserts the element owned by nh and returns an iterator pointing to the newly inserted element. Ensures: nh is empty | Average case O(1) , worst case O ( a_eq. size ( ) ) | |
|
a.
insert
(
q, nh
)
(since C++17) |
iterator
|
nh
is empty or
a.
get_allocator
(
)
|
If nh is empty, has no effect and returns a. end ( ) . Otherwise, inserts the element owned by nh if and only if there is no element with key equivalent to nh. key ( ) in containers with unique keys; always inserts the element owned by nh in containers with equivalent keys. The iterator q is a hint pointing to where the search should start. Implementations are permitted to ignore the hint. Ensures: nh is empty if insertion succeeds, unchanged if insertion fails | An iterator pointing to the element with key equivalent to nh. key ( ) | Average case O(1) , worst case O ( a. size ( ) ) |
|
a.
extract
(
k
)
(since C++17) |
node_type
|
Removes an element in the container with key equivalent to k |
A
node_type
owning the element if found, otherwise an empty
node_type
|
Average case O(1) , worst case O ( a. size ( ) ) | |
|
a_tran.
extract
(
kx
)
(since C++23) |
node_type
|
Removes an element in the container with key equivalent to kx |
A
node_type
owning the element if found, otherwise an empty
node_type
|
Average case O(1) , worst case O ( a_tran. size ( ) ) | |
|
a.
extract
(
q
)
(since C++17) |
node_type
|
Removes the element pointed to by q |
A
node_type
owning that element
|
Average case O(1) , worst case O ( a. size ( ) ) | |
|
a.
merge
(
a2
)
(since C++17) |
void |
a.
get_allocator
(
)
== a2. get_allocator ( ) |
Attempts to extract each element in a2 and insert it into a using the hash function and key equality predicate of a . In containers with unique keys, if there is an element in a with key equivalent to the key of an element from a2 , then that element is not extracted from a2 . Ensures: Pointers and references to the transferred elements of a2 refer to those same elements but as members of a . Iterators referring to the transferred elements and all iterators referring to a will be invalidated, but iterators to elements remaining in a2 will remain valid | Average case O(N) , where N is a2. size ( ) , worst case O ( N· ( a. size ( ) + 1 ) ) | |
| a. erase ( k ) |
size_type
|
Erases all elements with key equivalent to k | The number of elements erased | Average case O ( a. count ( k ) ), worst case O ( a. size ( ) ) | |
|
a_tran.
erase
(
kx
)
(since C++23) |
size_type
|
Erases all elements with key equivalent to kx | The number of elements erased | Average case O ( a_tran. count ( kx ) ), worst case O ( a_tran. size ( ) ) | |
| a. erase ( q ) |
iterator
|
Erases the element pointed to by q | The iterator immediately following q prior to the erasure | Average case O(1) , worst case O ( a. size ( ) ) | |
|
a.
erase
(
r
)
(since C++17) |
iterator
|
Erases the element pointed to by r | The iterator immediately following r prior to the erasure | Average case O(1) , worst case O ( a. size ( ) ) | |
| a. erase ( q1, q2 ) |
iterator
|
Erases all elements in the range
[
q1
,
q2
)
|
The iterator immediately following the erased elements prior to the erasure | Average case linear in std:: distance ( q1, q2 ) , worst case O ( a. size ( ) ) | |
| a. clear ( ) | void | Erases all elements in the container. Ensures: a. empty ( ) is true | Linear in a. size ( ) | ||
| b. find ( k ) |
iterator
;
const_iterator
for constant
b
|
An iterator pointing to an element with key equivalent to k , or b. end ( ) if no such element exists | Average case O(1) , worst case O ( b. size ( ) ) | ||
|
a_tran.
find
(
ke
)
(since C++17) ? |
iterator
;
const_iterator
for constant
a_tran
|
An iterator pointing to an element with key equivalent to ke , or a_tran. end ( ) if no such element exists | Average case O(1) , worst case O ( a_tran. size ( ) ) | ||
| b. count ( k ) |
size_type
|
The number of elements with key equivalent to k | Average case O ( b. count ( k ) ), worst case O ( b. size ( ) ) | ||
|
a_tran.
count
(
ke
)
(since C++17) ? |
size_type
|
The number of elements with key equivalent to ke | Average case O ( a_tran. count ( ke ) ), worst case O ( a_tran. size ( ) ) | ||
|
b.
contains
(
k
)
(since C++20) ? |
b. find ( k ) ! = b. end ( ) | ||||
|
a_tran.
contains
(
ke
)
(since C++20) ? |
a_tran. find ( ke ) ! = a_tran. end ( ) | ||||
| b. equal_range ( k ) |
std::
pair
<
iterator, iterator > ;
std::
pair
<
|
A range containing all elements with keys equivalent to
k
. Returns
std::
make_pair
(
|
Average case O ( b. count ( k ) ), worst case O ( b. size ( ) ) | ||
|
a_tran.
equal_range
(
ke
)
(since C++20) ? |
std::
pair
<
iterator, iterator > ;
std::
pair
<
|
A range containing all elements with keys equivalent to
ke
. Returns
std::
make_pair
(
|
Average case O ( a_tran. count ( ke ) ), worst case O ( a_tran. size ( ) ) | ||
| b. bucket_count ( ) |
size_type
|
The number of buckets that b contains | Constant | ||
| b. max_bucket_count ( ) |
size_type
|
An upper bound on the number of buckets that b can ever contain | Constant | ||
| b. bucket ( k ) |
size_type
|
b. bucket_count ( ) > 0 |
The index of the bucket in which elements with keys equivalent to
k
would be found, if any such element existed. The return value is in
[
0
,
b.
bucket_count
(
)
)
|
Constant | |
| a_tran. bucket ( ke ) |
size_type
|
a_tran.
bucket_count ( ) > 0 |
The index of the bucket in which elements with keys equivalent to
ke
would be found, if any such element existed. The return value must be in the range
[
0
,
a_tran.
bucket_count
(
)
)
|
Constant | |
| b. bucket_size ( n ) |
size_type
|
n
is in
[
0
,
b.
bucket_count
(
)
)
|
The number of elements in the n th bucket | O ( b. bucket_size ( n ) ) | |
| b. begin ( n ) |
local_iterator
;
const_local_iterator
for constant
b
|
n
is in
[
0
,
b.
bucket_count
(
)
)
|
An iterator referring to the first element in the bucket. If the bucket is empty, then b. begin ( n ) == b. end ( n ) | Constant | |
| b. end ( n ) |
local_iterator
;
const_local_iterator
for constant
b
|
n
is in
[
0
,
b.
bucket_count
(
)
)
|
An iterator which is the past-the-end value for the bucket | Constant | |
| b. cbegin ( n ) |
const_local_iterator
|
n
is in
[
0
,
b.
bucket_count
(
)
)
|
An iterator referring to the first element in the bucket. If the bucket is empty, then b. cbegin ( n ) == b. cend ( n ) | Constant | |
| b. cend ( n ) |
const_local_iterator
|
n
is in
[
0
,
b.
bucket_count
(
)
)
|
An iterator which is the past-the-end value for the bucket | Constant | |
| b. load_factor ( ) | float | The average number of elements per bucket | Constant | ||
| b. max_load_factor ( ) | float | A positive number that the container attempts to keep the load factor less than or equal to. The container automatically increases the number of buckets as necessary to keep the load factor below this number | Constant | ||
| a. max_load_factor ( z ) | void | z is positive. May change the container's maximum load factor, using z as a hint | Constant | ||
| a. rehash ( n ) | void |
Ensures:
a.
bucket_count
(
)
>=
|
Average case linear in a. size ( ) , worst case O(N 2 ) | ||
| a. reserve ( n ) |
a.
rehash
(
std::
ceil
(
n / a. max_load_factor ( ) ) ) |
|
本小节内容不完整
原因：关于成员函数的要求说明待补充。 |
标准库
以下标准库容器满足 UnorderedAssociativeContainer 要求：
|
(C++11)
|
唯一键的集合，通过键进行哈希
(类模板) |
|
(C++11)
|
键的集合，通过键进行哈希
(类模板) |
|
(C++11)
|
键值对的集合，通过键进行哈希，键唯一
(类模板) |
|
(C++11)
|
键值对的集合，通过键进行哈希
(类模板) |
缺陷报告
以下行为变更缺陷报告被追溯应用于先前发布的C++标准。
| 缺陷报告 | 适用标准 | 发布时行为 | 正确行为 |
|---|---|---|---|
| LWG 2156 | C++11 |
重哈希后的负载因子只能
严格低于最大负载因子 |
允许等于 |