STL中的向量与列表有何区别？

Question

STL中的向量与列表有何区别？

c++listvectorstl

307

我在Effective STL中注意到，

vector是默认应该使用的序列类型。

这是什么意思？似乎忽略效率，vector都可以胜任任何工作。

请问有没有一种场景，vector不是可行选项而必须使用list的情况？

- skydoor

8

虽然这并非您所询问的内容，但值得指出的是，默认使用向量还意味着您可以轻松地与旧代码、C库或非模板库进行交互，因为向量只是指针和大小的“传统”动态数组的薄包装器。 - Roger Pate

28

Bjarne Strostrup进行了一项测试，他生成了随机数并将它们分别添加到列表和向量中。插入操作使得列表/向量始终保持有序状态。尽管这通常是“列表领域”的问题，但向量的性能要比列表高得多。原因在于内存访问速度较慢，对于顺序数据缓存效果更好。这些内容都可以在他2012年的“GoingNative”主题演讲中找到。 - evading

5

http://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个回答

120

当你想要反复地向序列中除了末尾以外的任何位置插入大量项目时，即需要进行大规模插入操作。

请查看每个不同类型容器的复杂度保证：

标准容器的复杂度保证是什么？

- Martin York

2

在末尾插入元素也是计算内存分配和元素复制成本的，因此也要考虑。而且，在向量的开头插入元素几乎是不可能的，但是list有push_front方法。 - Notinlist

9

不，向向量末尾插入元素是摊销常数时间的。内存分配只会偶尔发生，并且可以预先为向量分配内存以防止它发生。当然，如果你必须保证插入操作始终以恒定的时间完成，那么这仍然是一个问题。 - Brian

18

@Notinlist - 对于你来说，以下内容是否“几乎不可能”？v.insert(v.begin(), i) （注：此处为代码语句，意为在向量v的开头插入元素i） - Manuel

6

我同意你的看法，只是我不希望原帖作者觉得界面不存在，以为可以随意自毁。 - Manuel

16

Bjarne Strostrup实际上进行了一项测试，他生成了随机数并将它们分别添加到列表和向量中。插入操作是按顺序进行的，以确保列表/向量始终有序。尽管这通常是“列表领域”的操作，但向量的性能要比列表高得多。原因是内存访问速度较慢，缓存对于顺序数据的效果更好。这些内容都可以在他2012年“GoingNative”大会上的主题演讲中找到。 - evading

显示剩余8条评论

41

如果您不需要频繁插入元素，那么向量会更加高效。它比列表具有更好的CPU缓存局部性。换句话说，访问一个元素使得下一个元素非常可能位于缓存中，并且可以在无需读取缓慢的RAM的情况下检索。

- Hans Passant

40

大多数回答都忽略了一个重要的细节：为什么使用容器？

您想要保存什么在容器中？

如果是一组int，则无论何时，std :: list都会失败，无论您是否可以重新分配，仅从前面删除等。列表遍历速度较慢，每次插入都会消耗与分配器的交互。几乎不可能准备一个示例，在其中>击败>。即使这样，deque 也可能更好或接近，不能证明使用列表，它将具有更大的内存开销。

但是，如果您处理大量丑陋的数据块 - 并且其中很少有数据块 - 当插入时不想过度分配，并且由于重新分配而进行复制将是一场灾难 - 那么也许您更适合使用>而不是>。

即使如此，如果您切换到vector 甚至是vector >>，列表也会落后。

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

- Tomasz Gandor

2

在阅读 Meyers 的《Effective STL》时，我又有了一个反思：list<T> 的一个特殊属性是可以在 O(1) 时间内进行 splice 操作。如果您需要常数时间的拼接操作，那么 list 也可能是最佳选择的数据结构 ;) - Tomasz Gandor

1

+1 - 它甚至不必是一个UglyBlob -- 即使只有几个字符串成员的对象也很容易在复制时产生禁止的高昂成本，因此重新分配一定会代价高昂。另外：不要忽略指数增长的空间开销，这可能会导致包含几十字节大小对象的vector。（如果您无法提前reserve）。 - Martin Ba

1

关于 vector<smart_ptr<Large>> 和 list<Large> -- 我会这么说，如果你需要随机访问元素，那么使用 vector 是有意义的。如果不需要随机访问，则使用 list 更为简单，而且性能也同样好。 - Martin Ba

39

简化问题：
当你在C++中选择容器时，如果感到困惑，请使用以下流程图（感谢我）：-

Vector-

vector基于连续的内存
对于小数据集，vector是最好的选择
在遍历数据集时，vector的性能最快
对于巨大的数据集，vector的插入和删除速度较慢，但对于非常小的数据集速度很快

List-

list基于堆内存
对于非常大的数据集，list是最好的选择
在遍历小数据集时，list相对较慢，但在遍历巨大数据集时很快
对于巨大的数据集，list的插入和删除速度很快，但对于较小的数据集速度较慢

- AtiqGauri

RE列表4。您应该提到它相对快/慢。对于列表，元素数量多少并不影响速度。 - infinitezero

向量内容存储在堆上（除非您使用指向堆上内容的指针存储在堆上的vector<Type*> vect）。为什么不能将vector用于非常大的数据集？ - jth_92

22

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

或者，如果您的内容非常昂贵而无法复制，例如，使用list对集合进行排序可能更便宜。

还要注意，如果集合很小（且内容不太昂贵），则向任何位置插入和删除元素时vector仍然可能比list更高效。列表单独分配每个节点，这可能比移动几个简单对象要费用更高。

