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_setstd::setstd::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缓存友好
频繁插入删除setO(log n) 插入删除
需要迭代器稳定性setflat_set 修改后迭代器失效
内存受限flat_set无节点指针开销
小数据集(< 几百)flat_set缓存效果好
不需要有序unordered_setO(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 因为其有序和连续特性而表现优秀。