flat_map, flat_set, flat_multimap, flat_multimap
这些是C++23引入的新容器类型，属于"扁平化关联容器"(flat associative containers)家族。它们提供了与标准关联容器(map, set等)类似的接口，但使用不同的底层实现，从而在某些场景下提供更好的性能。
基本概念
这些扁平化容器与标准关联容器的主要区别在于：
- 底层实现：使用排序的连续存储(通常是vector或类似结构)而非树结构
- 内存布局：元素在内存中是连续存储的。
- 性能特点：
- 查找速度比标准容器更快(两者都是二分查找，但是flat_map/set等内存连续，是缓存友好的，提高缓存命中率，总体速度比map/set等快)。
- 插入和删除通常较慢(需要对数组中的元素进行整体的移动，尤其不支持移动构造时)
- 迭代速度更快(由于内存局部性)
- 内存占用更小(相对于平衡二叉树，减少了节点指针的维护，从而节省了内存空间)
各容器详解
1. flat_map
类似std::map，但使用扁平化存储的键值对容器。
- 查找速度比标准关联容器
std::map更快(二者使用二分查找时间复杂度为O(log n),但是flat_map底层使用数组存储，在缓存友好性方面优于树结构，缓存命中率通常要高)。 - 迭代速度比标准关联容器
std::map快得多 。 - 使用随机访问迭代器而不是双向迭代器。
- 每个元素的内存消耗更少。
- 改进的缓存性能（数据存储在连续内存中，提高缓存命中率）。
- 迭代器不稳定（插入和删除元素时迭代器会失效）。
- 无法存储不可复制和不可移动的值类型。
- 异常安全性比标准关联容器弱（在删除和插入时移动值可能会抛出异常）。
- 插入和删除操作比标准关联容器慢（尤其是对于不可移动类型,插入和删除复杂度 O(N) 甚至高于map的 O(logN)）。
flat_map原理
flat_map：底层使用了有序数组，pair<Key, Value>直接作为元素存储在内，查找时通过二分法的方式定位数据，插入和删除时需要移动目标元素后的所有元素。
std::flat_map将所有的Key保存在连续的内存空间中（比如std::vector）。同样的，所有的Value也保存在连续的内存空间中。比如说，我们有三个键值对：(1, 2), (5, 6), (3, 4)，那么它们在std::flat_map中的存储如下图所示：
注意，Key序列是有序存储的，并且Key[i]和Value[i]构成了一个键值对。
对std::flat_map的遍历就是对这两个数组的遍历，由于数据是连续存储的，所以遍历速度会显著快于std::map。
如果对std::flat_map进行查找操作，只需要在Key数组上做binary_search即可，最多比较 log2(n) 次。相比之下，std::map的红黑树实现的树高可以达到 2log2(n+1) ，比较次数多于std::flat_map。
但是如果要对std::flat_map进行插入/删除操作，需要对数组中的元素进行整体的移动，最坏时间复杂度为 O(n) 。
std::flat_map有5个模板参数，分别表示：
- Key的类型
- Value的类型
- 比较器（默认为
std::less<Key>） - Key的存储容器类型（默认为
std::vector<Key>） - Value的存储容器类型（默认为
std::vector<T>）
#include <flat_map>
#include <iostream>
#include <string>int main()
{std::flat_map<std::string, int> ages{{"Alice", 30},{"Bob", 25},{"Charlie", 35}};// 插入元素(可能触发排序和移动)ages.insert({"David", 28});// 查找元素if (auto it = ages.find("Alice"); it != ages.end()) {std::cout << "Alice is " << it->second << " years old\n";}// 迭代for (const auto& [name, age] : ages) {std::cout << name << ": " << age << "\n";}
}2. flat_set
类似std::set，但使用扁平化存储的唯一键集合。
#include <flat_set>
#include <iostream>int main()
{std::flat_set<int> primes{2, 3, 5, 7, 11};// 插入元素primes.insert(13);// 检查存在性if (primes.contains(7)) {std::cout << "7 is a prime number\n";}// 范围查询auto [begin, end] = primes.equal_range(5);for (auto it = begin; it != end; ++it) {std::cout << *it << " ";}std::cout << "\n";
}性能考虑
-
适合场景：
- 需要频繁查找但较少插入/删除
- 需要快速迭代
- 内存受限环境
-
不适合场景：
- 需要频繁插入/删除
- 需要稳定的迭代器(插入/删除会使迭代器失效)
-
与标准容器比较：
- 查找：O(log n) - 与标准容器相同,但是缓存友好。
- 插入：O(n) - 比标准容器的O(log n)慢
- 内存：通常更节省(没有指针开销)
自定义比较和分配器
与标准容器一样，可以自定义比较函数和分配器：
struct CaseInsensitiveCompare
{bool operator()(const std::string& a, const std::string& b) const {return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),[](char c1, char c2) { return tolower(c1) < tolower(c2); });}
};std::flat_set<std::string, CaseInsensitiveCompare> caseInsensitiveSet;性能：xhttps://zhuanlan.zhihu.com/p/661418250