我认为没有非常严格的规则。这取决于您想要使用容器做什么，以及您期望容器的大小和包含类型的大小。一般情况下，vector比list更好，因为它将其内容分配为单个连续块（基本上是一个动态分配的数组，在大多数情况下，数组是持有一堆东西最有效的方式）。

- UncleBens

1

+1. 拼接经常被忽视，但不幸的是它并不像期望的那样是常数时间。:(( （如果list::size是常数时间，则无法实现。） - Roger Pate

我非常确定list::size是（允许）线性的，正是出于这个原因。 - UncleBens

1

@Roger：list::size 不一定是常数时间。请参见 https://dev59.com/GHVC5IYBdhLWcg3woSxW 和 http://gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html。 - Potatoswatter

@Potatoswatter：标准的模糊性使得你不能依赖“兼容”的实现，这使问题变得更加严重。你必须避免使用stdlib才能获得可移植和可靠的保证。 - Roger Pate

@Roger：是的，不幸的是。我的当前项目强烈依赖于splice操作，而该结构几乎是纯C。更不幸的是，在N3000序列中，不同列表之间的splice被指定为线性复杂度，而size则明确为常数。因此，为了适应那些迭代size或其他内容的新手，STL或任何“兼容”的容器都无法使用一整类算法。 - Potatoswatter

15

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

这是我的理解：

列表：每个项目都包含一个到下一个或前一个元素的地址，因此通过这个功能，即使它们未排序，您也可以随机排列项目，顺序不会改变：如果您的内存是分散的，则效率很高。但是它还有另一个非常大的优点：您可以轻松地插入/删除项目，因为您唯一需要做的就是更改一些指针。缺点：要阅读单个随机项，您必须从一个项目跳转到另一个项目，直到找到正确的地址。

向量：使用向量时，内存更像普通数组组织：每个n-th项存储在第（n-1）个项之后，在第（n+1）个项之前。为什么它比列表更好？因为它允许快速随机访问。方法如下：如果您知道向量中项目的大小，并且它们在内存中是连续的，那么您可以轻松预测第n个项目在哪里；您不必浏览列表的所有项目以读取您想要的那个，使用向量可以直接读取，使用列表则不能。另一方面，修改向量数组或更改值要慢得多。

列表更适合跟踪可以在内存中添加/删除的对象。向量更适合当您想从大量单个项目中访问元素时。

我不知道列表是如何优化的，但您必须知道，如果您想要快速的读取访问，应该使用向量，因为无论STL多么好地加速了列表，它在读取访问方面都不像向量那样快。

- jokoon

“修改向量数组或更改值的速度要慢得多” - 从字面上看，这似乎与您之前提到的向量由于其低级和连续性而具有良好性能的说法相矛盾。您是不是指由于更改其大小而导致重新分配vector可能会很慢？如果是这样，那么我同意，但在可以使用reserve()的情况下，可以避免这些问题。 - underscore_d

11

任何时候，您都不能使迭代器无效。

- dirkgently

3

在得出迭代器无法解决问题的结论之前，请先询问是否使用指向“deque”的持久化引用就足够了。 - Potatoswatter

10

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

在列表中，数据存储在不相关的内存位置中。在中间插入数据不涉及复制部分数据以腾出新空间。

更具体地回答您的问题，我会引用此页面。

向量通常是访问元素、添加或删除序列末尾元素的时间效率最高的数据结构。对于涉及在末尾以外位置插入或删除元素的操作，它们的性能不如双端队列和列表，并且迭代器和引用比列表不够一致。

- f4.

7

当你需要在序列中间进行大量插入或删除，例如内存管理器时。

- Khaled Alshaya

它们之间的区别只是效率问题，而不涉及功能问题。 - skydoor

它们都是对一系列元素进行建模。正如@dirkgently所提到的，使用上有一点小差别，但你需要根据你的“常见操作”的复杂度来决定选择哪种序列（参考@Martin的回答）。 - Khaled Alshaya

@skydoor - 有一些功能上的区别。例如，只有向量支持随机访问（即可以索引）。 - Manuel

2

@skydoor：效率转化为性能。糟糕的性能可能会破坏功能。毕竟，性能是C++的优势。 - Potatoswatter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonathan M Davis · Accepted Answer

std::vector	std::list
连续的内存。	非连续的内存。
为未来元素预先分配空间，因此除了元素本身所需的空间外，需要额外的空间。	没有预先分配的内存。列表本身的内存开销是恒定的。
每个元素仅需要该元素类型本身的空间（无需额外的指针）。	每个元素都需要额外的空间用于保存持有元素的节点，包括指向列表中下一个和前一个元素的指针。
当添加元素时，可以随时重新分配整个向量的内存。	仅添加元素时不必重新分配整个列表的内存。
在结尾处进行插入具有常数摊销时间，但在其他地方进行插入的时间成本很高（O(n)）。	无论列表中插入或删除发生在何处，它们都很便宜。
向量末尾的删除具有常数时间，但对于其余部分，其时间成本为O(n)。	使用splice可以轻松地合并列表。
您可以随机访问其元素。	您无法随机访问元素，因此访问列表中特定元素可能很昂贵。
如果向量添加或删除元素，则迭代器将无效。	即使在向列表添加或删除元素时，迭代器也保持有效。
如果需要元素的数组，则可以轻松获取底层数组。	如果需要元素的数组，则必须创建一个新数组并将所有元素添加到其中，因为没有底层数组。

一般情况下，如果您不关心使用哪种类型的顺序容器，则使用vector，但是如果您需要对容器中除末尾以外的任何位置进行多次插入或删除操作，则应使用list。或者，如果您需要随机访问，则应使用vector而不是list。除此之外，在实际应用中，基于您的需求，可能需要使用其中一种，但总体而言，这些都是很好的指导方针。