C++ 命名要求： AssociativeContainer

 

C++

编译器支持

独立和托管

语言

标准库

标准库头文件

命名要求

特性测试宏 (C++20)

语言支持库

概念库 (C++20)

元编程库 (C++11)

诊断库

通用实用工具库

字符串库

容器库

迭代器库

范围库 (C++20)

算法库

数值库

本地化库

输入/输出库

文件系统库 (C++17)

正则表达式库 (C++11)

并发支持库 (C++11)

执行支持库 (C++26)

技术规范

符号索引

外部库

 

C++ 命名要求

基本 默认可构造 可移动构造 (C++11) 可复制构造 可复制赋值 可移动赋值 (C++11) 可析构 类型属性 标量类型 POD 类型 可平凡复制 (C++11) 平凡类型 (C++11) 标准布局类型 (C++11)   隐式生命周期类型 库级 布尔可测试 可等式比较 可小于比较 可交换 可值交换 (C++11) 可空指针 (C++11) 哈希 (C++11) 分配器 函数对象 可调用 谓词 二元谓词 比较器

容器 容器 可逆容器 分配器感知容器 序列容器 连续容器 (C++17) 关联容器 无序关联容器 (C++11)   容器元素 默认可插入 (C++11) 可复制插入 (C++11) 可移动插入 (C++11) 可就地构造 (C++11) 可擦除 (C++11) 迭代器 旧式迭代器 旧式输入迭代器 旧式输出迭代器 旧式前向迭代器 旧式双向迭代器 旧式随机访问迭代器 旧式连续迭代器 (C++17) 常量表达式迭代器 (C++20) 流 I/O 格式化输入函数 非格式化输入函数 格式化输出函数 非格式化输出函数 格式化程序 基本格式化程序 (C++20) 格式化程序 (C++20)

随机数 种子序列 (C++11) 随机数生成器 (C++11) 随机数分布 (C++11) 均匀随机位生成器 (C++11) 随机数生成器适配器 (C++11) 并发 基本可锁定 (C++11) 可锁定 (C++11) 定时可锁定 (C++11) 共享可锁定 (C++14) 共享定时可锁定 (C++14) 互斥量 (C++11) 定时互斥量 (C++11) 共享互斥量 (C++17) 共享定时互斥量 (C++14) 范围 范围适配器对象 (C++20) 范围适配器闭包对象 (C++20) 多维视图 布局映射 (C++23) 布局映射策略 (C++23) 访问器策略 (C++23) 其他 字符特征 正则表达式特征 (C++11)   位掩码类型 文字类型 (C++11) 数值类型 一元类型特征 (C++11) 二元类型特征 (C++11) 转换特征 (C++11) 时钟 (C++11) 平凡时钟 (C++11)

 

一个 AssociativeContainer 是一个有序的 Container，它提供了基于键快速查找对象的机制。

关联容器支持唯一键，如果它最多可以包含每个键的一个元素。否则，它支持等效键。

要求

