我注意到在有效的STL

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

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

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


当前回答

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

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

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

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

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

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

其他回答

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

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

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

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

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

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

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

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

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

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

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

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

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