我正在寻找一个可以实现类似于 std::map 和 multimap 的库，但没有树，而是向量，比如pair<vector<key>,vector<value>>. 该库必须保持向量同步和排序。
我想比较地图vector<pair<key,value>>和这样的库的性能。我不会尝试做一个通用的基准测试，我只想要对我的应用程序更快的东西。
我可以像其他人一样使用地图，但是——我不知道我在说什么——我担心缓存未命中太多。我疯狂的、未受过教育的猜测是，我的应用程序只做很少的分组插入和许多分散的搜索，将受益于更紧凑和连续的键。
事实上，如果我要编写代码，我会用两个类来完成。一个未排序的版本，只允许快速的 push_back 插入，然后转换为排序的版本，该版本将采用未排序的版本，对其进行排序，可能检查重复性，然后允许快速搜索和较慢的排序插入。这实际上是 Scott Meyers 的 Effective STL 的第 23 条：“考虑用排序的向量替换关联容器”。
编辑：正如关于flat_(multi)map/set的 Boost 文档所指出的，Matt Austern 而不是 Scott Meyers 首先建议用向量替换地图和集合：http: //lafstern.org/matt/col1.pdf