STL中的向量和列表

我注意到在有效的STL

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

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

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

当前回答

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

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

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

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

其他回答

列表只是stl中double - linkedlist的包装器，因此提供了您可能希望从d-linklist中获得的功能，即O(1)插入和删除。向量是具有传染性的数据序列，其工作方式类似于动态数组。S-更容易遍历。

任何时候都不能使迭代器失效。

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

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

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

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

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

	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)

推荐文章