C++ 具名要求：关联容器 (AssociativeContainer)

关联容器 (AssociativeContainer) 是提供基于键的快速对象查找的容器 (Container) 。

要求

凡例
`X`	容器类型
`a`	`X` 类型的值
`a2`	其结点句柄与 X 兼容的 `Y` 类型的值
`b`	`X` 类型的可能为 const 的值
`u`	任意变量名
`a_uniq`	（当 `X` 支持唯一键时）`X` 类型的值
`a_eq`	（当 `X` 支持多重键时）`X` 类型的值
`a_tran`	（当 `X::key_compare::is_transparent` 存在时）`X` 类型的可能为 const 的值
`i`, `j`	遗留输入迭代器 (LegacyInputIterator) ，指代有效范围并指向可隐式转换到 `X::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 的值
`kl`	一个值，使得 `a` 依据 c(r,kl) 已划分，其中 `r` 是 `e` 的键且 `e` 在 `a` 中
`ku`	一个值，使得 `a` 依据 !c(ku, r) 已划分
`ke`	一个值，使得 `a` 依据 c(r, ke) 与 !c(ke, r) 已划分，其中 c(r, ke) 隐含 !c(ke, r)
`A`	`X` 所用的存储分配器，或 std::allocator_type<X::value_type>
`m`	分配器，其类型可转换为 `A`
`nh`	`X::node_type` 类型的非 const 右值

表达式	返回类型	前条件/要求	后条件/效果	复杂度
X::key_type	`Key`	`Key` 可析构 (Destructible)		编译时
X::key_compare	`Compare`			编译时
X::value_compare	满足二元谓词 (BinaryPredicate) 的类型	对于 std::set 和 std::multiset 为 key_compare；对于 std::map 和 std::multimap 为 `Key` 上的顺序关系		编译时
X(c), X a(c);		key_compare 可复制构造 (CopyConstructible)	以 c 的副本为 `key_comp` 构造空容器	常数
X(), X a;		key_compare 可复制构造 (CopyConstructible)	以 Compare() 为 `key_comp` 构造空容器	常数
X(i, j, c), X a(i, j, c);		key_compare 可复制构造 (CopyConstructible) 且 value_type 从 *i 可就位构造 (EmplaceConstructible) 到 X	以 c 的副本为 `key_comp` 构造空容器并插入来自范围 `[i; j)` 的所有元素	通常为 `N log N`，或若 `[i, j)` 已排序则为 `N`（其中 `N` 是 std::distance(i, j)）
X(i, j), X a(i, j);		key_compare 可复制构造 (CopyConstructible) 且 value_type 从 *i 可就位构造 (EmplaceConstructible) 到 X	以 Compare() 为 `key_comp` 构造空容器并插入来自范围 `[i; j)` 的所有元素	通常为 `N log N`，或若 `[i, j)` 已按照 value_comp() 排序则为 `N`（其中 `N` 是 std::distance(i, j)）
X(il);		等价于 X(il.begin(), il.end());	等价于 X(il.begin(), il.end());
a = il	X&	`T` 可复制插入 (CopyInsertable) 到 `X` 而且亦可复制赋值 (CopyAssignable)	将范围 [il.begin(), il.end()) 赋值到 `a`。 `a` 的未被赋值元素均被销毁	通常为 `N log N`，或若 [il.begin(), il.end()) 已按照 value_comp() 排序则为 `N`（其中 `N` 是 il.size() + a.size()）
a.key_comp()	X::key_compare		返回构造 `a` 所用的比较对象。	常数
a.value_comp()	X::value_compare		返回在比较对象外构造的 X::value_compare 类型的对象。	常数

作为 std::map 或 std::multimap 的关联容器 X 额外支持表达式 X::mapped_type，它以 T 为返回的类型（但要求 T 可析构 (Destructible) ），及编译时复杂度。

标准库中的关联容器

set	唯一键的集合，按照键排序 (类模板)
multiset	键的集合，按照键排序 (类模板)
map	键值对的集合，按照键排序，键是唯一的 (类模板)
multimap	键值对的集合，按照键排序 (类模板)

语言
标准库头文件
自立与有宿主实现
具名要求
语言支持库
概念库 (C++20)
诊断库
工具库
字符串库
容器库
迭代器库
范围库 (C++20)
算法库
数值库
本地化库
输入/输出库
文件系统库 (C++17)
正则表达式库 (C++11)
原子操作库 (C++11)
线程支持库 (C++11)
技术规范

C++ 具名要求：关联容器 (AssociativeContainer)

要求

凡例

标准库中的关联容器