C++ 命名要求： AssociativeContainer

關聯容器（AssociativeContainer）是一種有序的容器（Container），它提供基於鍵的快速物件查詢。

如果一個關聯容器對於每個鍵最多隻能包含一個元素，則它支援*唯一鍵*。否則，它支援*等價鍵*。

圖例
`X`	一個關聯容器類
`T`	`X` 的元素型別
`A`	`X` 的分配器型別：如果存在，則為 `X::allocator_type`，否則為 std::allocator<X::value_type>
a	型別 `X` 的值
a2	型別 `Y` 的值，其節點控制代碼與 `X` 相容
b	型別 `X` 或 const X 的值
u	正在宣告的變數名
a_uniq	當 `X` 支援唯一鍵時，型別 `X` 的值
a_eq	當 `X` 支援等價鍵時，型別 `X` 的值
a_tran	當型別 `X::key_compare::is_transparent` 存在時，型別 `X` 或 const X 的值
i, j	指向可隱式轉換為 `X::value_type` 的元素的 LegacyInputIterators
`[`i`,` j`)`	一個有效範圍
rg (C++23 起)	型別 `R` 的值，它實現了 `container-compatible-range<value_type>`
p	指向 a 的有效常量迭代器
q	指向 a 的有效可解引用常量迭代器
r	指向 a 的有效可解引用迭代器
q1, q2	a 中常量迭代器的有效範圍
il	型別為 std::initializer_list<X::value_type> 的物件
t	型別為 `X::value_type` 的值
k	型別為 `X::key_type` 的值
c	型別為 `X::key_compare` 或 const X::key_compare 的值
kl	一個值，使得 a 相對於 c(x, kl) 被劃分，其中 x 是 e 的鍵值，並且 e 在 a 中
ku	一個值，使得 a 相對於 !c(ku, x) 被劃分，其中 x 是 e 的鍵值，並且 e 在 a 中
ke	一個值，使得 a 相對於 c(x, ke) 和 !c(ke, x) 被劃分，其中 c(x, ke) 隱含 !c(ke, x)，並且 x 是 e 的鍵值，並且 e 在 a 中
kx (C++23 起)	一個值，使得 a 相對於 c(x, kx) 和 !c(kx, x) 被劃分，其中 c(x, kx) 隱含 !c(kx, x)，並且 x 是 e 的鍵值，並且 e 在 a 中，並且 kx 不可轉換為 `X::iterator` 或 `X::const_iterator`
m	可轉換為 `A` 型別的分配器
nh	型別 `X::node_type` 的非 const 右值

型別 X 滿足 AssociativeContainer 如果

型別 X 滿足 Container(直至 C++11)AllocatorAwareContainer(自 C++11 起)，
以 Key 和排序關係 Compare 為引數，該關係在 Key 的元素上引入嚴格弱序，並且
- 此外，std::map 和 std::multimap 將任意*對映型別* T 與 Key 相關聯。
- 型別 Compare 的物件稱為型別 X 的容器的*比較物件*。
以下表達式必須有效，並對所有關聯容器產生其指定效果

[編輯] 型別

名稱	型別	要求
`key_type`	`Key`
`mapped_type`	`T` (僅適用於 std::map 和 std::multimap)
`value_type`	`Key` (僅適用於 std::set 和 std::multiset) std::pair<const Key, T>(僅適用於 std::map 和 std::multimap)	可從 `X` 擦除
`key_compare`	`Compare`	CopyConstructible（可複製構造）
`value_compare`	與 `key_compare` 相同 (對於 std::set 和 std::multiset) 由第一元件（即 `Key`）引入的對的排序關係 (對於 std::map 和 std::multimap)	BinaryPredicate（二元謂詞）
`node_type`	節點控制代碼類模板的特化，使得公共巢狀型別與 `X` 中相應的型別相同。

[編輯] 成員函式和運算子

