C++23: Flat Containers
Hawtian Wang
Contents
C++23 的周期里又补充了四个非常重要的容器，这应该是继 C++11 加入 unordered_{map|set} 以来，
终于再次向 STL 里增加的容器。这四个容器是其实就是 map/set/multimap/multiset
的 flat 版本。
flat_mapflat_setflat_multimapflat_multiset
1 Specialties
这组新的容器可以在合适的场景下替换其对应的容器（当然也包括了他们的 unordered_ 的版本），
和同功能的其他容器相比:
- 更慢的插入和删除，因为插入和删除都会导致元素的移动，像
vector的insert一样 - 插入和删除都会造成旧迭代器的失效，因为不论是插入还是删除，都会伴随着大部分元素的移动，保存的旧迭代器很难不失效
- 元素类型必须是可移动（moveable）或者可拷贝的（copyable）
- 异常安全变得更弱了，像
vector一样构造函数的异常没法保证后面的元素可以成功构造
那上面付出的代价，我们获得了什么?
- 更快的遍历，在一个简单数组上的一次后继的时间复杂度是 $O(1)$ 而对于
map这个时间是$O(log_2n)$ - 得益于
vector的实现，现在我们的迭代器是random access的了 - 更小的空间复杂度，对于
map不用保存节点的额外信息了，对于unordered_map不会有空的slot - 更好的缓存性能（因为存储是连续的）
- 更快的查找，虽然数量级上都还是 $O(log_2n)$ 但是常数上小了很多
| Container | Ordered | Insert | Erase | Find | iter++ |
|---|---|---|---|---|---|
map/set | Yes | $O(log_2n)$ | $O(log_2n)$ | $O(log_2n)$ | $O(log_2n)$ |
unordered_{map/set} | No | $O(1)$ | $O(1)$ | $O(1)$ | $O(1)$ |
flat_{map/set} | Yes | $O(n)$ | $O(n)$ | $O(log_2n)$, but smaller constant | $O(1)$ |
所以它应该更适合存那些构造出来基本就不会改的数据，获得更好的遍历和查找性能。
