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.cn

命名空间

变体

视图

操作