std::flat_set(C++23)
什么是 std::flat_set
std::flat_set 是 C++23 引入的容器适配器,提供与 std::set 相同的有序集合功能(元素唯一,自动排序),但底层使用排序的连续容器(默认 std::vector)存储元素,而不是红黑树。和 flat_map 的设计思路一致——牺牲插入/删除性能,换取更好的查找和遍历性能。
cpp
#include <flat_set>
std::flat_set<int> s = {3, 1, 4, 1, 5, 9};
// s 中元素: {1, 3, 4, 5, 9}(去重且排序)flat_set vs set vs unordered_set
| 特性 | std::flat_set | std::set | std::unordered_set |
|---|---|---|---|
| 底层结构 | 排序的 vector | 红黑树 | 哈希表 |
| 查找复杂度 | O(log n) | O(log n) | O(1) 平均 |
| 插入复杂度 | O(n) | O(log n) | O(1) 平均 |
| 删除复杂度 | O(n) | O(log n) | O(1) 平均 |
| 内存布局 | 连续 | 节点分散 | 桶 |
| 缓存友好 | 好 | 差 | 一般 |
| 迭代器稳定性 | 插入后失效 | 稳定 | 重哈希后失效 |
| 内存开销 | 低 | 高(节点指针) | 中 |
| 有序 | 是 | 是 | 否 |
基本示例
cpp
#include <iostream>
#include <flat_set>
#include <string>
#include <vector>
#include <algorithm>
// ============================
// 示例1:基本用法
// ============================
void basic_demo() {
// 初始化列表——自动排序去重
std::flat_set<int> s = {5, 3, 8, 1, 3, 9, 2, 5};
std::cout << "元素: ";
for (int v : s) std::cout << v << " ";
std::cout << std::endl; // 1 2 3 5 8 9
// 插入
auto [it, inserted] = s.insert(4);
std::cout << "插入 4: " << std::boolalpha << inserted << std::endl; // true
auto [it2, inserted2] = s.insert(3);
std::cout << "插入 3: " << inserted2 << std::endl; // false(已存在)
// 查找
std::cout << "包含 5: " << s.contains(5) << std::endl; // true
std::cout << "包含 7: " << s.contains(7) << std::endl; // false
// 大小
std::cout << "大小: " << s.size() << std::endl;
}
// ============================
// 示例2:从已排序数据构造
// ============================
void sorted_demo() {
// 已排序且唯一的数据——用 sorted_unique 标签跳过排序
std::flat_set<int> s(std::sorted_unique,
std::vector<int>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
std::cout << "已排序构造: ";
for (int v : s) std::cout << v << " ";
std::cout << std::endl;
}
// ============================
// 示例3:字符串集合
// ============================
void string_demo() {
std::flat_set<std::string> fruits = {
"banana", "apple", "cherry", "date", "apple"
};
std::cout << "水果集合: ";
for (const auto& f : fruits) std::cout << f << " ";
std::cout << std::endl; // apple banana cherry date
// 范围查询
auto begin = fruits.lower_bound("b");
auto end = fruits.lower_bound("d");
std::cout << "b 到 d 之间: ";
for (auto it = begin; it != end; ++it) {
std::cout << *it << " ";
}
std::cout << std::endl; // banana cherry
}
// ============================
// 示例4:自定义比较器
// ============================
void custom_compare_demo() {
// 降序排列
std::flat_set<int, std::greater<>> desc_set = {1, 5, 3, 8, 2};
std::cout << "降序: ";
for (int v : desc_set) std::cout << v << " ";
std::cout << std::endl; // 8 5 3 2 1
// 不区分大小写的字符串集合
auto case_insensitive = [](const std::string& a, const std::string& b) {
return std::lexicographical_compare(
a.begin(), a.end(), b.begin(), b.end(),
[](char ca, char cb) { return std::tolower(ca) < std::tolower(cb); }
);
};
std::flat_set<std::string, decltype(case_insensitive)> ci_set(case_insensitive);
ci_set.insert("Hello");
ci_set.insert("hello"); // 不会插入(视为重复)
ci_set.insert("WORLD");
std::cout << "不区分大小写: ";
for (const auto& s : ci_set) std::cout << s << " ";
std::cout << std::endl;
}
// ============================
// 示例5:访问底层容器
// ============================
void underlying_demo() {
std::flat_set<int> s = {5, 3, 1, 4, 2};
// 直接获取底层的排序 vector
const auto& underlying = s.keys();
std::cout << "底层 vector: ";
for (int v : underlying) std::cout << v << " ";
std::cout << std::endl;
// 底层是连续内存——可以获取指针
const int* ptr = underlying.data();
std::cout << "第一个元素地址: " << ptr << std::endl;
std::cout << "第一个元素: " << *ptr << std::endl;
}
// ============================
// 示例6:集合操作
// ============================
void set_operations_demo() {
std::flat_set<int> a = {1, 2, 3, 4, 5};
std::flat_set<int> b = {3, 4, 5, 6, 7};
// 交集
std::vector<int> intersection;
std::ranges::set_intersection(a, b, std::back_inserter(intersection));
std::cout << "交集: ";
for (int v : intersection) std::cout << v << " ";
std::cout << std::endl; // 3 4 5
// 并集
std::vector<int> union_result;
std::ranges::set_union(a, b, std::back_inserter(union_result));
std::cout << "并集: ";
for (int v : union_result) std::cout << v << " ";
std::cout << std::endl; // 1 2 3 4 5 6 7
// 差集
std::vector<int> diff;
std::ranges::set_difference(a, b, std::back_inserter(diff));
std::cout << "差集 a-b: ";
for (int v : diff) std::cout << v << " ";
std::cout << std::endl; // 1 2
}
// ============================
// 示例7:批量操作
// ============================
void batch_demo() {
std::flat_set<int> s;
// 批量插入
std::vector<int> data = {9, 1, 5, 3, 7, 2, 8, 4, 6};
s.insert(data.begin(), data.end());
std::cout << "批量插入: ";
for (int v : s) std::cout << v << " ";
std::cout << std::endl;
// erase_if(C++23)
std::erase_if(s, [](int x) { return x % 2 == 0; });
std::cout << "去掉偶数: ";
for (int v : s) std::cout << v << " ";
std::cout << std::endl; // 1 3 5 7 9
}
int main() {
std::cout << "=== 基本用法 ===" << std::endl;
basic_demo();
std::cout << "\n=== 已排序构造 ===" << std::endl;
sorted_demo();
std::cout << "\n=== 字符串集合 ===" << std::endl;
string_demo();
std::cout << "\n=== 自定义比较 ===" << std::endl;
custom_compare_demo();
std::cout << "\n=== 底层容器 ===" << std::endl;
underlying_demo();
std::cout << "\n=== 集合操作 ===" << std::endl;
set_operations_demo();
std::cout << "\n=== 批量操作 ===" << std::endl;
batch_demo();
return 0;
}何时选择 flat_set
| 场景 | 推荐 | 原因 |
|---|---|---|
| 构建后主要查找/遍历 | flat_set | 缓存友好 |
| 频繁插入删除 | set | O(log n) 插入删除 |
| 需要迭代器稳定性 | set | flat_set 修改后迭代器失效 |
| 内存受限 | flat_set | 无节点指针开销 |
| 小数据集(< 几百) | flat_set | 缓存效果好 |
| 不需要有序 | unordered_set | O(1) 查找 |
| 需要连续内存 | flat_set | 底层是 vector |
适用场景
- 小型查找集合(如配置中的有效值列表)
- 构建一次、查找多次的场景
- 需要有序遍历的集合
- 需要直接访问底层连续内存
- 与需要排序数据的算法(set_intersection 等)配合
常见问题
flat_set 和手动排序的 vector 有什么区别?
flat_set 封装了排序和去重的逻辑,保证始终有序且唯一。手动用 vector + sort + unique 可以达到类似效果,但 flat_set 提供了标准的集合接口(contains、find、insert、erase 等),使用更方便。
flat_set 的底层容器可以换吗?
可以。默认是 std::vector,也可以指定为 std::deque。通过模板参数 KeyContainer 指定。
flat_multiset 和 flat_set 什么区别?
flat_multiset 允许重复元素,flat_set 要求元素唯一。类似于 multiset 和 set 的关系。
注意事项
- 插入和删除是 O(n) 的
- 插入和删除后所有迭代器失效
- 从已排序数据构造时用
sorted_unique标签 - 底层默认使用 vector
- 需要
<flat_set>头文件 - 不支持节点操作
总结
std::flat_set 是 C++23 引入的有序集合适配器,底层使用排序的连续容器,提供与 std::set 相同的接口。连续内存布局让查找和遍历更加缓存友好,内存开销更低。代价是插入和删除变成 O(n)。flat_set 最适合小型集合或"构建一次、查找多次"的场景。可以直接访问底层的 vector,方便与需要连续内存的 API 交互。配合标准的集合算法(set_intersection、set_union 等),flat_set 因为其有序和连续特性而表现优秀。