为快速查找优化了有序关联数据结构？
为快速查找优化了有序关联数据结构？
提问于 2013-01-17 22:19:36
我正在寻找一个为std::map快速查找优化的-esque数据结构。
一种方法是使用排序的std::vector作为底层存储来实现map的接口--这将提供快速binary_search，这要归功于随机访问迭代器和缓存局部性。
然而，这听起来像是车轮的重新发明。像这样的东西肯定已经存在了？
是否有一个开放源码有序关联数据结构，使用std：：向量进行存储？
编辑：
对于建议只使用std::map的评论，请阅读此处：http://lafstern.org/matt/col1.pdf
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-01-17 23:05:04
Boost.Containers库有一个有序的映射容器，其存储由一个名为boost::flat_map的连续数组支持。但是，请注意，渐近的理论复杂性与标准的map (对数)相同，更好的选择取决于用例的许多细节:插入与查找、迭代、迭代器失效需求。
由于接口非常相似，所以应该可以通过ty对联f逐个替换，并分析相关的性能，这是您绝对必须做的事情。
Stack Overflow用户
发布于 2013-01-17 22:25:54
是否有一个开放源码有序关联数据结构，使用std：：向量进行存储？
如何维护一个排序的这种方式可以快速查找(二进制搜索，不需要指针遍历)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14389200
复制相关文章
相似问题
腾讯云开发者