表示式	結果	前置條件	效果	返回	複雜度
X(c)			構造一個空容器。使用 c 的副本作為比較物件		常數
X u = X(); X u;		`key_compare` 滿足 DefaultConstructible 要求	構造一個空容器。使用 Compare() 作為比較物件		常數
X(i, j, c)		`value_type` 可從 *i 就位構造到 `X`	構造一個空容器，並從範圍 `[`i`,` j`)` 插入元素；使用 c 作為比較物件		通常為 N·log(N)，其中 `N` 的值為 std::distance(i, j)；如果 `[`i`,` j`)` 相對於 value_comp() 已排序，則為線性
X(i, j)		`key_compare` 滿足 DefaultConstructible 要求。`value_type` 可從 *i 就位構造到 `X`	構造一個空容器，並從範圍 `[`i`,` j`)` 插入元素；使用 Compare() 作為比較物件
X(from_range, rg, c) (C++23 起)		`value_type` 可從 *ranges::begin(rg) 就位構造到 `X`	構造一個空容器，並將 rg 中的每個元素插入其中。使用 c 作為比較物件		通常為 N·log(N)，其中 `N` 的值為 ranges::distance(rg)；如果 rg 相對於 value_comp() 已排序，則為線性
X(from_range, rg) (C++23 起)		`key_compare` 滿足 DefaultConstructible 要求。`value_type` 可從 *ranges::begin(rg) 就位構造到 `X`	構造一個空容器，並將 rg 中的每個元素插入其中。使用 Compare() 作為比較物件
X(il, c)			X(il.begin(), il.end(), c)
X(il)			X(il.begin(), il.end())
a = il	X&	`value_type` 可複製插入到 `X` 且可複製賦值	將範圍 `[`il.begin()`,` il.end()`)` 賦值給 a。 a 的所有現有元素要麼被賦值，要麼被銷燬		通常為 N·log(N)，其中 `N` 的值為 il.size() + a.size()；如果 `[`il.begin()`,` il.end()`)` 相對於 value_comp() 已排序，則為線性
b.key_comp()	`X::key_compare`			構造 b 的比較物件	常數
b.value_comp()	`X::value_compare`			由比較物件構造的 `value_compare` 物件	常數
a_uniq.emplace(args)	std::pair< iterator, bool>	`value_type` 可從 args 就位構造到 `X`	僅當容器中不存在鍵與 t 的鍵等價的元素時，才插入一個使用 std::forward<Args>(args)... 構造的 `value_type` 物件 t	返回對的 bool 元件當且僅當插入發生時為 true，並且對的迭代器元件指向鍵與 t 的鍵等價的元素	對數時間
a_eq.emplace(args)	`iterator`	`value_type` 可從 args 就位構造到 `X`	插入一個使用 std::forward<Args>(args)... 構造的 `value_type` 物件 t。如果 a_eq 中存在包含與 t 等價元素的範圍，則將 t 插入到該範圍的末尾	指向新插入元素的迭代器	對數時間
a.emplace_hint(p, args)	`iterator`		等價於 a.emplace( std::forward<Args>(args)...)，除了元素儘可能靠近 p 前面的位置插入	指向鍵與新插入元素的鍵等價的元素的迭代器	通常為對數時間，但如果元素緊接在 p 之前插入，則為均攤常數時間
a_uniq.insert(t)	std::pair< iterator, bool>	如果 t 是非 const 右值，則 `value_type` 可移動插入到 `X`；否則，`value_type` 可複製插入到 `X`	當且僅當容器中不存在鍵與 t 的鍵等價的元素時，才插入 t	返回對的 bool 元件當且僅當插入發生時為 true，並且對的 `iterator` 元件指向鍵與 t 的鍵等價的元素	對數時間
a_eq.insert(t)	`iterator`	如果 t 是非 const 右值，則 `value_type` 可移動插入到 `X`；否則，`value_type` 可複製插入到 `X`	插入 t 並返回指向新插入元素的迭代器。如果 a_eq 中存在包含與 t 等價元素的範圍，則將 t 插入到該範圍的末尾		對數時間
a.insert(p, t)	`iterator`	如果 t 是非 const 右值，則 `value_type` 可移動插入到 `X`；否則，`value_type` 可複製插入到 `X`	僅當唯一鍵容器中不存在鍵與 t 的鍵等價的元素時，才插入 t；在等價鍵容器中總是插入 t。 t 儘可能靠近 p 前面的位置插入	指向鍵與 t 的鍵等價的元素的迭代器	通常為對數時間，但如果 t 緊接在 p 之前插入，則為均攤常數時間
a.insert(i, j)	void	`value_type` 可從 *i 就位構造到 `X`。 i 和 j 都不是 a 的迭代器	僅當唯一鍵容器中不存在鍵與該元素的鍵等價的元素時，才插入範圍 `[`i`,` j`)` 中的每個元素；在等價鍵容器中總是插入該元素		N·log(a.size() + N)，其中 `N` 的值為 std::distance(i, j)
a.insert_range(rg) (C++23 起)	void	`value_type` 可從 *ranges::begin(rg) 就位構造到 `X`。 rg 和 a 不重疊	僅當唯一鍵容器中不存在鍵與該元素的鍵等價的元素時，才插入 rg 中的每個元素；在等價鍵容器中總是插入該元素		N·log(a.size() + N)，其中 `N` 的值為 ranges::distance(rg)
a.insert(il)			a.insert(il.begin(), il.end())
a_uniq.insert(nh)	`insert_return_type`	nh 為空或 a_uniq.get_allocator() == nh.get_allocator() 為 true	如果 nh 為空，則無效果。否則，當且僅當容器中不存在鍵與 nh.key() 等價的元素時，才插入 nh 所擁有的元素	如果 nh 為空，`inserted` 為 false，`position` 為 end()，且 `node` 為空。否則，如果插入成功，`inserted` 為 true，`position` 指向插入的元素，且 `node` 為空；如果插入失敗，`inserted` 為 false，`node` 具有 nh 的前一個值，且 `position` 指向鍵與 nh.key() 等價的元素	對數時間
a_eq.insert(nh)	`iterator`	nh 為空或 a_eq.get_allocator() == nh.get_allocator() 為 true	如果 nh 為空，則無效果並返回 a_eq.end()。否則，插入 nh 所擁有的元素並返回指向新插入元素的迭代器。如果 a_eq 中存在包含鍵與 nh.key() 等價的元素的範圍，則將該元素插入到該範圍的末尾。確保：nh 為空		對數時間
a.insert(p, nh)	`iterator`	nh 為空或 a.get_allocator() == nh.get_allocator() 為 true	如果 nh 為空，則無效果並返回 a.end()。否則，僅當唯一鍵容器中不存在鍵與 nh.key() 等價的元素時，才插入 nh 所擁有的元素；在等價鍵容器中總是插入 nh 所擁有的元素。該元素儘可能靠近 p 前面的位置插入。確保：如果插入成功，nh 為空；如果插入失敗，則不變	指向鍵與 nh.key() 等價的元素的迭代器	通常為對數時間，但如果元素緊接在 p 之前插入，則為均攤常數時間
a.extract(k)	`node_type`		刪除容器中鍵與 k 等價的第一個元素	如果找到，則為擁有該元素的 `node_type`；否則為空 `node_type`	log(a.size())
a_tran.extract(kx) (C++23 起)	`node_type`		刪除容器中鍵為 r 且 !c(r, kx) && !c(kx, r) 為 true 的第一個元素	如果找到，則為擁有該元素的 `node_type`；否則為空 `node_type`	log(a_tran.size())
a.extract(q)	`node_type`		刪除 q 指向的元素	擁有該元素的 `node_type`	均攤常數時間
a.merge(a2)	void	a.get_allocator() == a2.get_allocator()	嘗試提取 a2 中的每個元素，並使用 a 的比較物件將其插入到 a 中。在唯一鍵容器中，如果 a 中存在鍵與 a2 中元素的鍵等價的元素，則不會從 a2 中提取該元素。確保：指向 a2 中已轉移元素的指標和引用仍然指向這些相同的元素，但現在它們是 a 的成員。指向已轉移元素的迭代器將繼續指向它們的元素，但它們現在表現為 a 的迭代器，而不是 a2 的迭代器。丟擲：除非比較物件丟擲，否則不丟擲任何異常		N·log(a.size() + N)，其中 `N` 的值為 a2.size()
a.erase(k)	`size_type`		刪除容器中所有鍵與 k 等價的元素	已刪除元素的數量	log(a.size()) + a.count(k)
a_tran.erase(kx) (C++23 起)	`size_type`		刪除容器中鍵為 r 且 !c(r, kx) && !c(kx, r) 為 true 的所有元素	已刪除元素的數量	log(a_tran.size()) + a_tran.count(kx)
a.erase(q)	`iterator`		刪除 q 指向的元素	指向緊跟在被刪除元素之前的 q 後面的元素的迭代器。如果不存在此類元素，則返回 a.end()	均攤常數時間
a.erase(r)	`iterator`		刪除 r 指向的元素	一個迭代器，指向緊隨被擦除元素 r 之前的元素。如果不存在這樣的元素，則返回 a.end()。	均攤常數時間
a.erase(q1, q2)	`iterator`		擦除範圍內的所有元素 `[`q1`,` q2`)`	一個迭代器，指向在任何元素被擦除之前 q2 所指向的元素。如果不存在這樣的元素，則返回 a.end()。	log(a.size()) + N，其中 `N` 的值為 std::distance(q1, q2)
a.clear()			a.erase(a.begin(), a.end())。確保：a.empty() 為 true。		與 a.size() 成線性關係
b.find(k)	`iterator`；對於常量 b 則是 `const_iterator`			一個迭代器，指向鍵等價於 k 的元素，如果未找到此類元素，則為 b.end()	對數時間
a_tran.find(ke)	`iterator`；對於常量 a_tran 則是 `const_iterator`			一個迭代器，指向鍵 r 滿足以下條件的元素 !c(r, ke) && !c(ke, r) 為 true，如果未找到此類元素，則為 a_tran.end()	對數時間
b.count(k)	`size_type`			鍵等價於 k 的元素數量	log(b.size()) + b.count(k)
a_tran.count(ke)	`size_type`			鍵 r 滿足以下條件的元素數量 !c(r, ke) && !c(ke, r)	log(a_tran.size()) + a_tran.count(ke)
b.contains(k)	bool		return b.find(k) != b.end();
a_tran.contains(ke)	bool		return a_tran.find(ke) != a_tran.end();
b.lower_bound(k)	`iterator`；對於常量 b 則是 `const_iterator`			一個迭代器，指向第一個鍵不小於 k 的元素，如果未找到此類元素，則為 b.end()	對數時間
a_tran.lower_bound(kl)	`iterator`；對於常量 a_tran 則是 `const_iterator`			一個迭代器，指向第一個鍵 r 滿足 !c(r, kl) 的元素，如果未找到此類元素，則為 a_tran.end()	對數時間
b.upper_bound(k)	`iterator`；對於常量 b 則是 `const_iterator`			一個迭代器，指向第一個鍵大於 k 的元素，如果未找到此類元素，則為 b.end()	對數時間
a_tran.upper_bound(ku)	`iterator`；對於常量 a_tran 則是 `const_iterator`			一個迭代器，指向第一個鍵 r 滿足 c(ku, r) 的元素，如果未找到此類元素，則為 a_tran.end()	對數時間
b.equal_range(k)	std::pair< iterator, iterator>; std::pair< const_iterator, const_iterator> 對於常量 b		等價於 return std::make_pair( b.lower_bound(k), b.upper_bound(k));		對數時間
a_tran.equal_range(ke)	std::pair< iterator, iterator>; std::pair< const_iterator, const_iterator> 對於常量 a_tran		等價於 return std::make_pair( a_tran.lower_bound(ke), a_tran.upper_bound(ke));		對數時間

