我注意到在有效的STL

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

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

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


当前回答

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

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

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

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

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

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

其他回答

当你想在容器之间移动对象时,你可以使用list::splice。

例如,一个图划分算法可以将常数数量的对象递归地划分到数量不断增加的容器中。对象应该初始化一次,并始终保持在内存中的相同位置。通过重新链接来重新排列比重新分配要快得多。

Edit: as libraries prepare to implement C++0x, the general case of splicing a subsequence into a list is becoming linear complexity with the length of the sequence. This is because splice (now) needs to iterate over the sequence to count the number of elements in it. (Because the list needs to record its size.) Simply counting and re-linking the list is still faster than any alternative, and splicing an entire list or a single element are special cases with constant complexity. But, if you have long sequences to splice, you might have to dig around for a better, old-fashioned, non-compliant container.

std::list的一个特殊功能是拼接(将列表的一部分或整个链接或移动到另一个列表中)。

或者如果你的内容复制非常昂贵。在这种情况下,使用列表对集合进行排序可能更便宜。

还要注意,如果集合很小(并且复制内容的开销不是特别大),即使在任何地方插入和删除,vector的性能也可能优于list。列表单独分配每个节点,这可能比移动几个简单的对象要昂贵得多。

我不认为有什么严格的规定。这取决于您最想对容器做什么,以及您希望容器有多大以及所包含的类型。vector通常优于list,因为它将其内容分配为单个连续块(它基本上是一个动态分配的数组,在大多数情况下,数组是保存一堆东西的最有效方式)。

基本上,vector是一个具有自动内存管理功能的数组。数据在内存中是连续的。试图在中间插入数据是一项代价高昂的操作。

在列表中,数据存储在不相关的内存位置。在中间插入数据并不需要复制一些数据来为新数据腾出空间。

为了更具体地回答你的问题,我将引用这一页

对于访问元素以及从序列末尾添加或删除元素,向量通常是最有效的。对于涉及在末尾以外的位置插入或删除元素的操作,它们的性能不如deques和list,并且迭代器和引用的一致性也不如list。

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

在表格中总结答案以供快速参考:

Vector List
Access Faster Slower
Insert/Delete Operations Slower Faster
Memory Allocation Contiguous Non-contiguous
Size Pre-allocation Need to be reserved Not necessary to reserve
Space Required Per Element Only for the element itself For element and pointers to next
(and optionally previous elements)