std::list 和 std::vector - 两全其美？

Question

通过向量与 STL 中的列表：

• std::vector：最后的插入是常数，摊销时间，但其他地方的插入是一个代价高昂的 O(n)。

• std::list：您不能随机访问元素，因此获取列表中的特定元素可能会很昂贵。

我需要一个容器，这样您既可以在 O(1) 时间内访问任何索引处的元素，也可以在 O(1) 时间内在任何索引处插入/删除元素。它还必须能够管理数千个条目。有这样的容器吗？

编辑：如果不是 O(1)，一些 X << O(n)？

Answer 1

有一个理论结果表明，任何表示有序列表的数据结构都不能比 O(log n / log log n) 具有插入、按索引查找、删除和更新的所有时间，因此不存在这样的数据结构。

不过，有些数据结构与此非常接近。例如，订单统计树允许您在每个时间 O(log n) 的列表中的任何位置进行插入、删除、查找和更新。这些在实践中相当不错，你可以在网上找到一个实现。

根据您的特定应用程序，可能有更适合您需求的替代数据结构。例如，如果您只关心在每个时间点找到最小/最大的元素，那么像斐波那契堆这样的数据结构可能适合这个要求。（斐波那契堆在实践中通常比常规二叉堆慢，但相关的配对堆往往运行得非常快。）如果您经常通过添加或减去元素来更新元素范围，那么Fenwick 树可能更好称呼。

希望这可以帮助！