Namespaces
Variants

C++ named requirements: AssociativeContainer

From cppreference.net
C++
C++ named requirements

一个 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 s
[ i , j ) 有效范围
rg
(since 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
(since 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 满足 容器 (C++11 前) 分配器感知容器 (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 可从 X 中 擦除
key_compare Compare 可复制构造
value_compare 二元谓词
node_type 节点句柄类模板 的特化，其公共嵌套类型与 X 中的对应类型相同。

成员函数与运算符

表达式 结果 前置条件 效果 返回值 复杂度
X ( c ) 构造一个空容器。使用 c 的副本作为比较对象 常数
X u = X ( ) ;
X u ; 		key_compare 满足 DefaultConstructible 要求 构造一个空容器。使用 Compare ( ) 作为比较对象 常数
X ( i, j, c ) value_type 可从 * i EmplaceConstructible 到 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 EmplaceConstructible 到 X 构造一个空容器并将范围 [ i , j ) 中的元素插入其中；使用 Compare ( ) 作为比较对象
X ( from_range, rg, c )
(自 C++23 起) 		value_type 可从 * ranges:: begin ( rg ) EmplaceConstructible 到 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 ) EmplaceConstructible 到 X 构造一个空容器并将 rg 中的每个元素插入其中。使用 Compare ( ) 作为比较对象
X ( il, c ) X ( il. begin ( ) , il. end ( ) , c )
X ( il ) X ( il. begin ( ) , il. end ( ) )
a = il X & value_type 可 CopyInsertable 到 X 且 CopyAssignable 将范围 [ 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 <
iterator,
bool > 		value_type 可从 args EmplaceConstructible 到 X

迭代器

关联容器的迭代器满足 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 要求：

唯一键的集合，按键排序
(类模板)
键的集合，按键排序
(类模板)
键值对的集合，按键排序，键唯一
(类模板)
键值对的集合，按键排序
(类模板)

缺陷报告

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

缺陷报告 适用标准 发布时行为 正确行为
LWG 354 C++98 lower_bound 和 upper_bound 在未找到元素时
未返回结束迭代器 		在此情况下返回结束
迭代器
LWG 589 C++98 i 和 j 所引用的元素
具有类型 X::value_type 		元素可隐式
转换为 X::value_type