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

Question

通过 vector vs. list in STL :

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

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

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

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

Answer 1

有 a theoretical result 说任何表示有序列表的数据结构都不能比 O(log n/log log n) 具有插入、按索引查找、删除和更新的所有时间，因此不存在这样的数据结构。
不过，有些数据结构与此非常接近。例如，order statistics tree 允许您在每个时间为 O(log n) 的列表中的任何位置进行插入、删除、查找和更新。这些在实践中相当不错，你可以在网上找到一个实现。
根据您的特定应用程序，可能有更适合您需求的替代数据结构。例如，如果您只关心在每个时间点找到最小/最大的元素，那么像 Fibonacci heap 这样的数据结构可能符合要求。 (斐波那契堆在实践中通常比常规二元堆慢，但相关的 pairing heap 往往运行得非常快。)如果您经常通过添加或减去元素来更新元素范围，那么 Fenwick tree 可能是更好的调用。
希望这可以帮助!