c++ - 何时使用 C++ forward_list

Question

我是 C++ 的新手，正在阅读《C++ 编程语言(第 4 版)》一书。阅读《STL Containers》章节时，书中对forward_list有介绍:

A forward_list (a singly-linked list) is basically a list optimized for empty and very short lists. An empty forward_list takes up only one word. There are surprisingly many uses for lists where most are empty (and the rest are very short).

我想知道一个列表有多短？谁能举一个简单的例子来利用forward_list？

Answer 1

一般来说，当您关心存储大小而不是随机访问迭代时，您希望使用前向列表之类的东西。这是一种数据结构，可用于存储各种类型的稀疏数据。当您有大量具有某些默认值的条目时，假设所有条目都是默认值会变得更便宜(就内存而言)，除非明确指定它们不是。

我最后一次使用 forward_list 代表的是 sparse matrix使用列表方法。这节省了很多内存，因为只有极少数条目是非零的并且矩阵的维度非常大。

假设您有一个具有大量顶点但没有大量边的图，可能有数百万个顶点(节点)但每个顶点最多只有 5 个边(连接)。如果您尝试使用邻接矩阵(多维数组)将此图存储在内存中，则存储大小将由 O(|v|^2) (其中 v 是顶点集) .如果将它存储为一个数组，该数组是包含每个顶点的边列表的顶点长度，那么大小将为 O(|v|*|e|) (其中 e 是集合边缘)。如果边的数量远远少于顶点(许 multimap 就是这种情况)，那么使用边列表方法可能是一个不错的选择。在上面提到的这种情况下，|e| 最多为 5，因此内存节省是巨大的。通常，当您找到感兴趣的顶点时，您会先将与其相关的边加载到内存中，然后再开始对其进行操作。在这种情况下，这个想法主要是关于存储而不是随机访问迭代，所以如果你不使用它们，你不希望为大量的反向指针付费。对于这个 forward_list 将是一个合适的数据结构。