C++ 命名要求： UnorderedAssociativeContainer (C++11 起)
來自 cppreference.com
無序關聯容器是 Container，它根據鍵提供物件的快速查詢。在最壞情況下，複雜度是線性的，但對於大多數操作，平均速度要快得多。
無序關聯容器透過 `Key` 引數化；`Hash` 是一個 Hash 函式物件，它作為 `Key` 的雜湊函式；`Pred` 是一個 BinaryPredicate，用於評估 `Key` 之間的等價性。std::unordered_map 和 std::unordered_multimap 還有一個與 `Key` 關聯的對映型別 `T`。
如果兩個 `Key` 根據 `Pred` 相等，則 `Hash` 必須為兩個鍵返回相同的值。
|
如果 `Hash::is_transparent` 和 `Pred::is_transparent` 都存在並且各自命名一個型別，則成員函式 `find`、`contains`、`count`、`equal_range` 和 `bucket` 接受 `Key` 以外型別的引數，並期望 `Hash` 可以用這些型別的值呼叫，並且 `Pred` 是一個透明的比較函式，例如 std::equal_to<>。 |
(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>。
無序關聯容器中的元素被組織成桶，具有相同雜湊值的鍵將最終落在同一個桶中。當容器的大小增加時，桶的數量也會增加，以使每個桶中的平均元素數量保持在某個值以下。
再雜湊會使迭代器失效，並可能導致元素在不同的桶中重新排列，但它不會使對元素的引用失效。
無序關聯容器滿足 AllocatorAwareContainer 的要求。對於 std::unordered_map 和 std::unordered_multimap，AllocatorAwareContainer 中 `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 |
|
| std::pair<const Key, T> | std::unordered_map 和 std::unordered_multimap 僅適用。可擦除於 X |
||
X::hasher
|
Hash（雜湊）
|
Hash（雜湊） | |
X::key_equal
|
Pred
|
可複製構造；二元謂詞，它接受兩個 Key 型別的引數並表示等價關係 |
|
X::local_iterator
|
LegacyIterator（傳統迭代器） | 類別和型別與 X::iterator 相同 |
可用於遍歷單個桶，但不能跨桶遍歷 |
X::const_local_iterator
|
LegacyIterator（傳統迭代器） | 類別和型別與 X::const_iterator 相同 | |
X::node_type (C++17 起) |
node-handle 類模板的特化 | 公共巢狀型別與 X 中相應的型別相同 |
[編輯] 成員函式和運算子
| 表示式 | 結果 | 前置條件 | 效果 | 返回 | 複雜度 |
|---|---|---|---|---|---|
| X(n, hf, eq) | 構造一個空容器，至少有 n 個桶，使用 hf 作為雜湊函式，eq 作為鍵相等謂詞 | O(n) | |||
| X(n, hf) | key_equal 是 可預設構造的 |
構造一個空容器，至少有 n 個桶，使用 hf 作為雜湊函式，key_equal() 作為鍵相等謂詞 | O(n) | ||
| X(n) | hasher 和 key_equal 是 可預設構造的 |
構造一個空容器，至少有 n 個桶，使用 hasher() 作為雜湊函式，key_equal() 作為鍵相等謂詞 | O(n) | ||
| X a = X(); X a; |
hasher 和 key_equal 是 可預設構造的 |
構造一個空容器，桶的數量未指定，使用 hasher() 作為雜湊函式，key_equal() 作為鍵相等謂詞 | 常量 | ||
| X(i, j, n, hf, eq) | value_type 是 可就地構造到 X 的，從 *i 開始 |
構造一個空容器，至少有 n 個桶，使用 hf 作為雜湊函式，eq 作為鍵相等謂詞，並從 [i, j) 插入元素 |
平均情況 O(N)（N 為 std::distance(i, j)），最壞情況 O(N2) | ||
| X(i, j, n, hf) | key_equal 是 可預設構造的。value_type 是 可就地構造到 X 的，從 *i 開始 |
構造一個空容器，至少有 n 個桶，使用 hf 作為雜湊函式，key_equal() 作為鍵相等謂詞，並從 [i, j) 插入元素 |
平均情況 O(N)（N 為 std::distance(i, j)），最壞情況 O(N2) | ||
| X(i, j, n) | hasher 和 key_equal 是 可預設構造的。value_type 是 可就地構造到 X 的，從 *i 開始 |
構造一個空容器，至少有 n 個桶，使用 hasher() 作為雜湊函式，key_equal() 作為鍵相等謂詞，並從 [i, j) 插入元素 |
平均情況 O(N)（N 為 std::distance(i, j)），最壞情況 O(N2) | ||
| X(i, j) | hasher 和 key_equal 是 可預設構造的。value_type 是 可就地構造到 X 的，從 *i 開始 |
構造一個空容器，桶的數量未指定，使用 hasher() 作為雜湊函式，key_equal() 作為鍵相等謂詞，並從 [i, j) 插入元素 |
平均情況 O(N)（N 為 std::distance(i, j)），最壞情況 O(N2) | ||
| X(std::from_range, rg, n, hf, eq) (C++23 起) |
value_type 是 可就地構造到 X 的，從 *ranges::begin(rg) 開始 |
構造一個空容器，至少有 n 個桶，使用 hf 作為雜湊函式，eq 作為鍵相等謂詞，並從 rg 插入元素 | 平均情況 O(N)（N 為 ranges::distance(rg)），最壞情況 O(N2) | ||
| X(std::from_range, rg, n, hf) (C++23 起) |
key_equal 是 可預設構造的。value_type 是 可就地構造到 X 的，從 *ranges::begin(rg) 開始 |
構造一個空容器，至少有 n 個桶，使用 hf 作為雜湊函式，key_equal() 作為鍵相等謂詞，並從 rg 插入元素 | 平均情況 O(N)（N 為 ranges::distance(rg)），最壞情況 O(N2) | ||
| X(std::from_range, rg, n) (C++23 起) |
hasher 和 key_equal 是 可預設構造的。value_type 是 可就地構造到 X 的，從 *ranges::begin(rg) 開始 |
構造一個空容器，至少有 n 個桶，使用 hasher() 作為雜湊函式，key_equal() 作為鍵相等謂詞，並從 rg 插入元素 | 平均情況 O(N)（N 為 ranges::distance(rg)），最壞情況 O(N2) | ||
| X(std::from_range, rg) (C++23 起) |
hasher 和 key_equal 是 可預設構造的。value_type 是 可就地構造到 X 的，從 *ranges::begin(rg) 開始 |
構造一個空容器，桶的數量未指定，使用 hasher() 作為雜湊函式，key_equal() 作為鍵相等謂詞，並從 rg 插入元素 | 平均情況 O(N)（N 為 ranges::distance(rg)），最壞情況 O(N2) | ||
| 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) | 容器；複製雜湊函式、謂詞和最大負載因子 | 平均情況為 b.size() 的線性複雜度，最壞情況為 O(N2) | |||
| a = b | X&
|
容器；複製雜湊函式、謂詞和最大負載因子 | 平均情況為 b.size() 的線性複雜度，最壞情況為 O(N2) | ||
| a = il | X&
|
value_type 可 複製插入到 X 中，且可 複製賦值 |
將範圍 [il.begin(), il.end()) 賦值給 a。 a 中所有現有元素要麼被賦值，要麼被銷燬 |
平均情況為 il.size() 的線性複雜度，最壞情況為 O(N2) | |
| b.hash_function() | 雜湊器
|
b 的雜湊函式 | 常量 | ||
| b.key_eq() | 鍵相等
|
b 的鍵相等謂詞 | 常量 | ||
| a_uniq.emplace(args) | std::pair< 迭代器, bool> |
value_type 可 就地構造到 X 的，從 args 開始 |
僅當容器中沒有與 t 的鍵等效的元素時，才插入使用 std::forward<Args>(args)... 構造的 value_type 物件 t |
返回對的 bool 分量當且僅當插入發生時為 true，並且對的迭代器分量指向鍵與 t 的鍵等效的元素 | 平均情況 O(1)，最壞情況 O(a_uniq.size()) |
| a_eq.emplace(args) | 迭代器
|
value_type 可 就地構造到 X 的，從 args 開始 |
插入使用 std::forward<Args>(args)... 構造的 value_type 物件 t |
指向新插入元素的迭代器 | 平均情況 O(1)，最壞情況 O(a_eq.size()) |
| a.emplace_hint(p, args) | 迭代器
|
value_type 可 就地構造到 X 的，從 args 開始 |
a.emplace( std::forward<Args>(args)...) |
指向鍵與新插入元素等效的元素的迭代器。const_iterator p 是一個提示，指示搜尋應從何處開始。允許實現忽略該提示 |
平均情況 O(1)，最壞情況 O(a.size()) |
| a_uniq.insert(t) | std::pair< 迭代器, bool> |
如果 t 是一個非 const 右值，value_type 可 移動插入到 X 中；否則，value_type 可 複製插入到 X 中 |
當且僅當容器中沒有與 t 的鍵等效的元素時，才插入 t | 返回對的 bool 分量表示是否發生插入，並且 iterator 分量指向鍵與 t 的鍵等效的元素 |
平均情況 O(1)，最壞情況 O(a_uniq.size()) |
| a_eq.insert(t) | 迭代器
|
如果 t 是一個非 const 右值，value_type 可 移動插入到 X 中；否則，value_type 可 複製插入到 X 中 |
插入 t | 指向新插入元素的迭代器 | 平均情況 O(1)，最壞情況 O(a_eq.size()) |
| a.insert(p, t) | 迭代器
|
如果 t 是一個非 const 右值，value_type 可 移動插入到 X 中；否則，value_type 可 複製插入到 X 中 |
a.insert(t)。迭代器 p 是一個提示，指示搜尋應從何處開始。允許實現忽略該提示 | 指向鍵與 t 的鍵等效的元素的迭代器 | 平均情況 O(1)，最壞情況 O(a.size()) |
| a.insert(i, j) | void | value_type 是 可就地構造到 X 的，從 *i 開始。 i 和 j 都不是 a 的迭代器 |
對於範圍中的每個元素，執行 a.insert(t)[i, j)
|
平均情況 O(N)，其中 N 為 std::distance(i, j)，最壞情況 O(N·(a.size() + 1)) | |
| a.insert_range(rg) (C++23 起) |
void | value_type 是 可就地構造到 X 的，從 *ranges::begin(rg) 開始。 rg 和 a 不重疊 |
對於 rg 中的每個元素 t，執行 a.insert(t) | 平均情況 O(N)，其中 N 為 ranges::distance(rg)，最壞情況 O(N·(a.size() + 1)) | |
| a.insert(il) | a.insert(il.begin(), il.end()) | ||||
| a_uniq.insert(nh) (C++17 起) |
insert_return_type
|
nh 為空或 a_uniq.get_allocator() |
如果 nh 為空，則無效果。否則，當且僅當容器中沒有與 nh.key() 的鍵等效的元素時，插入 nh 所擁有的元素。確保：如果 nh 為空，則 inserted 為 false，position 為 end()，且 node 為空。否則，如果插入成功，則 inserted 為 true，position 指向插入的元素，且 node 為空；如果插入失敗，則 inserted 為 false，node 具有 nh 的先前值，且 position 指向鍵與 nh.key() 的鍵等效的元素 | 平均情況 O(1)，最壞情況 O(a_uniq.size()) | |
| a_eq.insert(nh) (C++17 起) |
迭代器
|
nh 為空或 a_eq.get_allocator() |
如果 nh 為空，則無效果並返回 a_eq.end()。否則，插入 nh 所擁有的元素並返回指向新插入元素的迭代器。確保：nh 為空 | 平均情況 O(1)，最壞情況 O(a_eq.size()) | |
| a.insert(q, nh) (C++17 起) |
迭代器
|
nh 為空或 a.get_allocator() |
如果 nh 為空，則無效果並返回 a.end()。否則，當且僅當具有唯一鍵的容器中沒有與 nh.key() 的鍵等效的元素時，插入 nh 所擁有的元素；對於具有等效鍵的容器，始終插入 nh 所擁有的元素。迭代器 q 是一個提示，指示搜尋應從何處開始。允許實現忽略該提示。確保：如果插入成功，則 nh 為空，如果插入失敗，則不變 | 指向鍵與 nh.key() 的鍵等效的元素的迭代器 | 平均情況 O(1)，最壞情況 O(a.size()) |
| a.extract(k) (C++17 起) |
node_type
|
刪除容器中鍵與 k 等效的元素 | 如果找到，則為擁有該元素的 node_type，否則為空的 node_type |
平均情況 O(1)，最壞情況 O(a.size()) | |
| a_tran.extract(kx) (C++23 起) |
node_type
|
刪除容器中鍵與 kx 等效的元素 | 如果找到，則為擁有該元素的 node_type，否則為空的 node_type |
平均情況 O(1)，最壞情況 O(a_tran.size()) | |
| a.extract(q) (C++17 起) |
node_type
|
刪除 q 指向的元素 | 擁有該元素的 node_type |
平均情況 O(1)，最壞情況 O(a.size()) | |
| a.merge(a2) (C++17 起) |
void | a.get_allocator() == a2.get_allocator() |
嘗試提取 a2 中的每個元素並使用 a 的雜湊函式和鍵相等謂詞將其插入 a。在具有唯一鍵的容器中，如果 a 中存在一個鍵與來自 a2 的元素的鍵等效的元素，則該元素不會從 a2 中提取。確保：指向 a2 中已轉移元素的指標和引用引用相同的元素，但作為 a 的成員。引用已轉移元素的迭代器以及所有引用 a 的迭代器都將失效，但 a2 中剩餘元素的迭代器將保持有效 | 平均情況 O(N)，其中 N 為 a2.size()，最壞情況 O(N·(a.size() + 1)) | |
| a.erase(k) | size_type
|
擦除所有鍵與 k 等效的元素 | 被擦除的元素數量 | 平均情況 O(a.count(k))，最壞情況 O(a.size()) | |
| a_tran.erase(kx) (C++23 起) |
size_type
|
擦除所有鍵與 kx 等效的元素 | 被擦除的元素數量 | 平均情況 O(a_tran.count(kx))，最壞情況 O(a_tran.size()) | |
| a.erase(q) | 迭代器
|
擦除 q 指向的元素 | 緊接在擦除前 q 之後的迭代器 | 平均情況 O(1)，最壞情況 O(a.size()) | |
| a.erase(r) (C++17 起) |
迭代器
|
擦除 r 指向的元素 | 緊接在擦除前 r 之後的迭代器 | 平均情況 O(1)，最壞情況 O(a.size()) | |
| a.erase(q1, q2) | 迭代器
|
擦除範圍內的所有元素[q1, q2)
|
緊接在擦除前被擦除元素之後的迭代器 | 平均情況 O(N)，其中 N 為 std::distance(q1, q2)，最壞情況 O(a.size()) | |
| a.clear() | void | 擦除容器中的所有元素。確保：a.empty() 為 true | 線性複雜度，與 a.size() 相關 | ||
| b.find(k) | iterator；對於常量 b，為 const_iterator |
指向鍵與 k 等效的元素的迭代器，如果不存在此類元素，則為 b.end() | 平均情況 O(1)，最壞情況 O(b.size()) | ||
| a_tran.find(ke) (C++17 起)? |
iterator；對於常量 a_tran，為 const_iterator |
指向鍵與 ke 等效的元素的迭代器，如果不存在此類元素，則為 a_tran.end() | 平均情況 O(1)，最壞情況 O(a_tran.size()) | ||
| b.count(k) | size_type
|
鍵與 k 等效的元素數量 | 平均情況 O(b.count(k))，最壞情況 O(b.size()) | ||
| a_tran.count(ke) (C++17 起)? |
size_type
|
鍵與 ke 等效的元素數量 | 平均情況 O(a_tran.count(ke))，最壞情況 O(a_tran.size()) | ||
| b.contains(k) (C++20 起)? |
b.find(k) != b.end() | ||||
| a_tran.contains(ke) (C++20 起)? |
a_tran.find(ke) != a_tran.end() | ||||
| b.equal_range(k) | std::pair< 迭代器, 迭代器>; std::pair< |
包含所有鍵與 k 等效的元素的範圍。如果不存在此類元素，則返回 std::make_pair( |
平均情況 O(b.count(k))，最壞情況 O(b.size()) | ||
| a_tran.equal_range(ke) (C++20 起)? |
std::pair< 迭代器, 迭代器>; std::pair< |
包含所有鍵與 ke 等效的元素的範圍。如果不存在此類元素，則返回 std::make_pair( |
平均情況 O(a_tran.count(ke))，最壞情況 O(a_tran.size()) | ||
| b.bucket_count() | size_type
|
b 包含的桶的數量 | 常量 | ||
| b.max_bucket_count() | size_type
|
b 可以包含的桶數量的上限 | 常量 | ||
| b.bucket(k) | size_type
|
b.bucket_count() > 0 | 鍵與 k 等效的元素（如果存在）將位於的桶的索引。返回值在 [0, b.bucket_count()) 範圍內 |
常量 | |
| a_tran.bucket(ke) | size_type
|
a_tran. bucket_count() > 0 |
鍵與 ke 等效的元素（如果存在）將位於的桶的索引。返回值必須在 [0, a_tran.bucket_count()) 範圍內 |
常量 | |
| b.bucket_size(n) | size_type
|
n 在 [0, b.bucket_count()) 範圍內 |
第 n 個桶中的元素數量 | O(b.bucket_size(n)) | |
| b.begin(n) | local_iterator；對於常量 b，為 const_local_iterator |
n 在 [0, b.bucket_count()) 範圍內 |
指向桶中第一個元素的迭代器。如果桶為空，則 b.begin(n) == b.end(n) | 常量 | |
| b.end(n) | local_iterator；對於常量 b，為 const_local_iterator |
n 在 [0, b.bucket_count()) 範圍內 |
桶的末尾值迭代器 | 常量 | |
| b.cbegin(n) | const_local_iterator
|
n 在 [0, b.bucket_count()) 範圍內 |
指向桶中第一個元素的迭代器。如果桶為空，則 b.cbegin(n) == b.cend(n) | 常量 | |
| b.cend(n) | const_local_iterator
|
n 在 [0, b.bucket_count()) 範圍內 |
桶的末尾值迭代器 | 常量 | |
| b.load_factor() | float | 每個桶的平均元素數量 | 常量 | ||
| b.max_load_factor() | float | 一個正數，容器試圖將負載因子保持在該數之下或等於該數。容器在必要時自動增加桶的數量，以使負載因子低於該數 | 常量 | ||
| a.max_load_factor(z) | void | z 為正數。可能會更改容器的最大負載因子，使用 z 作為提示 | 常量 | ||
| a.rehash(n) | void | 確保 a.bucket_count() >= |
平均情況線性複雜度，與 a.size() 相關，最壞情況 O(N2) | ||
| 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 | 再雜湊後的負載因子只能是 嚴格低於最大負載因子 |
允許相等 |
