STL中的向量和列表

我注意到在有效的STL

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

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

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

当前回答

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

2010-02-05 18:53:43

其他回答

〇简单一点在一天结束的时候，当你在c++中选择容器时感到困惑时，使用下面的流程图图像(对我说谢谢):-

向量,

Vector基于传染性记忆矢量是小数据集的一种方式 Vector在遍历数据集时执行最快向量插入删除在巨大数据集上很慢，但在非常数据集上很快小

列表,

List基于堆内存列表是非常庞大的数据集 List在遍历小数据集时相对较慢，但在巨大的气候资料列表插入删除在大数据集上速度快，但在小数据集上速度慢的

2019-10-30 07:53:40

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

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

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

2010-02-05 17:56:35

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

2010-02-05 17:56:32

当你想在容器之间移动对象时，你可以使用list::splice。

例如，一个图划分算法可以将常数数量的对象递归地划分到数量不断增加的容器中。对象应该初始化一次，并始终保持在内存中的相同位置。通过重新链接来重新排列比重新分配要快得多。

Edit: as libraries prepare to implement C++0x, the general case of splicing a subsequence into a list is becoming linear complexity with the length of the sequence. This is because splice (now) needs to iterate over the sequence to count the number of elements in it. (Because the list needs to record its size.) Simply counting and re-linking the list is still faster than any alternative, and splicing an entire list or a single element are special cases with constant complexity. But, if you have long sequences to splice, you might have to dig around for a better, old-fashioned, non-compliant container.

2010-02-05 18:22:18

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

2010-02-05 18:05:05

STL中的向量和列表

推荐文章

最新文章

标签