C++ 命名要求： AssociativeContainer

 

C++

编译器支持

独立和宿主式

语言

标准库

标准库头文件

命名要求

特性测试宏 (C++20)

语言支持库

概念库 (C++20)

诊断库

内存管理库

元编程库 (C++11)

通用工具库

容器库

迭代器库

范围库 (C++20)

算法库

字符串库

文本处理库

数值库

日期和时间库

输入/输出库

文件系统库 (C++17)

并发支持库 (C++11)

执行控制库 (C++26)

技术规范

符号索引

外部库

 

C++ 命名要求

基本 DefaultConstructible MoveConstructible (C++11) CopyConstructible CopyAssignable MoveAssignable (C++11) Destructible 类型属性 ScalarType PODType TriviallyCopyable (C++11) TrivialType (C++11) StandardLayoutType (C++11)   ImplicitLifetimeType 库范围 BooleanTestable EqualityComparable LessThanComparable Swappable ValueSwappable (C++11) NullablePointer (C++11) Hash (C++11) Allocator FunctionObject Callable Predicate BinaryPredicate Compare

Container Container ReversibleContainer AllocatorAwareContainer SequenceContainer ContiguousContainer (C++17) AssociativeContainer UnorderedAssociativeContainer (C++11)   容器元素 DefaultInsertable (C++11) CopyInsertable (C++11) MoveInsertable (C++11) EmplaceConstructible (C++11) Erasable (C++11) Iterator LegacyIterator LegacyInputIterator LegacyOutputIterator LegacyForwardIterator LegacyBidirectionalIterator LegacyRandomAccessIterator LegacyContiguousIterator (C++17) ConstexprIterator (C++20) 流 I/O FormattedInputFunction UnformattedInputFunction FormattedOutputFunction UnformattedOutputFunction 格式化器 BasicFormatter (C++20) Formatter (C++20)

随机数 SeedSequence (C++11) RandomNumberEngine (C++11) RandomNumberDistribution (C++11) UniformRandomBitGenerator (C++11) RandomNumberEngineAdaptor (C++11) 并发 BasicLockable (C++11) Lockable (C++11) TimedLockable (C++11) SharedLockable (C++14) SharedTimedLockable (C++14) Mutex (C++11) TimedMutex (C++11) SharedMutex (C++17) SharedTimedMutex (C++14) 范围 RangeAdaptorObject (C++20) RangeAdaptorClosureObject (C++20) 多维视图 LayoutMapping (C++23) LayoutMappingPolicy (C++23) AccessorPolicy (C++23) 其他 CharTraits RegexTraits (C++11)   BitmaskType LiteralType (C++11) NumericType UnaryTypeTrait (C++11) BinaryTypeTrait (C++11) TransformationTrait (C++11) Clock (C++11) TrivialClock (C++11)

 

一个 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 的元素的 LegacyInputIterator
[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<   迭代器,   bool>	value_type 可从 args 就地构造 到 X 中	当且仅当容器中没有元素的键与 t 的键等效时，才插入使用 std::forward<Args>(args)... 构造的 value_type 对象 t	返回的对的 bool 组件是 true 当且仅当发生插入时，并且该对的迭代器组件指向键与 t 的键等效的元素	对数
a_eq.emplace(args)	迭代器	value_type 可从 args 就地构造 到 X 中	插入使用 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	返回的对的 bool 组件是 true 当且仅当发生插入时，并且该对的 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 可从 *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 中的元素的键等效时，才插入 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> 对于常量 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> 对于常量 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++ 标准。

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