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 或 const X 的值，当类型 X::key_compare::is_transparent 存在时
i , j 指向可隐式转换为 X::value_type 元素的 LegacyInputIterator s
[ 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 的非常量右值

类型 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 可擦除 自 X
key_compare Compare 可复制构造
value_compare 二元谓词
node_type 节点句柄类模板 的特化，其公共嵌套类型与 X 中的对应类型相同。

成员函数与运算符

（注：根据要求，所有HTML标签、属性及 标签内的C++代码均保持原样未翻译） （说明：根据要求，所有HTML标签、属性及 标签内的C++代码（包括insert/begin/end等术语）均保持原样未翻译，仅对非代码部分进行了简体中文转换。由于原文中除代码外无其他可翻译文本内容，故输出保持原结构不变）
表达式 结果 前置条件 效果 返回值 复杂度
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 可 EmplaceConstructible 到 X 中（通过 * i 构造） 构造空容器并插入区间 [ 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 可 EmplaceConstructible 到 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 需满足 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 到 X 的 EmplaceConstructible 要求 当且仅当容器中不存在与 t 的键等价元素时，插入一个通过 std:: forward < Args > ( args ) ... 构造的 value_type 对象 t 返回对的 bool 分量当且仅当插入发生时值为 true ，对的迭代器分量指向与 t 的键等价的元素 对数复杂度
a_eq. emplace ( args ) iterator value_type 需满足从 args 到 X 的 EmplaceConstructible 要求 插入一个通过 std:: forward < Args > ( args ) ... 构造的 value_type 对象 t 。若 a_eq 中存在与 t 等价的元素范围，则将 t 插入到该范围的末尾 指向新插入元素的迭代器 对数复杂度
a. emplace_hint ( p, args ) iterator 等价于

a. emplace (
std:: forward < Args > ( args ) ... ) ， 不同之处在于元素会尽可能插入到刚好位于 p 之前的位置

指向与新增元素键值等价的元素的迭代器 通常为对数复杂度，若元素恰好插入在 p 之前则为均摊常数复杂度
a_uniq. insert ( t ) std:: pair <
iterator,
bool > 		若 t 是非常量右值，则 value_type 需满足 MoveInsertable 要求；否则 value_type 需满足 CopyInsertable 要求 当且仅当容器中不存在与 t 的键等效的元素时，插入 t 返回对的 bool 分量在且仅在插入发生时返回 true ，对的 iterator 分量指向与 t 的键等效的元素 对数复杂度
a_eq. insert ( t ) iterator 若 t 是非常量右值，则要求 value_type 满足 MoveInsertable 要求；否则要求 value_type 满足 CopyInsertable 要求 插入 t 并返回指向新插入元素的迭代器。若 a_eq 中已存在与 t 等价的元素范围，则将 t 插入到该范围的末尾 对数复杂度
a. insert ( p, t ) iterator 若 t 是非常量右值，则要求 value_type 满足 MoveInsertable 要求；否则要求 value_type 满足 CopyInsertable 要求 在具有唯一键的容器中，当且仅当不存在与 t 的键等效的元素时插入 t ；在具有等价键的容器中始终插入 t 。将 t 插入到尽可能接近 p 之前的位置 指向具有与 t 的键等效的元素的迭代器 通常为对数复杂度，但若 t 正好插入在 p 之前则为均摊常数复杂度
a. insert ( i, j ) void value_type 需满足从 * i 到 X 的 EmplaceConstructible 要求。 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 ) 可 EmplaceConstructible 到 X 中。 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 ) iterator nh 为空或

a_eq. get_allocator ( )
==
nh. get_allocator ( ) 为 true

若 nh 为空，则无效果并返回 a_eq. end ( ) 。否则，插入由 nh 拥有的元素，并返回指向新插入元素的迭代器。若 a_eq 中存在键等价于 nh. key ( ) 的元素范围，则该元素将插入到该范围的末尾。确保： nh 变为空 对数复杂度
a. insert ( p, nh ) iterator nh 为空或

a. get_allocator ( )
==
nh. get_allocator ( ) 为 true

若 nh 为空，则无效果并返回 a. end ( ) 。否则，当且仅当在具有唯一键的容器中不存在与 nh. key ( ) 等价的键时，插入由 nh 拥有的元素；在具有等价键的容器中始终插入由 nh 拥有的元素。该元素被插入到尽可能接近 p 之前的位置。确保：若插入成功则 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 移除容器中首个满足 ! c ( r, kx ) && ! c ( kx, r ) 条件且键为 r 的元素 若找到元素则返回拥有该元素的 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 ) iterator 删除由 q 指向的元素 返回指向被删除元素前一个紧邻元素的迭代器。若该元素不存在，则返回 a. end ( ) 摊还常数复杂度
a. erase ( r ) iterator 删除由 r 指向的元素 返回指向被删除元素前一个元素的迭代器。若该元素不存在，则返回 a. end ( ) 摊还常数复杂度
a. erase ( q1, q2 ) iterator 删除范围
[ 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 ； const_iterator 用于常量版本 b 返回指向键等价于 k 的元素的迭代器，若未找到此类元素则返回 b. end ( ) 对数复杂度
a_tran. find ( ke ) iterator ； const_iterator 用于常量 a_tran 指向满足条件的元素的迭代器：该元素的键 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 ； 常量版本为 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 ； 常量版本为 const_iterator 返回指向首个键大于 k 的元素的迭代器，若未找到此类元素则返回 b. end ( ) 对数复杂度
a_tran. upper_bound ( ku ) iterator ； const_iterator 用于常量 a_tran 指向第一个键值为 r 且满足 c ( ku, r ) 条件的元素的迭代器，若未找到此类元素则返回 a_tran. end ( ) 对数复杂度
b. equal_range ( k ) std:: pair <
iterator,
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,
iterator > ;

std:: pair <
const_iterator,
const_iterator > 对于常量 a_tran

等价于：

return
std:: make_pair (
a_tran. lower_bound ( ke ) ,
a_tran. upper_bound ( ke ) ) ;

对数复杂度

Iterators

关联容器的迭代器满足 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++ 标准。

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