std :: list和std :: vector-两全其美？ [英] std::list and std::vector - Best of both worlds?

问题描述

通过 vector vs. 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<< O（n）？

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-两全其美？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！