我注意到在有效的STL

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

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

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


当前回答

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

其他回答

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

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

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

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

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

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

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

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

我班上的学生似乎无法向我解释什么时候使用向量更有效,但他们在建议我使用列表时看起来很高兴。

这是我的理解

列表: 每一项都包含下一个或上一个元素的地址,所以有了这个功能,你可以随机项,即使它们没有排序,顺序也不会改变:如果你的内存是碎片化的,它是有效的。 但是它还有一个非常大的优势:你可以很容易地插入/删除项,因为你唯一需要做的就是改变一些指针。 缺点: 要读一个随机的条目,你必须从一个条目跳到另一个条目,直到你找到正确的地址。

Vectors: When using vectors, the memory is much more organized like regular arrays: each n-th items is stored just after (n-1)th item and before (n+1)th item. Why is it better than list ? Because it allow fast random access. Here is how: if you know the size of an item in a vector, and if they are contiguous in memory, you can easily predict where the n-th item is; you don't have to browse all the item of a list to read the one you want, with vector, you directly read it, with a list you can't. On the other hand, modify the vector array or change a value is much more slow.

列表更适合用于跟踪可以在内存中添加/删除的对象。 当您希望从大量单个项中访问一个元素时,向量更适合。

我不知道列表是如何优化的,但你必须知道,如果你想要快速读取访问,你应该使用向量,因为STL固定列表有多好,它在读取访问方面不会像向量那样快。

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

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

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

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

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。如果你需要随机访问,你就需要向量,而不是列表。除此之外,在某些情况下,根据应用程序需要其中一个或另一个,但一般来说,这些都是很好的指导原则。