我在Effective STL中注意到，
vector是默认应该使用的序列类型。
这是什么意思？似乎忽略效率，vector都可以胜任任何工作。
请问有没有一种场景，vector不是可行选项而必须使用list的情况？
STL中的向量与列表有何区别？
307
- skydoor
4
8虽然这并非您所询问的内容，但值得指出的是，默认使用向量还意味着您可以轻松地与旧代码、C库或非模板库进行交互，因为向量只是指针和大小的“传统”动态数组的薄包装器。 - Roger Pate
28Bjarne Strostrup进行了一项测试，他生成了随机数并将它们分别添加到列表和向量中。插入操作使得列表/向量始终保持有序状态。尽管这通常是“列表领域”的问题，但向量的性能要比列表高得多。原因在于内存访问速度较慢，对于顺序数据缓存效果更好。这些内容都可以在他2012年的“GoingNative”主题演讲中找到。 - evading
5http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/ - Adam Burry
1如果你想看@evading提到的Bjarne Stroustrup的主题演讲，我在这里找到了它：https://youtu.be/OB-bdWKwXsU?t=2672 - brain56
17个回答
7
将答案总结成表格以便快速参考：
| 向量 | 列表 | |
|---|---|---|
| 访问 | 更快 | 较慢 |
| 插入/删除操作 | 较慢 | 更快 |
| 内存分配 | 连续的 | 非连续的 |
| 预先分配空间大小 | 需要保留 | 不需要保留 |
| 每个元素所需空间 | 仅为元素本身 | 包括指向下一个（和可选的前一个）元素的指针 |
- Frida Schenker
5
在向量和链表的情况下，我注意到的主要区别如下：
向量
- 向量将其元素存储在连续的内存中。因此，在向量内部进行随机访问是可能的，这意味着访问向量的一个元素非常快，因为我们只需将基地址与项索引相乘即可访问该元素。实际上，这仅需要O（1）或常数时间。 - 由于向量基本上包装了一个数组，每次将一个元素插入向量（动态数组）时，它都必须通过查找新的连续内存块来调整大小以容纳新的元素，这是耗时的。 - 它不会消耗额外的内存来存储指向其中其他元素的任何指针。
链表
- 链表将其元素存储在非连续的内存中。因此，在链表内部进行随机访问是不可能的，这意味着要访问其元素，我们必须使用指针并遍历链表，这相对于向量而言速度较慢。这需要O（n）或线性时间，比O（1）慢得多。 - 由于链表使用非连续内存，插入元素的时间比其向量对应物的情况更为高效，因为避免了内存的重新分配。 - 它消耗额外的内存来存储指向特定元素之前和之后的元素的指针。
因此，考虑到这些差异，我们通常考虑内存、频繁的随机访问和插入来决定在给定情况下“向量 vs 链表”的胜者。
向量
- 向量将其元素存储在连续的内存中。因此，在向量内部进行随机访问是可能的，这意味着访问向量的一个元素非常快，因为我们只需将基地址与项索引相乘即可访问该元素。实际上，这仅需要O（1）或常数时间。 - 由于向量基本上包装了一个数组，每次将一个元素插入向量（动态数组）时，它都必须通过查找新的连续内存块来调整大小以容纳新的元素，这是耗时的。 - 它不会消耗额外的内存来存储指向其中其他元素的任何指针。
链表
- 链表将其元素存储在非连续的内存中。因此，在链表内部进行随机访问是不可能的，这意味着要访问其元素，我们必须使用指针并遍历链表，这相对于向量而言速度较慢。这需要O（n）或线性时间，比O（1）慢得多。 - 由于链表使用非连续内存，插入元素的时间比其向量对应物的情况更为高效，因为避免了内存的重新分配。 - 它消耗额外的内存来存储指向特定元素之前和之后的元素的指针。
因此，考虑到这些差异，我们通常考虑内存、频繁的随机访问和插入来决定在给定情况下“向量 vs 链表”的胜者。
- Ardent Coder
4
保持迭代器的有效性是使用列表的原因之一。另一个原因是当您不希望向向量推送项时重新分配内存。这可以通过智能使用reserve()来管理，但在某些情况下，仅使用列表可能更容易或更可行。
- John Dibling
4
当你想要在容器之间移动对象时，可以使用
例如，图分割算法可能会将一定数量的对象递归地分配到越来越多的容器中。这些对象应该被初始化一次，并始终保持在内存中相同的位置。通过重新链接而不是重新分配，重新排列它们要快得多。 编辑：随着库准备实现C++0x，将子序列拼接到列表中的一般情况正在变为与序列长度成线性复杂度。这是因为
list::splice。例如，图分割算法可能会将一定数量的对象递归地分配到越来越多的容器中。这些对象应该被初始化一次，并始终保持在内存中相同的位置。通过重新链接而不是重新分配，重新排列它们要快得多。 编辑：随着库准备实现C++0x，将子序列拼接到列表中的一般情况正在变为与序列长度成线性复杂度。这是因为
splice（现在）需要迭代整个序列以计算其中元素的数量。（因为列表需要记录其大小。）仅计数并重新链接列表仍然比任何其他替代方案更快，并且拼接整个列表或单个元素是具有常量复杂度的特殊情况。但是，如果您需要拼接长序列，则可能需要寻找更好的、老式的、非兼容的容器。- Potatoswatter
3
唯一强制使用
（从技术上讲，
其他软性规则与将元素插入容器中间时可能出现的性能问题有关，在这种情况下，
list的硬性规定是在需要分配容器元素的指针时。与vector不同，您知道元素的内存不会被重新分配。如果可能会重新分配，则可能存在对未使用内存的指针，这最多是一个大忌，最坏的情况下是一个SEGFAULT。（从技术上讲，
*_ptr的vector也可以工作，但在这种情况下，您正在模拟list，因此这只是语义上的问题。）其他软性规则与将元素插入容器中间时可能出现的性能问题有关，在这种情况下，
list更可取。- iPherian
1
列表只是STL中双向链表的包装器，因此提供了您可能从D-Linklist中期望的功能，即O（1）插入和删除。而向量是一种连续的数据序列，类似于动态数组。P.S-更容易遍历。
- Ritankar Paul
0
列表是双向链表，因此插入和删除元素很容易。我们只需要改变一些指针，而在向量中，如果我们想在中间插入一个元素，则其后的每个元素都必须向右移动一个索引。此外，如果向量的大小已满，则必须先增加其大小。因此，这是一项昂贵的操作。 因此，在需要更频繁执行插入和删除操作的情况下，应使用列表。
- Siddesh Pawar
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接