我相信我想使用 boost::icl::interval_map 来解决问题(描述 here ，如果 interval_maps 最终有效，我将发布完整的答案。)
我想使用 interval_map<unsigned long long, set<foo*>> ，但是 boost::icl 的文档提到存在潜在的效率问题(低于 from )。
We are introducing interval_maps using an interval map of sets of strings, because of it's didactic advantages. The party example is used to give an immediate access to the basic ideas of interval maps and aggregate on overlap. For real world applications, an interval_map of sets is not necessarily recommended. It has the same efficiency problems as a std::map of std::sets. There is a big realm though of using interval_maps with numerical and other efficient data types for the associated values.
std::map of std::sets 的效率问题是什么？ 以及我怎样才能避免它们？
最佳答案
两者都是 std::map<K, V>和 std::set<V>是由指针链接的基于节点的容器。遍历它们具有很好的复杂性保证(即，每个单独的操作至多为 O(log n))，但您实际上需要相当大的容器来比较复杂性，例如，与 std::vector<std::pair<K, V>> 相比。特别是当 K和 V是基本类型。基于节点的容器的主要性能问题是它们或多或少地随机分布在内存中，而现代 CPU 喜欢访问以某种形式聚集的数据。
当然，像往常一样，您需要在相当真实的数据集上测量不同实现之间获得的时间，以确定哪种数据结构产生最佳性能。
关于c++ - STL::sets的STL::map的效率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18581957/