stl的效率：：stl：：set的映射

Question

我相信我希望使用boost::icl::interval_map来解决一个问题(描述了这里，如果interval_maps最终成功的话，我会发布一个完整的答案)。

我想使用interval_map<unsigned long long, set<foo*>>，但是boost::icl的文档提到了潜在的效率问题(在从…下面)。

我们使用一组字符串的间隔映射来介绍interval_maps，因为它具有教学优势。党的例子是用来立即访问的基本思想的间隔图和聚合的重叠。对于实际应用程序，不一定推荐使用集合的interval_map。它与std：：set的std::map具有相同的效率问题。但是，对于相关值使用interval_maps和其他有效的数据类型是一个很大的领域。

：：std::map of std：：set的效率问题是什么？和如何避免它们？

Answer 1

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

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