std::flat_set
来自 cppreference.com
| 定义在头文件 <flat_set> 中 |
||
| template< class Key, |
(自 C++23 起) | |
flat 集合是一个 容器适配器，它提供了一个关联容器的功能，该容器存储类型为 Key 的唯一对象的排序集合。排序使用键比较函数 Compare 进行。
类模板 flat_set 充当对作为类型 KeyContainer 的对象传递的底层排序容器的包装器。
标准库在使用 Compare 要求的地方，唯一性是使用等价关系确定的。非正式地说，两个对象 a 和 b 被认为是等价的，如果它们都不比另一个小：!comp(a, b) && !comp(b, a).
std::flat_set 满足 Container、ReversibleContainer、可选容器要求 以及 AssociativeContainer 的所有要求（包括对数搜索复杂度），除了
- 与节点相关的要求不适用，
- 迭代器失效要求不同，
- 插入和删除操作的复杂度是线性的。
flat 集合支持大多数 AssociativeContainer 的使用唯一键的操作。
内容 |
[编辑] 迭代器失效
| 本节内容不完整 |
[编辑] 模板参数
| Key | - | 存储元素的类型。如果 Key 与 KeyContainer::value_type 不是同一类型，则程序格式错误。 |
| Compare | - | 一个 Compare 类型，提供严格的弱排序。 |
| KeyContainer | - | 存储元素的底层 SequenceContainer 的类型。此类容器的迭代器应满足 LegacyRandomAccessIterator 或建模 random_access_iterator。标准容器 std::vector 和 std::deque 满足这些要求。 |
[编辑] 成员类型
| 成员类型 | 定义 |
container_type
|
KeyContainer |
key_type
|
Key |
value_type
|
Key |
key_compare
|
Compare |
value_compare
|
Compare |
reference
|
value_type& |
const_reference
|
const value_type& |
size_type
|
typename KeyContainer::size_type |
difference_type
|
typename KeyContainer::difference_type |
iterator
|
实现定义的 LegacyRandomAccessIterator 和 random_access_iterator 到 value_type |
const_iterator
|
实现定义的 LegacyRandomAccessIterator 和 random_access_iterator 到 const value_type |
reverse_iterator
|
std::reverse_iterator<iterator> |
const_reverse_iterator
|
std::reverse_iterator<const_iterator> |
[编辑] 成员对象
| 成员名称 | 定义 |
c (私有) |
container_type 的底层容器(仅供说明的成员对象*) |
compare (私有) |
类型为 key_compare 的比较函数对象(仅供说明的成员对象*) |
[编辑] 成员函数
构造 flat_set(公有成员函数) | |
| (析构函数) (隐式声明) |
销毁容器适配器中的每个元素 (公有成员函数) |
| 将值分配给容器适配器 (公有成员函数) | |
迭代器 | |
| 返回指向开头的迭代器 (公有成员函数) | |
| 返回指向结尾的迭代器 (公有成员函数) | |
| 返回指向开头的反向迭代器 (公有成员函数) | |
| 返回指向结尾的反向迭代器 (公有成员函数) | |
容量 | |
| 检查容器适配器是否为空 (公有成员函数) | |
| 返回元素数量 (公有成员函数) | |
| 返回元素的最大可能数量 (公有成员函数) | |
修改器 | |
| 就地构造元素 (公有成员函数) | |
| 使用提示就地构造元素 (公有成员函数) | |
| 插入元素 (公有成员函数) | |
| 插入一系列元素 (公有成员函数) | |
| 提取底层容器 (公有成员函数) | |
| 替换底层容器 (公有成员函数) | |
| 删除元素 (公有成员函数) | |
| 交换内容 (公有成员函数) | |
| 清除内容 (公有成员函数) | |
查找 | |
| 查找具有特定键的元素 (公有成员函数) | |
| 返回与特定键匹配的元素数量 (公有成员函数) | |
| 检查容器是否包含具有特定键的元素 (公有成员函数) | |
| 返回指向第一个不小于给定键的元素的迭代器 (公有成员函数) | |
| 返回指向第一个大于给定键的元素的迭代器 (公有成员函数) | |
| 返回与特定键匹配的元素范围 (公有成员函数) | |
观察者 | |
| 返回比较键的函数 (公有成员函数) | |
返回比较类型为 value_type 的对象中的键的函数(公有成员函数) | |
[编辑] 非成员函数
| (C++23) |
按字典顺序比较两个 flat_set 的值(函数模板) |
| (C++23) |
专门化 std::swap 算法 (函数模板) |
| (C++23) |
删除所有满足特定条件的元素 (函数模板) |
[编辑] 辅助类
| 专门化 std::uses_allocator 类型特征 (类模板专门化) |
[编辑] 标签
| (C++23) |
表示范围中的元素已排序且唯一 (标签) |
[编辑] 推断指南
[编辑] 注释
成员类型 iterator 和 const_iterator 可能为相同类型的别名。这意味着使用这两个类型作为参数类型定义一对函数重载可能会违反 单一定义规则。由于 iterator 可转换为 const_iterator，因此可以使用具有 const_iterator 作为参数类型的单个函数来代替。
与其他标准 容器适配器 相比，flat set 的一些优点是
- 查找速度可能更快（即使搜索操作具有对数复杂度）。
- 迭代速度快得多：随机访问迭代器 而不是 双向迭代器。
- 对于小型对象，内存消耗更少（对于大型对象，如果 KeyContainer::shrink_to_fit() 可用）。
- 更好的缓存性能（取决于
KeyContainer，键存储在内存中连续的块中）。
flat set 的一些缺点是
- 非稳定迭代器（在插入和删除元素时，迭代器将失效）。
- 不可复制和不可移动的类型值不能存储。
- 更弱的异常安全性（在删除和插入元素时，复制/移动构造函数可能会抛出异常）。
- 插入和删除速度较慢（即线性），尤其对于不可移动的类型。
| 特性测试 宏 | 值 | Std | 特性 |
|---|---|---|---|
__cpp_lib_flat_set |
202207L | (C++23) | std::flat_set 和 std::flat_multiset |
[编辑] 示例
| 本节内容不完整 原因：没有示例 |
[编辑] 参见
| (C++23) |
使容器适应，提供由键排序的键集合 (类模板) |
| 由键排序的唯一键集合 (类模板) | |
| (C++11) |
由键哈希的唯一键集合 (类模板) |
