使用向量类实现栈的时候，链表和动态数组哪个更好？

Question

我正在研究两种实现栈的不同方式：链表和动态数组。与动态数组相比，链表的主要优点是不需要调整大小，而如果插入的元素过多，动态数组必须调整大小，从而浪费大量时间和内存。

这让我想知道在C++中是否也是如此（因为有一个向量类，在插入新元素时会自动调整大小）。

- Computernerd

---

大多数动态数组在负载因子达到60-70％（满负荷）时会将其大小（支持数组的大小）加倍。使用这种增长模式可以最小化浪费的时间，重新分配和移动内存。虽然我不知道C ++向量类的具体细节。 - Justin

可能是重复的问题 https://dev59.com/KGs05IYBdhLWcg3wJ-yQ?rq=1 - miguel.martin

“因此浪费了很多时间和内存”并不是因为使用了很多时间（因为它是摊销常数时间），而是在调整大小和复制操作发生时需要付出大量的时间成本。就内存而言，根据您使用的乘数（它不必是二，1.4或1.5也很常见）以及链表中有效负载大小，动态数组可能在浪费空间方面具有竞争力。 - dmckee --- ex-moderator kitten

Answer 1

由于它们的内存使用模式非常不同，因此很难进行比较。

向量缩放

向量会根据需要动态地调整自己的大小。它通过分配一个新的内存块，将数据从旧块移动（或复制）到新块中，然后释放旧块来实现。在典型情况下，新块的大小是旧块的1.5倍（与普遍信仰相反，在实践中2倍似乎相当少见）。这意味着在重新分配期间的短时间内，它需要的内存大约等于实际存储的数据量的2.5倍。其余的时间，“块”中使用的部分至少填满了2/3，最多完全填满。如果所有大小可能性相等，那么我们可以预计平均填满大约为5/6。从另一个方向看，我们可以预计在任何给定时间大约有1/6或约17%的空间被“浪费”。

当我们像这样通过一个常数因子来调整大小时（而不是例如始终添加特定大小的块，如以4Kb增量增长），我们得到所谓的摊销常数时间添加。换句话说，随着数组的增长，重新调整大小发生的次数指数级地减少。数组中项目被复制的平均次数趋于常量（通常约为3，但取决于使用的增长因子）。

链表分配

使用链表时情况就有些不同了。我们从未见过调整大小，因此我们不会在某些插入时看到额外的时间或内存使用。同时，我们确实始终看到额外的时间和内存使用。特别是，链表中的每个节点都需要包含指向下一个节点的指针。根据节点中数据的大小与指针的大小比较，这会导致显着的开销。例如，假设您需要一个int类型的栈。在典型情况下，int与指针的大小相同，这意味着会出现50%的开销-始终如此。指针比int更大变得越来越常见；两倍的大小非常普遍（64位指针，32位int）。在这种情况下，您会面临约67%的开销-明显地，每个节点将指针占用的空间是要存储的数据的两倍。

不幸的是，这通常只是冰山一角。在典型的链表中，每个节点都是单独动态分配的。至少如果您正在存储小的数据项（例如int），则为节点分配的内存可能会比您实际请求的数量大（通常会这样）。因此，您请求12字节的内存来容纳一个int和一个指针，但您获得的内存块可能会被舍入到16或32字节。现在你看到至少有75%的额外开销，很可能是约88%。

就速度而言，情况十分相似：动态分配和释放内存通常非常缓慢。堆管理器通常具有一些空闲内存块，并需要花费时间在其中搜索以找到最适合您所请求大小的块。然后，它（通常）必须将该块分成两个部分，一个用于满足您的分配，另一个用于满足其他分配的剩余内存。同样，当您释放内存时，它通常返回到相同的空闲块列表，并检查是否已经有相邻的空闲内存块，以便将它们合并在一起。

分配和管理大量内存块是昂贵的。

最后，对于最近的处理器，我们遇到了另一个重要的因素：缓存使用。在向量的情况下，我们所有的数据都紧挨着彼此。然后，在向量中正在使用的部分结束后，我们有一些空闲内存。这导致了优秀的缓存使用-我们正在使用的数据会被缓存；我们没有使用的数据对缓存几乎没有影响。

对于链表，指针（和每个节点中可能的开销）分布在整个链表中。也就是说，我们关心的每个数据片段旁边都有指针的开销，并且用于我们不使用的节点的空间。简而言之，缓存的有效大小减少了每个节点总开销相同的因子-也就是说，我们可能会看到只有 1/8 的缓存存储我们关心的数据，7/8 存储指针和/或纯垃圾。

综上所述。

当你有相对较少、每个节点都很大的情况下，链表可以发挥良好作用。 如果（对于栈而言更加典型），你处理的是相对较多、每个项都很小的情况，那么你很可能不会在时间或内存使用方面看到节省。 相反，对于这种情况，链表更有可能浪费大量的时间和内存。

- Jerry Coffin

Answer 2

是的，你说的对，这对于C++是正确的。因此，在C++中使用的标准栈类std::stack内的默认容器既不是向量也不是链表，而是双端队列（deque）。这几乎具有向量的所有优点，但它的重新调整大小能力更好。

基本上，std::deque在内部是一种“数组的链接列表”。这样，当它需要重新调整大小时，它只需添加另一个数组。

