从flat_set管窥C++的价值权衡
前几天，有朋友催更 C++ 系列，让讲讲 flat_set 之类。今天，就来写这篇半命题作文。顺便也宣布下：欢迎催更，欢迎指定题目或内容，这也是对我的肯定，虽然从响应时间上，我无法给出绝对的承诺，但我保证，我一定会尽力尽早满足的。
1. 最基本的集合容器 std::set
在C++标准库中，提供了大量的容器，用于按照特定方式存放一组数据，并通过一系列形式上统一的函数调用接口，以及各种经过仔细权衡和大量测试的优质算法，来对这些数据进行操作。
这其中有一类相对简单的容器，就是集合。集合通常会要求没有重复元素。最基本的集合类就是 std::set。
之前我在《从C++语法特性检查想到的》一文中提到过，“在C/C++中，自己造的轮子，超越标准库是有可能的”。因为“作为标准库，需要适应各种复杂使用场景，需要具备广泛的支持能力，这成为了沉重的负担”。从标准库针对同一类容器，提供了不止一种选择，就可以看出这种需要权衡考虑、并支持各种场景的沉重负担。
标准的集合类 std::set，是一个中庸的选择，它底层使用红黑树（一种最常见的平衡二叉树），来确保每次对容器内容的调整（如插入、删除），都能在 O(n * log(n)) 时间复杂度内完成。这同时也使得它，如同在标准中规定的，可以保证容器元素是经过排序的（即从 std::begin() 遍历到 std::end() 是正序的；如果是整数元素，则是从小到大排序）。红黑树算法的高效，使得 std::set 足以应付日常大多数场景了。
2. 标准库中的其他集合容器
但是，凡事总有例外，而且，在追求性能极致的C++极客眼中，每次访问一个元素都要经历 O(log(n))，每次插入或删除一个元素都要经历 O(n * log(n))，实在是难以忍受的折磨。为什么非要搞个二叉树？为什么不能用哈希（hash），从而实现常数时间复杂度？嗯，这是可以的，这就是 std::unordered_set。
有了 std::unordered_set，是不是它与 std::set 配合，就足够打遍天下了呢？当然不是，计算机的世界并不总是跟数学的世界对应。有时候，为了实现一些特殊需求，我们还希望集合里允许重复元素出现。可以吗？难道不可以吗？可以！只要是“合理”的需求，极客们总是有办法满足的。于是在标准库中，又出现了 std::multiset 和 std::unordered_multiset。（注：std::set 和 std::multiset 是一开始在 C++03 时就有的，而 std::unordered_set 和 std::unordered_multiset 是在 C++11 中加入的。）
然而，哈希也并不完美，虽然号称是常数时间，但毕竟要通过哈希函数计算和重新寻址，因而各元素并不存放在空间连续的内存中，远不如 std::vector 来得顺眼。有没有办法解决这个问题，让“好处占尽”呢？这就轮到本文的主角 flat_set 登场了。
3. 将 std::vector 当成集合来用
std::vector 是标准库中最接近完美的容器，因为它可以直接对应到物理意义上的一块连续内存，并通过容器标准函数进行各类常见操作，而且很方便将其与其他不同类型容器之间，进行复制、转移或变换。这简直就是把洁癖到容不下各种复杂封装、恨不得直接写C或汇编，但又割舍不掉种种高级语言的丰富类库函数操作和优雅写法，完美地结合起来并加以满足。
于是，我们总是不免希望，能用 std::vector 的地方，就尽量选择它（C++中的最佳实践，确实也都是这么建议的），包括集合类需求的场景。在C++中有一种技术，名为“容器适配器”（container adaptors），就是把标准容器进行“适配”包装，使其表现得像另外一种不同的、甚至大相径庭的容器。flat_set 正是通过这种技术，使得一个在内存中以连续存储方式保存元素的数据结构，对外表现得跟 std::set 一样。
这么折腾一圈，到底图啥呢？其实核心在于“性能”，这个永恒的话题！
4. 关于选择 flat_set 的权衡
flat_set 的性能优势主要在于几个方面：
更好的缓存局部性：由于数据存储在连续的内存块中，flat_set的元素可以更有效地利用CPU缓存，提高访问速度。
优化的迭代性能：连续存储也使得迭代器遍历速度更快，尤其是在访问大量数据时。
可自定义的存储分配器：是的，关于“以std::vector来存储”这件事，flat_set 并未完全剥夺用户的选择权，它提供了一个模板参数，来允许用户指定其他特定的底层容器和分配器，从而可为具体场景进行内存使用优化。
这里顺道补充划个重点：优化考虑到这份上，其实简直就是奔着嵌入式支持去的。虽然很多时候做嵌入式会受限于硬件厂商提供的交叉编译环境，以至于只能采用旧版的 gcc 或 STL，但如果能设法重新编译并升级到较新的版本，把这些更好的 C++ 新标准及其标准库用起来，实在会是一件大幅提升开发效率的事。 因此，它所适合的应用场景包括： 大量数据访问：当需要频繁地读取集合中的元素时，flat_set 的连续内存布局提供了优势。
性能关键型应用：在延迟敏感的应用中，flat_set 的高迭代速度和优秀的缓存局部性可以带来显著的性能提升。
内存使用优化：如果内存使用是一个关键问题，flat_set 允许更细粒度的控制，如自定义分配器和预留空间。 当然，任何事都是在做选择（如同我在《我在创业中的抉择与思考（上）》一文中提到的理念），选择使用 flat_set，获得并享受其优势的同时，自然也是要付出代价的。其代价至少包括： 插入和删除代价：由于需要保持元素顺序，插入和删除操作可能需要移动多个元素，这使得这些操作的成本较高。
初始构建成本：构建一个大的 flat_set 可能比标准集合更耗时，因为它需要排序和移动元素。
5. flat_set 的使用
不知道你是否注意到，在描述其他容器时，我都会加上 std:: 前缀，但 flat_set 却没有。其实，主要是因为，到目前为止，我们都还无法使用 std::flat_set。
C++23 标准计划将 flat_set 引入，但我们还需要等待该标准的最后审批通过和正式发布，以及各编译器厂商的相应跟进实现。在这件事发生之前，我们可以通过 boost 类库来使用它，这就不是 std::flat_set，而是boost::container::flat_set 了。
所以，期待 C++23 的正式发布，到时候应该就可以大大方方地直接使用 std::flat_set 了。
篇幅差不多了，这篇暂且打住。写完我才发现，这样一篇计算机语言技术类文章，我竟然没有留下一丝提供代码展示的空间。算了，就这样吧，这次就当闲聊，下次再补代码吧。
注：本文首发表于“不靠谱颜论”公众号，并同步至本站。