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

std::list and std::vector - Best of both worlds?(std::list 和 std::vector - 两全其美?)

问题描述

向量与STL中的列表:

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

• std::vector: Insertions at the end are constant, amortized time, but insertions elsewhere are a costly O(n).

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

std::list: You cannot randomly access elements, so getting at a particular element in the list can be expensive.

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

I need a container such that you can both access the element at any index in O(1) time, but also insert/remove an element at any index in O(1) time. It must also be able to manage thousands of entries. Is there such a container?

如果不是 O(1)，一些 X <<

If not O(1), some X << O(n)?

推荐答案

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

There's a theoretical result that says that any data structure representing an ordered list cannot have all of insert, lookup by index, remove, and update take time better than O(log n / log log n), so no such data structure exists.

不过，有些数据结构与此非常接近.例如，订单统计树让您可以在任何地方进行插入、删除、查找和更新时间 O(log n) 的列表.这些在实践中相当不错，您也许可以在线找到实现.

There are data structures that get pretty close to this, though. For example, an order statistics tree lets you do insertions, deletions, lookups, and updates anywhere in the list in time O(log n) apiece. These are reasonably good in practice, and you may be able to find an implementation online.

根据您的具体应用，可能会有更适合您需求的替代数据结构.例如，如果您只关心在每个时间点找到最小/最大元素，那么像 斐波那契堆 可能符合要求.(斐波那契堆在实践中通常比常规二叉堆慢，但相关的配对堆倾向于运行速度非常快.)如果您经常通过添加或减去元素来更新元素范围，那么 芬威克树 可能是更好的选择.

Depending on your specific application, there may be alternative data structures that are more tailored toward your needs. For example, if you only care about finding the smallest/biggest element at each point in time, then a data structure like a Fibonacci heap might fit the bill. (Fibonacci heaps are usually slower in practice than a regular binary heap, but the related pairing heap tends to run extremely quickly.) If you're frequently updating ranges of elements by adding or subtracting from them, then a Fenwick tree might be a better call.

希望这会有所帮助！

这篇关于std::list 和 std::vector - 两全其美?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！