c++ - 为快速查找优化的有序关联数据结构？

Question

我正在寻找一种为快速查找std::map而优化的-esque 数据结构。

一种方法是使用 sortedstd::vector作为底层存储来实现 map 的接口 -binary_search由于随机访问迭代器和缓存局部性，这将提供快速。

然而，这听起来像是对轮子的重新发明。肯定已经存在这样的东西了？

是否有使用 std::vector 进行存储的开源有序关联数据结构？

编辑：

针对建议仅使用 std::map的评论- 请在此处阅读：http: //lafstern.org/matt/col1.pdf

Answer 1

Boost.Containers 库有一个有序的地图容器，其存储由一个名为boost::flat_map. 但是请注意，渐近的理论复杂度与标准map（对数）相同，更好的选择取决于用例的许多细节：插入与查找、迭代、迭代器失效要求。

由于接口非常相似，因此应该可以通过 typedef 逐个替换并分析相关性能，这是您绝对必须做的事情。

Answer 2

是否有使用 std::vector 进行存储的开源有序关联数据结构？

维护一个sortedvector怎么样？这样查找可以很快（二进制搜索，没有指针遍历）。