图例
X	一个关联容器类
T	X 的元素类型
A	X 的分配器类型：如果存在 X::allocator_type，则为 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 的元素的 旧式输入迭代器
[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	键
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	比较器	可复制构造
value_compare	与 key_compare 相同（适用于 std::set 和 std::multiset） 由第一个组件（即 Key）诱导的对排序关系（适用于 std::map 和 std::multimap）	二元谓词
node_type	节点句柄类模板的特化，其公共嵌套类型与 X 中的对应类型相同。

成员函数和运算符

表达式	结果	前提条件	效果	返回	复杂度
X(c)			构造一个空容器。 使用 c 的副本作为比较对象		常量
X u = X(); X u;		key_compare 满足 可默认构造 需求	构造一个空容器。 使用 Compare() 作为比较对象		常量
X(i, j, c)		value_type 是 可就地构造 到 X 中，来自 *i	构造一个空容器并将范围 [i, j) 中的元素插入到其中；使用 c 作为比较对象		N·log(N) 通常，其中 N 的值为 std::distance(i, j)；如果 [i, j) 相对于 value_comp() 排序，则为线性
X(i, j)		key_compare 满足 可默认构造 需求。 value_type 是 可就地构造 到 X 中，来自 *i	构造一个空容器并将范围 [i, j) 中的元素插入到其中；使用 Compare() 作为比较对象
X(from_range, rg, c) (自 C++23 起)		value_type 是 可就地构造 到 X 中，来自 *ranges::begin(rg)	构造一个空容器并将 rg 中的每个元素插入到其中。 使用 c 作为比较对象		N·log(N) 通常，其中 N 的值为 ranges::distance(rg)；如果 rg 相对于 value_comp() 排序，则为线性
X(from_range, rg) (自 C++23 起)		key_compare 满足 可默认构造 需求。 value_type 是 可就地构造 到 X 中，来自 *ranges::begin(rg)	构造一个空容器并将 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<   迭代器,   bool>	value_type 是 可就地构造 到 X 中，来自 args	仅当容器中没有与 t 的键等效的键的元素时，才插入一个使用 std::forward<Args>(args)... 构造的 value_type 对象 t	返回的 pair 的 bool 组件仅当插入发生时为 true，并且 pair 的迭代器组件指向与 t 的键等效的键的元素	对数
a_eq.emplace(args)	迭代器	value_type 是 可就地构造 到 X 中，来自 args	插入一个使用 std::forward<Args>(args)... 构造的 value_type 对象 t。 如果 a_eq 中存在包含与 t 等效的元素的范围，则 t 将插入该范围的末尾	指向新插入元素的迭代器	对数
a.emplace_hint(p, args)	迭代器		等同于 a.emplace(   std::forward<Args>(args)...)，除了元素插入尽可能靠近 p 之前的的位置	指向具有与新插入元素等效的键的元素的迭代器	通常情况下是对数，但如果元素插入到 p 之前，则是摊销常数
a_uniq.insert(t)	std::pair<   迭代器,   bool>	如果 t 是一个非 const 右值，则 value_type 是 可移动插入 到 X 中；否则，value_type 是 可复制插入 到 X 中	仅当容器中没有与 t 的键等效的键的元素时，才插入 t	返回的 pair 的 bool 成分仅当插入发生时才为 true，并且该 pair 的 iterator 成分指向与 t 的键等效的元素。	对数
a_eq.insert(t)	迭代器	如果 t 是一个非 const 右值，则 value_type 是 可移动插入 到 X 中；否则，value_type 是 可复制插入 到 X 中	插入 t 并返回指向新插入元素的迭代器。如果在 a_eq 中存在包含与 t 等效的元素的范围，则 t 将插入到该范围的末尾。		对数
a.insert(p, t)	迭代器	如果 t 是一个非 const 右值，则 value_type 是 可移动插入 到 X 中；否则，value_type 是 可复制插入 到 X 中	仅当在具有唯一键的容器中不存在与 t 的键等效的元素时，才插入 t；在具有等效键的容器中始终插入 t。t 将尽可能靠近 p 之前的那个位置插入。	指向与 t 的键等效的元素的迭代器。	一般情况下是对数级的，但如果 t 插入到 p 之前，则为均摊常数级。
a.insert(i, j)	void	value_type 是 EmplaceConstructible 到 X 中，来自 *i。i 和 j 都不是 a 中的迭代器。	仅当在具有唯一键的容器中不存在与该元素的键等效的元素时，才插入 [i, j) 范围内的每个元素；在具有等效键的容器中始终插入该元素。		N·log(a.size() + N)，其中 N 的值为 std::distance(i, j)
a.insert_range(rg) (自 C++23 起)	void	value_type 是 EmplaceConstructible 到 X 中，来自 *ranges::begin(rg)。 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)	迭代器	nh 为空，或者 a_eq.get_allocator() == nh.get_allocator() 为 true	如果 nh 为空，则不生效并返回 a_eq.end()。否则，插入由 nh 拥有的元素并返回指向新插入元素的迭代器。如果在 a_eq 中存在包含与 nh.key() 的键等效的元素的范围，则该元素将插入到该范围的末尾。确保：nh 为空。		对数
a.insert(p, nh)	迭代器	nh 为空，或者 a.get_allocator() == nh.get_allocator() 为 true	如果 nh 为空，则不生效并返回 a.end()。否则，仅当在具有唯一键的容器中不存在与 nh.key() 的键等效的元素时，才插入由 nh 拥有的元素；在具有等效键的容器中始终插入由 nh 拥有的元素。该元素将尽可能靠近 p 之前的那个位置插入。确保：如果插入成功，则 nh 为空；如果插入失败，则 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)	迭代器		擦除由 q 指向的元素	指向擦除元素之前紧随 q 的元素的迭代器。如果不存在这样的元素，则返回 a.end()	均摊常数级。
a.erase(r)	迭代器		擦除由 r 指向的元素	指向擦除元素之前紧随 r 的元素的迭代器。如果不存在这样的元素，则返回 a.end()	均摊常数级。
a.erase(q1, q2)	迭代器		擦除范围内的所有元素 [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>; std::pair<   const_iterator,   const_iterator> for constant b		等同于 return   std::make_pair(     b.lower_bound(k),     b.upper_bound(k));		对数
a_tran.equal_range(ke)	std::pair<   迭代器,   iterator>; std::pair<   const_iterator,   const_iterator> for constant 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 成立。

标准库中的关联容器

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

缺陷报告

以下行为变更的缺陷报告被追溯应用到之前发布的 C++ 标准。

DR	应用于	已发布的行为	正确行为
LWG 354	C++98	lower_bound 和 upper_bound 没有 在找不到元素的情况下返回末尾迭代器	在这种情况下，它们返回末尾 迭代器
LWG 589	C++98	i 和 j 所指代的元素 类型为 X::value_type	这些元素被隐式 转换为 X::value_type