我注意到在有效的STL

向量是这样一种序列 默认情况下应该使用。

这是什么意思?似乎忽略效率向量可以做任何事情。

谁能给我一个场景,其中向量不是一个可行的选择,但必须使用列表?


当前回答

std::vector std::list
Contiguous memory. Non-contiguous memory.
Pre-allocates space for future elements, so extra space required beyond what's necessary for the elements themselves. No pre-allocated memory. The memory overhead for the list itself is constant.
Each element only requires the space for the element type itself (no extra pointers). Each element requires extra space for the node which holds the element, including pointers to the next and previous elements in the list.
Can re-allocate memory for the entire vector any time that you add an element. Never has to re-allocate memory for the whole list just because you add an element.
Insertions at the end are constant, amortized time, but insertions elsewhere are a costly O(n). Insertions and erasures are cheap no matter where in the list they occur.
Erasures at the end of the vector are constant time, but for the rest it's O(n). It's cheap to combine lists with splicing.
You can randomly access its elements. You cannot randomly access elements, so getting at a particular element in the list can be expensive.
Iterators are invalidated if you add or remove elements to or from the vector. Iterators remain valid even when you add or remove elements from the list.
You can easily get at the underlying array if you need an array of the elements. If you need an array of the elements, you'll have to create a new one and add them all to it, since there is no underlying array.

一般来说,当你不关心你使用的是哪种类型的顺序容器时,使用vector,但如果你在容器的任何地方做很多插入或擦除,而不是在末尾,你就会想要使用list。如果你需要随机访问,你就需要向量,而不是列表。除此之外,在某些情况下,根据应用程序需要其中一个或另一个,但一般来说,这些都是很好的指导原则。

其他回答

当你在序列中间有很多插入或删除时。例如,内存管理器。

List是双链表,所以很容易插入和删除一个元素。我们只需要改变这几个指针,而在向量中如果我们想在中间插入一个元素那么它后面的每个元素都要移动一个下标。此外,如果向量的大小已满,那么它必须首先增加它的大小。所以这是一个昂贵的手术。 因此,在这种情况下,只要需要更频繁地执行插入和删除操作,就应该使用案例列表。

这里的大多数答案都遗漏了一个重要的细节:为什么?

你想在集装箱里放些什么?

如果它是int型的集合,那么std::list在任何情况下都将丢失,不管你是否可以重新分配,你只从前面删除,等等。遍历列表的速度较慢,每次插入都需要与分配器进行交互。要准备一个例子是极其困难的,其中list<int>击败vector<int>。即使这样,deque<int>可能更好或关闭,而不仅仅是使用列表,这将有更大的内存开销。

然而,如果您正在处理大而丑陋的数据块——而且数量很少——您不想在插入时过度分配,而由于重新分配而进行复制将是一场灾难——那么您可能,也许,使用list<UglyBlob>比使用vector<UglyBlob>更好。

不过,如果你切换到vector<UglyBlob*>或甚至vector<shared_ptr<UglyBlob> >, - list仍然会滞后。

因此,访问模式、目标元素数量等仍然会影响比较,但在我看来,元素大小、复制成本等。

想要重复将大量项插入序列末尾以外的任何位置的情况。

看看每种不同类型的容器的复杂度保证:

标准容器的复杂性保证是什么?

保留迭代器的有效性是使用列表的原因之一。另一种情况是当你不希望在推送物品时重新分配向量。这可以通过巧妙地使用reserve()来管理,但在某些情况下,仅使用列表可能更容易或更可行。