C++ 具名要求：关联容器 (AssociativeContainer)
来自cppreference.com
关联容器 (AssociativeContainer) 是提供基于键的快速对象查找的容器 (Container) 。
要求
凡例 | |
X
|
容器类型 |
a
|
X 类型的值
|
a2
|
其结点句柄与 X 兼容的 Y 类型的值
|
b
|
X 类型的可能为 const 的值
|
u
|
任意变量名 |
a_uniq
|
（当 X 支持唯一键时）X 类型的值
|
a_eq
|
（当 X 支持多重键时）X 类型的值
|
a_tran
|
（当 X::key_compare::is_transparent 存在时）X 类型的可能为 const 的值
|
i, j
|
老式输入迭代器 (LegacyInputIterator) ，指代有效范围并指向可隐式转换到 X::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 的值
|
kl
|
一个值，使得 a 依据 c(r,kl) 已划分，其中 r 是 e 的键且 e 在 a 中
|
ku
|
一个值，使得 a 依据 !c(ku, r) 已划分
|
ke
|
一个值，使得 a 依据 c(r, ke) 与 !c(ke, r) 已划分，其中 c(r, ke) 隐含 !c(ke, r)
|
A
|
X 所用的存储分配器，或 std::allocator_type<X::value_type>
|
m
|
分配器，其类型可转换为 A
|
nh
|
X::node_type 类型的非 const 右值
|
| 表达式 | 返回类型 | 前条件/要求 | 后条件/效果 | 复杂度 |
|---|---|---|---|---|
| X::key_type | Key |
Key 可析构 (Destructible) |
编译时 | |
| X::key_compare | Compare |
编译时 | ||
| X::value_compare | 满足二元谓词 (BinaryPredicate) 的类型 | 对于 std::set 和 std::multiset 为 key_compare； 对于 std::map 和 std::multimap 为 Key 上的顺序关系 |
编译时 | |
| X(c), X a(c); | key_compare 可复制构造 (CopyConstructible) | 以 c 的副本为 key_comp 构造空容器 |
常数 | |
| X(), X a; | key_compare 可复制构造 (CopyConstructible) | 以 Compare() 为 key_comp 构造空容器 |
常数 | |
| X(i, j, c), X a(i, j, c); | key_compare 可复制构造 (CopyConstructible) 且 value_type 从 *i 可就位构造 (EmplaceConstructible) 到 X | 以 c 的副本为 key_comp 构造空容器并插入来自范围 [i; j) 的所有元素 |
通常为 N log N，或若 [i, j) 已排序则为 N（其中 N 是 std::distance(i, j)）
| |
| X(i, j), X a(i, j); | key_compare 可复制构造 (CopyConstructible) 且 value_type 从 *i 可就位构造 (EmplaceConstructible) 到 X | 以 Compare() 为 key_comp 构造空容器并插入来自范围 [i; j) 的所有元素 |
通常为 N log N，或若 [i, j) 已按照 value_comp() 排序则为 N（其中 N 是 std::distance(i, j)）
| |
| X(il); | 等价于 X(il.begin(), il.end()); | 等价于 X(il.begin(), il.end()); | ||
| a = il | X& | T 可复制插入 (CopyInsertable) 到 X 而且亦可复制赋值 (CopyAssignable) |
将范围 [il.begin(), il.end()) 赋值到 a。 a 的未被赋值元素均被销毁 |
通常为 N log N，或若 [il.begin(), il.end()) 已按照 value_comp() 排序则为 N（其中 N 是 il.size() + a.size()）
|
| a.key_comp() | X::key_compare | 返回构造 a 所用的比较对象。 |
常数 | |
| a.value_comp() | X::value_compare | 返回在比较对象外构造的 X::value_compare 类型的对象。 | 常数 |
作为 std::map 或 std::multimap 的关联容器 X 额外支持表达式 X::mapped_type，它以 T 为返回的类型（但要求 T 可析构 (Destructible) ），及编译时复杂度。
| 本节未完成 原因：完成要求。 |
标准库中的关联容器
| 唯一键的集合，按照键排序 (类模板) | |
| 键的集合，按照键排序 (类模板) | |
| 键值对的集合，按照键排序，键是唯一的 (类模板) | |
| 键值对的集合，按照键排序 (类模板) |