- Gorpik

---

所以std:stack和vector类不同吗？ - Computernerd

是的。std::stack 实际上不是一个容器，而是一个使用内部容器实现的容器适配器。默认情况下，它使用 std::deque，但您可以使用任何容器。std::vector 是一个真正的容器。您可以拥有一个使用 std::vector 作为内部容器的 std::stack，但接口将会不同。 - Gorpik

Answer 3

首先，链表和动态数组之间的性能权衡往往比这更微妙。在C ++中，vector类必须作为“动态数组”实现，这意味着将元素插入其中必须具有摊销常数成本。通常的实现方式是以几何方式增加数组的“容量”，也就是说，当你用完（或接近用完）时，你会将容量加倍。最后，这意味着重新分配操作（分配新的内存块并将当前内容复制到其中）只会在少数几个情况下发生。实际上，这意味着重新分配的开销仅会显示在性能图表上的对数间隔处的小峰值中。这就是“摊销平均常数”成本的含义，因为一旦忽略这些小峰值，插入操作的成本基本上是恒定的（在这种情况下甚至可以说是微不足道的）。

在链表实现中，您没有重新分配的开销，但是您需要在freestore（动态内存）上分配每个新元素的开销。因此，开销要更加规则一些（不会像有时候那样出现尖峰），但是如果要复制的元素相当便宜（体积小且简单对象），则可能比使用动态数组更显着。在我看来，链表仅建议用于非常昂贵的对象（或移动）复制。但是到最后，在任何给定情况下这都需要进行测试。

最后，需要指出的重要问题是引用位置往往是使用和遍历元素的任何应用程序的决定性因素。在使用动态数组时，元素相互紧密地打包在内存中，依次遍历非常高效，因为CPU可以预测地缓存读/写操作之前的内存。在一个普通链接列表实现中，从一个元素跳到下一个元素通常涉及相当不规则的跃迁，这有效地禁用了这种“预取”行为。因此，除非列表的各个元素非常大且对它们的操作通常需要很长时间才能执行，否则使用链表时缺少预取将成为占主导地位的性能问题。

正如你猜到的，我很少使用链接列表(std :: list)，因为有利应用程序的数量很少。对于大型和昂贵的对象，通常最好只使用指针向量(您基本上获得与链接列表相同的性能优势(和劣势)，但使用较少的内存(用于链接指针)，并且如果需要，可以获得随机访问能力)。

我能想到的主要情况是，链表胜过动态数组（或类似std::deque的分段动态数组）的情况是当你需要经常在中间插入元素时（而不是在两端）。然而，这种情况通常发生在你需要保持排序（或按某种方式排序）的元素集合中，在这种情况下，你将使用树结构来存储元素（例如二叉搜索树（BST）），而不是链表。而且，这样的树通常使用半连续内存布局（例如广度优先布局）在一个动态数组或分段动态数组内存储它们的节点（元素）（例如一个缓存无关的动态数组）。

- Mikael Persson

Answer 4

是的，对于C++或任何其他语言都是正确的。动态数组是一个概念。C++有vector并不改变这个理论事实。在C++中的向量实际上会在内部进行调整大小，因此这项任务不是开发人员的责任。当使用vector时，实际成本并没有神奇地消失，而只是转移到了标准库实现。

- SomeWittyUsername

Answer 5

std::vector 是使用动态数组实现的，而 std::list 则是使用链表实现的。使用这两种数据结构都有权衡之处。选择最适合您需求的那一个。

• 正如您所指出的，如果动态数组已满，则添加项目需要更长的时间，因为它必须扩展自身。但是，由于所有成员都在内存中紧密分组，因此访问速度更快。这种紧密分组通常也使其更易于缓存。

• 链表永远不需要调整大小，但遍历它们需要更长的时间，因为 CPU 必须在内存中跳转。

- Matt Kline

Answer 6

这让我想知道在C++中是否也是这样，因为有一个向量类可以在插入新元素时自动调整大小。

是的，它仍然适用，因为vector的重新分配是一种潜在的昂贵操作。 在内部，如果向量的预分配大小达到并且您尝试添加新元素，则会发生新的分配，并且旧数据将移动到新的内存位置。

- Luchian Grigore

Answer 7

来自C++文档：

vector::push_back - 在末尾添加元素

在向量的末尾添加一个新元素，该元素位于当前最后一个元素之后。将val的内容复制（或移动）到新元素中。

这实际上通过一增加容器大小，如果新向量大小超过当前向量容量，则会自动重新分配已分配的存储空间。

- Svalorzen

Answer 8

http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style 跳到44:40。正如Bjarne在视频中所解释的那样，尽可能使用std::vector而不是std::list。由于std::vector将所有元素都存储在内存中的相邻位置，因此具有缓存在内存中的优势。这对于添加、删除和搜索std::vector中的元素都是适用的。他指出，std::list比std::vector慢50-100倍。

如果您真的需要一个堆栈，应该使用std::stack而不是自己编写。

- miguel.martin

---

所以std::vector和std::stack有什么不同？ - Computernerd

在C++中，std::stack被实现为一个适配器，因此您可以将容器传递给它，并使其作为堆栈工作。默认情况下，使用std::deque。http://www.cplusplus.com/reference/stack/stack/ - Svalorzen