我注意到在有效的STL

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

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

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


当前回答

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

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

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

其他回答

必须使用list的唯一硬性规则是需要将指针分发到容器元素的地方。

与vector不同,你知道元素的内存不会被重新分配。如果可以,那么可能会有指向未使用内存的指针,这在最好的情况下是一个大禁忌,在最坏的情况下是SEGFAULT。

(从技术上讲,*_ptr的向量也可以工作,但在这种情况下,你是在模拟列表,所以这只是语义。)

其他软规则与将元素插入容器中间可能存在的性能问题有关,因此最好使用list。

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

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

如果你不需要经常插入元素,那么向量会更有效。它具有比列表更好的CPU缓存位置。换句话说,访问一个元素使得下一个元素很有可能存在于缓存中,并且可以在不读取慢速RAM的情况下被检索。

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

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

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

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