[編輯] 迭代器

關聯容器的迭代器滿足 LegacyBidirectionalIterator 的要求。

對於 value_type 與 key_type 相同的關聯容器，iterator 和 const_iterator 都是常量迭代器。iterator 和 const_iterator 是否為相同型別是未指定的。

關聯容器的迭代器以鍵的非降序遍歷容器，其中非降序由用於構造容器的比較定義。也就是說，給定

a，一個關聯容器
i 和 j，指向 a 的可解引用迭代器。

如果從 i 到 j 的距離為正，則 a.value_comp()(*j, *i) == false。此外，如果 a 是具有唯一鍵的關聯容器，則更強的條件 a.value_comp()(*i, *j) != false 成立。

[編輯] 標準庫

以下標準庫容器滿足 AssociativeContainer 要求

set	唯一鍵的集合，按鍵排序 (類模板) [編輯]
multiset	鍵的集合，按鍵排序 (類模板) [編輯]
map	鍵值對集合，按鍵排序，鍵唯一 (類模板) [編輯]
multimap	鍵值對的集合，按鍵排序 (類模板) [編輯]

[編輯] 缺陷報告

下列更改行為的缺陷報告追溯地應用於以前出版的 C++ 標準。

缺陷報告	應用於	釋出時的行為	正確的行為
LWG 354	C++98	`lower_bound` 和 `upper_bound` 沒有在沒有找到元素時返回 end 迭代器	它們在這種情況下返回 end 迭代器
LWG 589	C++98	由 i 和 j 引用的元素的型別為 `X::value_type`	這些元素可以隱式轉換為 `X::value_type`

編譯器支援
自由（freestanding）與宿主（hosted）
語言
標準庫
標準庫標頭檔案
具名要求
特性測試宏 (C++20)
語言支援庫
概念庫 (C++20)
診斷庫
記憶體管理庫
超程式設計庫 (C++11)
通用工具庫
容器庫
迭代器庫
範圍庫 (C++20)
演算法庫
字串庫
文字處理庫
數值庫
日期和時間庫
輸入/輸出庫
檔案系統庫 (C++17)
併發支援庫 (C++11)
執行控制庫 (C++26)
技術規範
符號索引
外部庫

cppreference.com

名稱空間

變體

檢視

操作