C++ 命名要求： 关联容器

关联容器是一种有序容器，它根据键提供对象的快速查找。

关联容器支持唯一键（如果它对每个键最多包含一个元素）。否则，它支持等价键。

要求

如果类型 X 满足关联容器，则

• 类型 X 满足容器 (直到 C++11) 分配器感知容器 (C++11 起)
• 以 Key 和排序关系 Compare 为参数，该排序关系 Compare 在 Key 的元素上引入严格弱序，并且
  • 此外，std::map 和 std::multimap 将任意映射类型 T 与 Key 关联起来。
  • Compare 类型的对象被称为类型 X 的容器的比较对象。

给定

• a，类型 X 的值
• a2，类型 Y 的值，其节点句柄与 X 兼容
• b，类型 X 或 const X 的值
• a_uniq，当 X 支持唯一键时，类型 X 的值
• a_eq，当 X 支持等价键时，类型 X 的值
• a_tran，当类型 X::key_compare::is_transparent 存在时，类型 X 或 const X 的值
• i 和 j，旧版输入迭代器，表示有效范围并引用隐式可转换为 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 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，一个值，使得
  • a 根据 c(x, kx) 和 !c(kx, x) 进行分区，其中 c(x, kx) 意味着 !c(kx, x)，并且 x 是 e 的键值，e 在 a 中，并且
  • 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	键
mapped_type	T（仅适用于std::map 和 std::multimap）
value_type	* 键（仅适用于std::set 和 std::multiset） * std::pair<const Key, T>（仅适用于std::map 和 std::multimap）	可从 X 擦除
key_compare	比较	可复制构造
value_compare	* 与 key_compare 相同（对于std::set 和 std::multiset） * 对由第一个组件（即 Key）引起的对的排序关系（对于std::map 和 std::multimap）	二元谓词
node_type	节点句柄类模板的特化，其公共嵌套类型与 X 中的相应类型相同。

方法和运算符

表达式	返回类型	前/要求	后/效果	复杂度
X(c)			使用 c 的副本作为比较对象构造一个空容器	常量
X(), X a = X();		X::key_compare 是默认可构造的	使用 Compare() 作为比较对象构造一个空容器	常量
X(i, j, c)		X::value_type 可从 *i 就地构造到 X 中	使用 c 的副本作为比较对象构造一个空容器，并插入范围 [i, j) 中的所有元素	通常为 N·log N，如果 [i, j) 已排序则为 N（其中 N 为 std::distance(i, j)）
X(i, j)		X::key_compare 是默认可构造的，并且 X::value_type 可从 *i 就地构造到 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 可复制插入到 X 中，并且也可复制赋值	将范围 [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 类型的对象。	常量

迭代器

关联容器的迭代器满足旧版双向迭代器的要求。

对于 value_type 与 key_type 相同的关联容器，迭代器和 const_iterator 都是常量迭代器。迭代器和 const_iterator 是否为同一类型未指定。

关联容器的迭代器以键的非降序遍历容器，其中非降序由用于构造容器的比较定义。也就是说，给定

• a，一个关联容器
• i 和 j，a 的可解引用迭代器

如果从 i 到 j 的距离为正，则 a.value_comp()(*j, *i) == false。此外，如果 a 是具有唯一键的关联容器，则更强的条件 a.value_comp()(*i, *j) != false 成立。

注意

此部分不完整
原因：未完成的要求

标准库中的关联容器

公有	std::set	唯一键的集合，按键排序
公有	std::multiset	键的集合，按键排序
公有	std::map	键值对的集合，按键排序，键唯一
公有	std::multimap	键值对的集合，按键排序

缺陷报告

以下改变行为的缺陷报告已追溯应用于先前发布的 C++ 标准。

DR	应用于	发布时的行为	正确行为
LWG 354	C++98	如果未找到元素，lower_bound 和 upper_bound 不返回 end 迭代器	在这种情况下它们返回 end 迭代器
LWG 589	C++98	i 和 j 引用的元素类型为 X::value_type	元素可隐式转换为 X::value_type