我在 Effective STL 中注意到
vector 是默认情况下应该使用的序列类型。
这是什么意思？似乎忽略效率vector可以做任何事情。
谁能给我一个vector不是可行选项但必须使用list的场景？
向量：
连续记忆。
为将来的元素预先分配空间，因此需要超出元素本身所需的额外空间。
每个元素只需要元素类型本身的空间（没有额外的指针）。
可以在添加元素的任何时候为整个向量重新分配内存。
最后的插入是恒定的，摊销的时间，但其他地方的插入是一个代价高昂的 O(n)。
向量末尾的擦除是常数时间，但其余时间为 O(n)。
您可以随机访问其元素。
如果您在向量中添加或删除元素，迭代器将失效。
如果您需要元素数组，则可以轻松获取底层数组。
列表：
非连续内存。
没有预先分配的内存。列表本身的内存开销是恒定的。
每个元素都需要额外的空间用于保存该元素的节点，包括指向列表中下一个和前一个元素的指针。
永远不必仅仅因为添加一个元素就为整个列表重新分配内存。
插入和擦除无论出现在列表中的哪个位置都很便宜。
将列表与拼接结合起来很便宜。
您不能随机访问元素，因此获取列表中的特定元素可能会很昂贵。
即使您从列表中添加或删除元素，迭代器仍然有效。
如果您需要一个元素数组，则必须创建一个新元素并将它们全部添加到其中，因为没有底层数组。
一般来说，当你不关心你使用的是什么类型的顺序容器时，使用向量，但是如果你在容器中的任何地方进行多次插入或擦除而不是末端，你会想要使用列表。或者，如果您需要随机访问，那么您将需要向量，而不是列表。除此之外，在某些情况下，您自然会根据您的应用程序需要其中一种，但总的来说，这些都是很好的指导方针。
您希望将大量项目重复插入序列末尾以外的任何位置的情况。
查看每种不同类型容器的复杂性保证：
What are the complexity guarantees of the standard containers?
list 有 push_front
如果您不需要经常插入元素，那么向量会更有效。它比列表具有更好的 CPU 缓存局部性。换句话说，访问一个元素使得下一个元素很可能存在于缓存中，并且可以在无需读取慢速 RAM 的情况下进行检索。
这里的大多数答案都错过了一个重要的细节：为什么？
你想在容器里放什么？
如果它是 int 的集合，那么 std::list 在每种情况下都会丢失，无论您是否可以重新分配，您只能从前面删除，等等。列表的遍历速度较慢，每次插入都会花费您与分配器。准备一个 list<int> 击败 vector<int> 的示例将非常困难。即便如此，deque<int> 可能更好或更接近，而不是使用列表，这将有更大的内存开销。
但是，如果您正在处理大而丑陋的数据块 - 而且其中很少 - 您不想在插入时过度分配，并且由于重新分配而复制将是一场灾难 - 那么您可能会更好list<UglyBlob> 比 vector<UglyBlob>。
不过，如果您再次切换到 vector<UglyBlob*> 甚至 vector<shared_ptr<UglyBlob> > - list 将落后。
因此，访问模式、目标元素计数等仍然会影响比较，但在我看来 - 元素大小 - 复制成本等。
list<T> 的一个特殊属性是 O(1) 中的 splice 的可能性。如果您需要恒定时间拼接，列表也可能是选择的结构；）
UglyBlob - 即使是只有几个字符串成员的对象也很容易复制起来非常昂贵，因此重新分配将成本。另外：不要忽略 vector 持有几十字节大小的对象的指数增长可能导致的空间开销（如果您不能提前 reserve）。
vector<smart_ptr<Large>> 与 list<Large> - 我想说，如果您需要随机访问元素，vector 是有意义的。如果您不需要随机访问，list 似乎更简单，并且性能应该相同。
让它变得简单 - 最终，当您在 C++ 中选择容器时感到困惑时，请使用此流程图图像（感谢我）：-
https://i.stack.imgur.com/Px7uf.png
向量-
向量是基于传染性内存的向量是小数据集向量执行最快的方法，而遍历数据集向量插入删除在大数据集上很慢，但对非常小的数据集很快
列表-
列表基于堆内存 列表是非常大的数据集的方法 列表在遍历小数据集时相对较慢，但在大数据集时速度较快 列表插入删除在大数据集上很快，但在较小数据集上较慢
std::list 的一项特殊功能是拼接（将部分或整个列表链接或移动到不同的列表中）。
或者，如果您的内容复制起来非常昂贵。在这种情况下，例如使用列表对集合进行排序可能会更便宜。
另请注意，如果集合很小（并且复制内容不是特别昂贵），即使您在任何地方插入和擦除，向量仍可能优于列表。列表单独分配每个节点，这可能比移动一些简单的对象要昂贵得多。
我不认为有非常严格的规则。这取决于您最想对容器做什么，以及您期望容器有多大和包含的类型。向量通常胜过列表，因为它将其内容分配为单个连续块（它基本上是一个动态分配的数组，在大多数情况下，数组是保存一堆东西的最有效方式）。
list::size 不一定是恒定时间。请参阅 stackoverflow.com/questions/228908/is-listsize-really-on 和 gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html
splice 被指定为线性复杂度，而 size 是特别恒定的。因此，为了适应在 size 或其他任何东西上进行迭代的新手，一整类算法对于 STL 或任何“兼容”容器时期都是遥不可及的。
好吧，我班的学生似乎无法向我解释什么时候使用向量更有效，但是在建议我使用列表时他们看起来很高兴。
我是这样理解的
列表：每个项目都包含一个指向下一个或前一个元素的地址，因此使用此功能，您可以随机化项目，即使它们没有排序，顺序也不会改变：如果您的内存是碎片化的，它会很有效。但它还有一个非常大的优势：您可以轻松插入/删除项目，因为您唯一需要做的就是更改一些指针。缺点：要读取随机的单个项目，您必须从一个项目跳到另一个项目，直到找到正确的地址。
向量：使用向量时，内存的组织方式更像常规数组：每个第 n 项存储在第 (n-1) 项之后和第 (n+1) 项之前。为什么它比 list 更好？因为它允许快速随机访问。方法如下：如果您知道向量中某个项目的大小，并且它们在内存中是连续的，则可以轻松预测第 n 个项目的位置；您不必浏览列表的所有项目来阅读您想要的项目，使用矢量，您可以直接阅读它，使用您无法阅读的列表。另一方面，修改向量数组或改变一个值要慢得多。
列表更适合跟踪可以在内存中添加/删除的对象。当您想从大量单个项目中访问一个元素时，向量更合适。
我不知道列表是如何优化的，但你必须知道，如果你想要快速读取访问，你应该使用向量，因为 STL 对列表的紧固有多好，它在读取访问时不会比向量快。
vector 由更改其 size 引起的可能很慢？然后同意，但在可以使用 reserve() 的情况下，可以避免这些问题。
任何时候你都不能让迭代器失效。
deque 中是否足够，就不要贸然下关于迭代器的结论。
基本上，向量是具有自动内存管理的数组。数据在内存中是连续的。试图在中间插入数据是一项代价高昂的操作。
在列表中，数据存储在不相关的内存位置。在中间插入并不涉及复制一些数据来为新数据腾出空间。
为了更具体地回答您的问题，我将引用 this page
对于访问元素以及从序列末尾添加或删除元素，向量通常是最有效的时间。对于涉及在结尾以外的位置插入或删除元素的操作，它们的性能比双端队列和列表差，并且迭代器和引用的一致性不如列表。
当您在序列中间有很多插入或删除时。例如内存管理器。
对于向量和列表，我认为的主要区别如下：
向量
向量将其元素存储在连续内存中。因此，在向量内部可以进行随机访问，这意味着访问向量的元素非常快，因为我们可以简单地将基地址乘以项目索引来访问该元素。事实上，这个目的只需要 O(1) 或恒定的时间。
由于向量基本上包装了一个数组，因此每次将元素插入向量（动态数组）时，它都必须通过找到一个新的连续内存块来调整自身大小以容纳新元素，这非常耗时。
它不会消耗额外的内存来存储指向其中其他元素的任何指针。
列表
列表将其元素存储在非连续内存中。因此，在列表内不可能进行随机访问，这意味着要访问其元素，我们必须使用指针并遍历相对于向量较慢的列表。这需要 O(n) 或比 O(1) 慢的线性时间。
由于列表使用非连续内存，因此在列表中插入元素所花费的时间比在其对应向量的情况下要高效得多，因为避免了内存的重新分配。
它消耗额外的内存来存储指向特定元素之前和之后的元素的指针。
因此，牢记这些差异，我们通常会考虑内存、频繁的随机访问和插入来决定给定场景中向量与列表的胜者。
在表格中总结答案以供快速参考：
向量列表访问更快更慢插入/删除操作更慢更快内存分配连续非连续大小预分配需要保留不需要保留每个元素所需的空间仅用于元素本身对于元素和指向下一个（以及可选的前一个元素）的指针
保持迭代器的有效性是使用列表的一个原因。另一个是当您不希望在推送项目时重新分配向量时。这可以通过智能使用 reserve() 来管理，但在某些情况下，仅使用列表可能更容易或更可行。
当您想在容器之间移动对象时，可以使用 list::splice。
例如，图分区算法可能具有在数量不断增加的容器中递归划分的恒定数量的对象。对象应该被初始化一次并且总是保持在内存中的相同位置。通过重新链接重新排列它们比重新分配要快得多。
编辑：随着库准备实现 C++0x，将子序列拼接到列表中的一般情况随着序列的长度而变得线性复杂。这是因为 splice（现在）需要遍历序列以计算其中的元素数。 （因为列表需要记录它的大小。）简单地计算和重新链接列表仍然比任何替代方法都快，拼接整个列表或单个元素是具有恒定复杂性的特殊情况。但是，如果你有很长的序列要拼接，你可能不得不四处寻找更好的、老式的、不兼容的容器。
必须使用 list 的唯一硬性规则是您需要分配指向容器元素的指针。
与 vector 不同，您知道元素的内存不会被重新分配。如果可以，那么您可能有指向未使用内存的指针，这充其量是一个很大的禁忌，最坏的情况是 SEGFAULT。
（从技术上讲，*_ptr 的 vector 也可以，但在这种情况下，您正在模拟 list，所以这只是语义。）
其他软规则与将元素插入容器中间可能出现的性能问题有关，因此 list 更可取。
列表只是 stl 中双链表的包装器，因此提供了您可能期望从 d-linklist 中获得的功能，即 O(1) 插入和删除。虽然向量是具有传染性的数据序列，其工作方式类似于动态数组。PS- 更容易遍历。
List 是双向链表，因此很容易插入和删除元素。我们只需要更改几个指针，而在向量中，如果我们想在中间插入一个元素，那么它后面的每个元素都必须移动一个索引。此外，如果向量的大小已满，则必须首先增加其大小。所以这是一项昂贵的手术。因此，在这种情况下，只要需要更频繁地执行插入和删除操作，就应该使用列表。
关注公众号
不定期副业成功案例分享
reserve()将其减少到 O(1)。将新项目添加到列表（即不拼接它们）执行 O(n) 自由存储分配。list会释放内存，而vector不会。当您减小vector的大小时，它不会减少其容量，除非您使用swap()技巧。