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
|
指代合法范围并指向可隐式转换到 X::value_type 的元素的输入迭代器 (InputIterator)
|
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
|
就 c(r,kl) 划分 a 的值，其中 r 是 e 的关键且 e 在 a 中
|
ku
|
就 !c(ku, r) 划分 a 的值
|
ke
|
就 c(r, ke) 与 !c(ke, r) 划分 a 的值，其中 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 的关联容器 (AssociativeContainer) X 额外支持表达式 X::mapped_type ，它拥有 T 的返回类型，并要求 T 可析构 (Destructible) ，及编译时复杂度。
| 本节未完成 原因：完成要求。 |
[编辑] 标准库中的关联容器 (AssociativeContainer)
| 唯一键的集合，按照键排序 (类模板) | |
| 键的集合，按照键排序 (类模板) | |
| 键值对的集合，按照键排序，键是唯一的 (类模板) | |
| 键值对的集合，按照键排序 (类模板) |
