google的时候偶然看到一个chromium开发者有关std::unordered_map的讨论，感觉比较有意思，文章主要是在说在chromium中选择map/set的原则，这里记录一下相关的结论。
Map/Set
std::map and std::set
通过红黑树来实现，每个节点保存了一个left pointer，一个right pointer，一个parent pointer和一个color，在64位的平台上占32个byte
std::unordered_map and std::unordered_set
哈希表实现，通过std::vector + std::forward_list来实现。
在开始的时候会分配一个长度为8的哈希表，当插入了8个数据后，会分配64个entry。超过64以后每当load factor超过1的时候，会多分配一倍的entry数量。
空的容器的大小为：sizeof(std::unordered_map) = 64 + 8个节点。每个节点占用1/2个指针（取决于实现），比如libc++占用一个指针，按照平均0.5的load factor来看，就是每一项占16个byte
在windows上的microbenchmark中显示，插入1M个整数，std::unordered_set用的时间是std::set的1.07倍，查询则是0.67倍。对于size比较小的情况下，比如4个entry，std::unordered_set/std::set/base::flat_set的查询速度是接近的。（在ARM上性能可能会更差，因为涉及到除法来计算bucket（2的倍数直接右移？））
base::flat_map and base::flat_set
实现是一个sorted vector，通过二分来进行搜索。插入的时候需要做元素的移动。
每一个元素占用的内存空间取决于vector的重分配策略。平均情况下3/4的load factor，所以每个元素额外占用的空间是sizeof(T) * 0.25
base::fixed_flat_map and base::fixed_flat_set
定长的base::flat_map，底层实现不是vector而是array。不支持动态的插入，只能通过初始化的时候进行构造。优点是没有动态内存分配。
base::small_map
inline了一个小的栈上的buffer，暴力搜索，数据大小超了以后会被存储到std::map/std::unordered_map中。好处是数据规模小的时候性能比较高，并且也可以处理比较大的数据规模。和inline_vector/small_vector一个思路
代码的大小会多一些，因为逻辑更多。
使用建议
* std::unordered_map/std::unordered_set在container比较小的时候整体开销比较大，所以只有在数据量大的时候再使用他们。不要默认使用他们，因为大多数情况下查询开销不会差距很大，而内存开销相对较高。
* base::small_map的代码量会大一些。但是如果是在关键路径上，他们节省的内存开销会更有优势。
* 不知道用什么的时候就用std::map/std::set
* chromium中很多对象的移动速度比较快，所以可以考虑使用base::flat_map。他们的修改操作可以避免很多的malloc，并且他们有更好的缓存局部性。
Deque
std::deque and std::queue
deque的实现一般是，一堆data block 加上一个指针数组。保证随机访问，均摊下常数时间的双端操作，以及线性时间下在中间修改。
Microsoft的实现下，每个block的大小都是min(sizeof(T), 16)，基本上说明每次deque的插入都涉及到堆内存分配。并且从不会进行block的释放，只会复用
libc++使用了4k的block大小，相对来说空间浪费比较大。然后至多会存在两个空block
libstdc++用了512的block，并且在block空了以后会立刻释放
base::circular_deque and base::queue
通过环状buffer实现deque，当空间不够用的时候，底层的array会进行增长。和vector不同的是，当浪费的空间过多的时候会进行shrink
使用建议
- chromium应该总是使用
base::circular_deque/base::queue避免内存占用过多
文章评论