更新
您需要一个订单统计树。C++ 标准库没有，也没有提供一种简单的方法来实现，见
也没有提升，请参阅“未来工作”和上面链接的问题。
然而，好消息是，这样的树可以libstdc++作为扩展使用！
（原答案：）
- 按排序顺序自动插入元素。（日志 n）
- 从起始节点返回元素的索引/深度。（日志 n）
在我看来，C++ 标准库和 boost 都没有提供一个容器来提供这些开箱即用的复杂性保证。您要么必须自己实现此容器，要么放宽您的复杂性要求并允许O(n)至少使用其中之一。
如果不是：实现这一目标的最佳方法是什么？我正在考虑使用双链接列表的解决方案。是解决这个问题的好选择吗？
std::list是一个双向链表，但只能实现线性时间插入。std::list由于缓存使用不当，是一个很大的性能杀手。
你可能会更好地使用boost::container::flat_set它也只提供线性时间插入，但由于缓存的出色使用（感谢硬件预取器），它的速度仍然会让你感到惊讶。作为奖励，您可以获得随机访问迭代器，因此O(1)如果您已经拥有该元素，则可以及时找到索引。
如果这两个复杂性要求都是必须的，那么我认为没有比实现自平衡二叉搜索树并在每个父节点上存储子树大小更简单的方法了。维护这些额外信息不会破坏O(log n)复杂性。实现它是一项重要且非平凡的工作，即使您从红黑树实现中的一个开始std::map（不保证是红黑树，但libstdc++它是开源的）。
又想到一件事：你的使用模式是什么？您是否一个接一个地完全随机地进行插入和索引查找？如果不是，或者至少主要不是，那么您可能会在两者之间切换数据结构并使用 stl 或 boost 容器之一。
| 归档时间： |
|
| 查看次数： |
928 次 |
| 最近记录： |