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

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

对于每个键都只能包含最多一个元素的关联容器支持唯一键，其他关联容器支持等价键。

满足以下条件的类型 X 是关联容器 (AssociativeContainer) ：

类型 X 是容器 (Container) (C++11 前)知分配器容器 (AllocatorAwareContainer) (C++11 起)
以类型 Key 和在 Key 类型的元素上引入严格弱序的排序关系 Compare 参数化
- 另外，std::map 和 std::multimap 会将一个任意 映射类型 T 关联到 Key。
- X 类型容器的类型是 Compare 的对象被称该容器的 比较对象。

并且，给定

a，X 类型的值
a2，节点把柄与 X 兼容的 Y 类型的值
b，X 或 const X 类型的值
a_uniq，支持唯一键的 X 类型的值
a_eq，支持等价键的 X 类型的值
a_tran，当类型 X::key_compare::is_transparent 存在时具有 X 或 const X 类型的值
i and j，表示有效范围并指代可以隐式转换到 X::value_type 的元素的老式输入迭代器 (LegacyInputIterator)
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 是 a 中的元素 e 的键值
ku，使得 a 以 !c(ku, x) 划分的值，其中 x 是 a 中的元素 e 的键值
ke，使得 a 以 c(x, ke) 和 !c(ke, x) 划分的值，其中 c(x, ke) 意味着 !c(ke, x)，并且 x 是 a 中的元素 e 的键值
kx，满足以下条件的值
- a 以 c(x, kx) 和 !c(kx, x) 划分，其中 c(x, kx) 意味着 !c(kx, x)，并且 x 是 a 中的元素 e 的键值
- kx 不可转换到 X::iterator 或 X::const_iterator
A，X 的分配器类型：在 X::allocator_type 存在时是该类型，否则是 std::allocator<X::value_type>
m，具有可转换到 A 的类型的分配器
nh，X::node_type 类型的非 const 右值

名称	类型	要求
`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`可擦除 (Erasable)
`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(), X a = X();		`X::key_compare`可默认构造 (DefaultConstructible)	以 Compare() 作为比较对象构造空容器	常数
X(i, j, c)		`X::value_type` 从 *i可就位构造 (EmplaceConstructible) 到 `X`	以 c 的副本作为比较对象构造空容器，并且插入范围 `[`i`,` j`)` 中的所有元素	通常是 `N·log N`，或者在 `[`i`,` j`)` 已排序时是 `N`（其中 `N` 是 std::distance(i, j)）
X(i, j)		`X::key_compare`可默认构造 (DefaultConstructible) ，并且 `X::value_type` 从 *i可就位构造 (EmplaceConstructible) 到 `X`	以 Compare() 作为比较对象构造空容器，并且插入范围 `[`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` 类型对象。	常数

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告	应用于	出版时的行为	正确行为
LWG 354	C++98	`lower_bound` 和 `upper_bound` 在没找到元素时不会返回尾迭代器	此时它们会返回尾迭代器
LWG 589	C++98	i 和 j 指代的元素具有 `X::value_type` 类型	那些元素可以隐式转换到 `X::value_type`