c++ - stl::map 的 stl::sets 的效率

Question

我相信我想使用 boost::icl::interval_map 来解决问题（在此处描述，如果 interval_maps 最终有效，我将发布完整的答案。）

我想使用interval_map<unsigned long long, set<foo*>>，但 boost::icl 的文档提到存在潜在的效率问题（以下来自）。

我们使用一组字符串的区间映射来介绍区间映射，因为它具有教学优势。派对示例用于立即访问区间图和重叠聚合的基本思想。对于现实世界的应用程序，不一定建议使用一组 interval_map。它与 std::sets 的 std::map 具有相同的效率问题。尽管将区间映射与数字和其他有效数据类型一起用于关联值，但仍有一个很大的领域。

std::sets 的 std::map 的效率问题是什么？ 以及如何避免它们？

Answer 1

两者std::map<K, V>和std::set<V>都是通过指针链接的基于节点的容器。遍历它们有很好的复杂性保证（即，每个单独的操作最多为 O(log n)），但您实际上需要相当大的容器来比较复杂性，例如，std::vector<std::pair<K, V>>特别是当K和V是基本类型时。基于节点的容器的主要性能问题是它们在内存中或多或少地随机布局，而现代 CPU 喜欢访问以某种形式聚集的数据。

当然，像往常一样，您需要在相当真实的数据集上测量不同实现之间获得的时间，以确定哪种数据结构产生最佳性能。