c++ - 使用向量类实现堆栈的链表与动态数组

Question

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

这让我想知道这是否适用于 C++（因为有一个向量类可以在插入新元素时自动调整大小）？

Answer 1

很难比较两者，因为它们的内存使用模式完全不同。

矢量调整大小

矢量根据需要动态调整自身大小。它通过分配新的内存块、将数据从旧块移动（或复制）到新块、释放旧块来实现这一点。在典型情况下，新块的大小是旧块的 1.5 倍（与流行的看法相反，在实践中 2 倍似乎很不寻常）。这意味着在重新分配的短时间内，它需要的内存大约是您实际存储的数据的 2.5 倍。其余时间，正在使用的“块”最少 2/3 ^rds满，最多完全满。如果所有尺寸的可能性相同，我们可以预期它平均约为^5/6。从另一个方向来看，我们可以预期大约 1/6^或大约 17% 的空间被“浪费”

当我们通过这样的常数因子调整大小时（而不是总是添加特定大小的块，例如以 4Kb 为增量增长），我们得到所谓的摊销常数时间加法。换句话说，随着数组的增长，调整大小的频率会呈指数下降。数组中的项目被复制的平均次数趋于一个常数（通常在 3 左右，但取决于您使用的增长因子）。

链表分配

使用链表，情况就大不相同了。我们从来没有看到调整大小，所以我们没有看到一些插入的额外时间或内存使用。同时，我们确实看到基本上一直在使用额外的时间和内存。特别是，链表中的每个节点都需要包含一个指向下一个节点的指针。根据节点中数据的大小与指针的大小相比，这可能会导致大量开销。例如，假设您需要一堆ints。int在一个与指针大小相同的典型情况下，这将意味着 50% 的开销——一直如此。指针大于_int; 两倍大小是相当常见的（64 位指针，32 位 int）。在这种情况下，您有大约 67% 的开销——也就是说，很明显，每个节点用于指针的空间是存储数据的两倍。

不幸的是，这通常只是冰山一角。在典型的链表中，每个节点都是单独动态分配的。至少如果您要存储小数据项（例如int），分配给节点的内存可能（通常会）甚至大于您实际请求的数量。所以——你要求 12 字节的内存来保存一个 int 和一个指针——但是你得到的内存块很可能被四舍五入到 16 或 32 字节。现在您看到的开销至少为 75%，很可能是 ~88%。

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

分配和管理大量内存块的成本很高。

缓存使用

最后，对于最近的处理器，我们遇到了另一个重要因素：缓存使用。在向量的情况下，我们将所有数据彼此相邻。然后，在使用中的向量部分结束后，我们有一些空内存。这导致了出色的缓存使用——我们正在使用的数据被缓存；我们不使用的数据对缓存几乎没有影响。

使用链表，指针（以及每个节点中可能的开销）分布在整个链表中。即，我们关心的每条数据旁边都有指针的开销，以及分配给我们不使用的节点的空白空间。简而言之，缓存的有效大小减少了与列表中每个节点的总体开销大致相同的因子——即，我们可能很容易看到只有 1/8^的缓存存储了我们关心的日期，并且7/8^用于存储指针和/或纯垃圾。

概括

当您的节点数量相对较少时，链表可以很好地工作，每个节点都非常大。如果（对于堆栈来说更典型）您正在处理相对大量的项目，每个项目都非常小，那么您不太可能看到时间或内​​存使用的节省。恰恰相反，对于这种情况，链表基本上更可能浪费大量时间和内存。

Answer 2

是的，你所说的对于 C++ 来说是正确的。由于这个原因，里面的默认容器std::stack，也就是C++中的标准栈类，既不是向量也不是链表，而是一个双端队列（a deque）。这几乎具有矢量的所有优点，但它可以更好地调整大小。

基本上，anstd::deque是 内部排序数组的链表。这样，当它需要调整大小时，它只是添加另一个数组。

Answer 3

首先，链表和动态数组之间的性能权衡比这要微妙得多。

根据要求，C++ 中的向量类被实现为“动态数组”，这意味着它必须具有摊销常数成本才能将元素插入其中。这通常是通过以几何方式增加数组的“容量”来完成的，也就是说，每当你用完（或接近用完）时，你就会将容量翻倍。最后，这意味着重新分配操作（分配新的内存块并将当前内容复制到其中）只会在少数情况下发生。在实践中，这意味着重新分配的开销仅在性能图上显示为对数间隔的小峰值。这就是“摊销不变”成本的含义，因为一旦你忽略了那些小尖峰，

在链表实现中，您没有重新分配的开销，但是，您确实有在 freestore（动态内存）上分配每个新元素的开销。因此，开销有点规律（不是尖峰，有时可能需要），但可能比使用动态数组更重要，特别是如果元素复制成本相当低（尺寸小，对象简单）。在我看来，链表只推荐用于复制（或移动）成本很高的对象。但归根结底，这是您需要在任何给定情况下测试的东西。

最后，重要的是要指出，对于任何广泛使用和遍历元素的应用程序，参考位置通常是决定因素。使用动态数组时，元素一个接一个地打包在内存中，并且进行中序遍历非常有效，因为 CPU 可以在读/写操作之前抢先缓存内存。在一个普通的链表实现中，从一个元素到下一个元素的跳转通常涉及在完全不同的内存位置之间的相当不稳定的跳转，这有效地禁用了这种“预取”行为。因此，除非列表的各个元素非常大并且对它们的操作通常执行时间很长，否则使用链表时缺乏预取将是主要的性能问题。

你可以猜到，我很少使用链表 ( std::list)，因为有利的应用程序的数量很少而且相差甚远。通常，对于大型且复制成本高的对象，通常最好简单地使用指针向量（您可以获得与链表基本相同的性能优势（和劣势），但内存使用量更少（用于链接指针)，如果需要，您可以获得随机访问功能)。

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

Answer 4

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

Answer 5

std::vector使用动态数组实现，而std::list实现为链表。使用这两种数据结构需要权衡取舍。选择最适合您需求的那一款。

• 正如您所指出的，如果动态数组已满，则添加项目可能会花费大量时间，因为它必须自行扩展。但是，它的访问速度更快，因为它的所有成员都在内存中组合在一起。这种紧密的分组通常也使它对缓存更加友好。

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

Answer 6

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

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

Answer 7

从C++ 文档：

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

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

这有效地将容器大小增加了 1，当且仅当新向量大小超过当前向量容量时，这会导致分配的存储空间的自动重新分配。

Answer 8

http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Keynote-Bjarne-Stroustrup-Cpp11-Style 跳到 44:40。std::vector正如视频中所解释的那样，您应该尽可能喜欢std::listBjarne 本人的 . 由于std::vector将所有元素彼此相邻地存储在内存中，因此它将具有缓存在内存中的优势。这对于添加和删除元素std::vector以及搜索也是如此。他说这std::list比std::vector.

如果你真的想要一个堆栈，你应该真正使用std::stack而不是自己制作。