我注意到在有效的STL
向量是这样一种序列 默认情况下应该使用。
这是什么意思?似乎忽略效率向量可以做任何事情。
谁能给我一个场景,其中向量不是一个可行的选择,但必须使用列表?
我注意到在有效的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。如果你需要随机访问,你就需要向量,而不是列表。除此之外,在某些情况下,根据应用程序需要其中一个或另一个,但一般来说,这些都是很好的指导原则。