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

Question

我正在寻找一种针对快速查找优化的std::map 式数据结构。

一种方法是使用排序的 std::vector 作为底层存储来实现 map 的接口(interface)——这将提供快速的 binary_search，这要归功于随机访问迭代器和缓存地点。

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

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

编辑:

回应建议只使用 std::map 的评论 - 请阅读此处:http://lafstern.org/matt/col1.pdf

Answer 1

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

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