STL中的向量和列表

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

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

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

标准容器的复杂度保证是什么?< / >

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

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

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

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

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

为了更具体地回答你的问题，我将引用这个页面

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

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

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

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

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

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

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

编辑:当库准备实现c++ 0x时，将子序列拼接到列表的一般情况将随着序列的长度而变得线性复杂。这是因为splice(现在)需要遍历序列以计算其中的元素数量。(因为列表需要记录它的大小。)简单地计数和重新链接列表仍然比任何替代方法都快，拼接整个列表或单个元素是具有恒定复杂性的特殊情况。但是，如果需要拼接较长的序列，则可能需要寻找更好的、老式的、不兼容的容器。

一般来说，当你不关心你使用的是哪种类型的顺序容器时，使用vector，但如果你在容器的任何地方做很多插入或擦除，而不是在末尾，你就会想要使用list。如果你需要随机访问，你就需要向量，而不是列表。除此之外，在某些情况下，根据应用程序需要其中一个或另一个，但一般来说，这些都是很好的指导原则。

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

这是我的理解

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

这里的大多数答案都遗漏了一个重要的细节:为什么?

你想在集装箱里放些什么?

如果它是__abc0的集合，那么std::list将在每个场景中丢失，不管你是否可以重新分配，你只从前面删除，等等。遍历列表的速度较慢，每次插入都需要与分配器进行交互。要准备一个list<int>胜过vector<int>的例子是极其困难的。即使这样，deque<int>可能更好或接近，而不仅仅是使用列表，这将有更大的内存开销。

然而，如果你正在处理大而丑陋的数据块——而且很少——你不想在插入时过度分配，而由于重新分配而复制将是一场灾难——那么你可能，也许，使用list<UglyBlob>比vector<UglyBlob>更好。

尽管如此，如果你切换到vector<UglyBlob*>甚至vector<shared_ptr<UglyBlob> >， - list仍然会落后。

因此，访问模式、目标元素数量等仍然会影响比较，但在我看来，元素大小、复制成本等。

必须使用list的唯一硬规则是需要分配指向容器元素的指针。

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

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

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

在向量和列表的情况下，让我印象深刻的主要区别如下:

向量

向量将其元素存储在相邻内存中。因此,随机 访问是可能的在一个向量，这意味着访问 向量的元素运算非常快因为我们可以简单地乘以 使用项目索引来访问该元素的基址。事实上，它
由于vector基本上是对数组进行换行，每次插入 元素转换为vector(动态数组)时，它必须通过 寻找一个新的连续内存块来容纳新的

• 不消耗额外的内存来存储指向other的指针

列表

列表将其元素存储在非连续内存中。因此, 随机访问在列表中是不可能的，这意味着 访问它的元素，我们必须使用指针和遍历 这个列表相对于向量来说比较慢。这需要O(n)或线性时间 比O(1)慢。

• 由于列表使用的是非连续内存，所以插入一个数组所花费的时间 元素在列表中的使用要比在它的情况下高效得多

• 它消耗额外的内存来存储指向和之前元素的指针

因此，记住这些差异，我们通常考虑内存，频繁的随机存取和插入来决定给定场景中向量vs列表的获胜者。

向量,

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

列表,

1. List基于堆内存
2. 列表是非常庞大的数据集
3. list在遍历小数据集时相对较慢，但在 李巨大先于< / >
4. 列表插入删除在大型数据集上快速，但在较小数据集上缓慢 李的< / >

List是双链表，所以很容易插入和删除一个元素。我们只需要改变这几个指针，而在向量中如果我们想在中间插入一个元素那么它后面的每个元素都要移动一个下标。此外，如果向量的大小已满，那么它必须首先增加它的大小。所以这是一个昂贵的手术。 因此，无论在这样的case列表中需要更频繁地执行插入和删除操作，都应该使用

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