C++ 具名要求：关联容器(AssociativeContainer)
来自cppreference.com
关联容器(AssociativeContainer) 是提供基于键的快速对象查找的容器(Container) 。
对于每个键都只能包含最多一个元素的关联容器支持唯一键，其他关联容器支持等价键。
目录 |
[编辑]要求
Legend | |
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) |
[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 是 a 中的元素 e 的键 |
| ku | 使得 a 以 !c(ku, x) 划分的值，其中 x 是 a 中的元素 e 的键 |
| ku | 使得 a 以 c(x, ke) 和 !c(ke, x) 划分的值，其中 c(x, ke) 意味着 !c(ke, x)，并且 x 是 a 中的元素 e 的键 |
| kx (C++23 起) | 满足以下条件的值：
|
| m | 具有可转换到 A 的类型的分配器 |
| nh | X::node_type 类型的非 const 右值 |
满足以下条件的类型 X 满足关联容器(AssociativeContainer) ：
- 类型
X满足容器(Container) (C++11 前)知分配器容器(AllocatorAwareContainer) (C++11 起), - 它以类型
Key和在Key类型的元素上引入严格弱序的排序关系的Compare参数化- 另外，std::map 和 std::multimap 会将一个任意映射类型
T关联到Key。 Compare类型的对象被称为X类型的容器的比较对象。
- 另外，std::map 和 std::multimap 会将一个任意映射类型
- 下列表达式必须对所有关联容器有效并具有所指定的效果：
[编辑]类型
| 名称 | 类型 | 要求 |
|---|---|---|
key_type | Key | |
mapped_type | T（仅限 std::map 和 std::multimap） | |
value_type |
| 从 X可擦除(Erasable) |
key_compare | Compare | 可复制构造(CopyConstructible) |
value_compare |
| 二元谓词(BinaryPredicate) |
node_type | 使得公开嵌套类型与 X 中对应类型相同的节点句柄类模板特化 |
[编辑]成员函数与运算符
| 表达式 | 结果 | 前条件 | 效果 | 返回 | 复杂度 |
|---|---|---|---|---|---|
| X(c) | 构造空容器。以 c 的副本作为比较对象 | 常数 | |||
| X u = X(); X u; | X::key_compare 满足可默认构造(DefaultConstructible) 的规定 | 构造空容器。以 Compare() 作为比较对象 | 常数 | ||
| X(i, j, c) | X::value_type 从 *i可就位构造(EmplaceConstructible) 到 X | 构造空容器并向其中插入范围 [i, j) 中的元素；以 c 作为比较对象 | 通常是 N·log(N)，其中 N 的值为 std::distance(i, j)；或者在 [i, j) 根据 value_comp() 有序时成线性 | ||
| X(i, j) | X::key_compare 满足可默认构造(DefaultConstructible) 的规定。X::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 | 构造 a 时提供的比较对象 | 常数 | ||
| b.value_comp() | X::value_compare | 从比较对象构造出的 value_compare 类型的对象 | 常数 | ||
| a_uniq.emplace(args) | std::pair< iterator, bool> | value_type 以 args可就位构造(EmplaceConstructible) 到 X | 当且仅当容器中不存在元素带有与 t 的键等价的键时，插入一个以 std::forward<Args>(args)... 构造的 value_type 对象 t | 当且仅当发生插入时，所返回对偶的 bool 组分为 true，而对偶的迭代器组分指向带有与 t 的键等价的键的元素 | 对数 |
| a_eq.emplace(args) | iterator | value_type 以 args可就位构造(EmplaceConstructible) 到 X | 插入一个以 std::forward<Args>(args)... 构造的 value_type 对象 t。如果 a_eq 中存在包含等价于 t 的元素范围，则 t 被插入到这个范围末尾 | 指向新插入元素的迭代器 | 对数 |
| a.emplace_hint(p, args) | iterator | 等价于 a.emplace( | 指向带有与新插入元素等价的键的元素的迭代器 | 通常是对数，但当于紧接 p 之前插入元素时是均摊常数 | |
| a_uniq.insert(t) | std::pair< iterator, bool> | 如果 t 是非 const 右值，则 value_type可移动插入(MoveInsertable) 到 X；否则 value_type可复制插入(CopyInsertable) 到 X | 当且仅当容器中不存在带有与 t 的键等价的键的元素时，插入 t | 当且仅当发生插入时，所返回对偶的 bool 组分为 true，而对偶的 iterator 组分指向带有与 t 的键等价的键的元素 | 对数 |
| a_eq.insert(t) | iterator | 如果 t 是非 const 右值，则 value_type可移动插入(MoveInsertable) 到 X；否则 value_type可复制插入(CopyInsertable) 到 X | 插入 t 并返回指向新插入元素的迭代器。如果 a_eq 中存在包含等价于 t 的元素的范围，则 t 被插入到这个范围末尾 | 对数 | |
| a.insert(p, t) | iterator | 如果 t 是非 const 右值，则 value_type可移动插入(MoveInsertable) 到 X；否则 value_type可复制插入(CopyInsertable) 到 X | 当且仅当带有唯一键的容器中不存在带有与 t 的键等价的键的元素时，插入 t；带有等价键的容器总是插入 t。t 被插入到尽可能靠近紧接 p 之前的位置 | 指向带有与 t 的键等价的键的元素的迭代器 | 通常是对数，但当于紧接 p 之前插入 t 时是均摊常数 |
| a.insert(i, j) | void | value_type 以 *i可就位构造(EmplaceConstructible) 到 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)可就位构造(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 为空时无效果。否则，当且仅当容器中不存在具有与 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 为空时无效果并返回 a_eq.end()。否则，插入 nh 拥有的元素并返回指向新插入元素的迭代器。如果 a_eq 中存在包含具有等价于 nh.key() 的键的元素的范围，则在这个范围末尾插入元素。保证：nh 为空 | 对数 | |
| a.insert(p, nh) | iterator | nh 为空，或者 a.get_allocator() | 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 | 移除容器中第一个带有键 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) | iterator | 擦除 q 指向的元素 | 指向元素被擦除前紧跟 q 之后的元素的迭代器。若不存在这种元素则返回 a.end() | 均摊常数 | |
| a.erase(r) | iterator | 擦除 r 指向的元素 | 指向元素被擦除前紧跟 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; 对常量 b 为 const_iterator | 指向带有等价于 k 的键的元素的迭代器，或未找到这种元素时为 b.end() | 对数 | ||
| a_tran.find(ke) | iterator; 对常量 a_tran 为 const_iterator | 指向带有键 r 使得 !c(r, ke)&& | 对数 | ||
| b.count(k) | size_type | 带有等价于 k 的键的元素数量 | log(b.size()) + b.count(k) | ||
| a_tran.count(ke) | size_type | 带有键 r 使得 !c(r, ke)&& | log(a_tran.size()) + a_tran.count(ke) | ||
| b.contains(k) | bool | return b.find(k)!= b.end(); | |||
| a_tran.contains(ke) | bool | return | |||
| 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, iterator>; 对于常量 b 为 std::pair< | 等价于： return | 对数 | ||
| a_tran.equal_range(ke) | std::pair< iterator, iterator>; 对于常量 a_tran 为 std::pair< | 等价于： return | 对数 |
[编辑]迭代器
关联容器的迭代器满足老式双向迭代器(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 也成立。
| 本节未完成 原因：Finish requirements. |
[编辑]标准库
下列标准库容器均满足关联容器(AssociativeContainer) ：
| 唯一键的集合，按照键排序 (类模板) | |
| 键的集合，按照键排序 (类模板) | |
| 键值对的集合，按照键排序，键是唯一的 (类模板) | |
| 键值对的集合，按照键排序 (类模板) |
[编辑]缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
| 缺陷报告 | 应用于 | 出版时的行为 | 正确行为 |
|---|---|---|---|
| LWG 354 | C++98 | lower_bound 和 upper_bound 在没找到元素时不会返回尾迭代器 | 此时它们会返回尾迭代器 |
| LWG 589 | C++98 | i 和 j 指代的元素具有 X::value_type 类型 | 那些元素可以隐式转换到 X::value_type |
