c++ - 是否有任何支持以下操作的boost/STL容器？

Question

我一直在寻找可以提供以下功能的 STL/boost 容器:

1. 按排序顺序自动插入元素。 (登录 n)
2. 从起始节点返回元素的索引/深度。 (登录 n)

如果没有，实现这一目标的最佳方法是什么？我正在考虑使用双向链接列表的解决方案。这是解决这个问题的好选择吗？

Answer 1

更新

你需要一个 order statistic tree . C++ 标准库没有，也没有提供实现标准库的简单方法，请参阅

• Rank Tree in C++

• How to find rank of an element in stl set in O(logn)

• ith order statistic using C++'s STL

boost 也没有，参见 Future work以及上面链接的问题。

不过，好消息是，这样的树在 libstdc++ 中作为扩展可用!

• GNU Policy-Based STL MAP implemented as order statistic tree

• Example in the doc或 here

---

_{(原始答案:)}

1. Auto insert element in sorted order. (log n)
2. Return index/depth of element from starting node. (log n)

在我看来，C++ 标准库和 boost 都没有提供一个容器来提供这些开箱即用的复杂性保证。您要么必须自己实现此容器，要么放宽您的复杂性要求并允许 O(n) 至少其中之一。

if not: What will be the best way to achieve this ? I am thinking a solution using double link list. Will it be good choice to solve this problem ?

std::list 是双向链表，但只能实现线性时间插入。 std::list 是一个很大的性能 killer ，因为它对缓存的使用不当。

使用 boost::container::flat_set 可能会更好它也只提供线性时间插入，但由于缓存的出色使用(多亏了硬件预取器)，它的速度仍然会让您感到惊讶。作为奖励，您可以获得随机访问迭代器，因此如果您已经拥有该元素，则可以在 O(1) 时间内找到索引。

如果这两种复杂性要求都是必须的，那么我认为没有比实现自平衡二叉搜索树并在每个父节点上存储子树大小更简单的方法了。维护这些额外信息不会破坏 O(log n) 的复杂性。实现它是一项重要且不平凡的工作，即使您从 red-black tree 之一开始也是如此。 std::map 的实现(不保证是红黑树，但在 libstdc++ 中是，并且是开源的)。

---

还有一件事浮现在脑海:您的使用模式是什么？您是否完全随机地进行插入和索引查找，一个接一个？如果不是，或者至少主要不是，那么您可以在两者之间切换数据结构，并使用 STL 或 boost 容器之一。