我对 C++ 有点陌生，正在阅读《C++ 编程语言（第 4 版）》一书。在阅读《STL Containers》章节时，书中对forward_list有介绍：
forward_list（单链表）基本上是一个优化的列表
对于空的和非常短的列表。空的forward_list只占用
一个词。令人惊讶的是，列表有很多用途，其中大多数用途是
空（其余部分都很短）。
我想知道一个列表有多短才算短？谁能举一个简单的例子来利用forward_list？
一般来说，当您更关心存储大小而不是随机访问迭代时，您希望使用类似前向列表的东西。
这是一种可用于存储各种类型的稀疏数据的数据结构。当您有大量具有某些默认值的条目时，假设所有条目都是默认值会更便宜（就内存而言），除非明确指定它们不是默认值。
我上次使用的时候forward_list代表的是稀疏矩阵 http://en.wikipedia.org/wiki/Sparse_matrix使用列表列表方法。这节省了大量内存，因为只有极少量的条目是非零的，并且矩阵的维度非常大。
假设您有一个具有大量顶点但没有大量边的图，也许有数百万个顶点（节点），但每个顶点最多只有 5 个边（连接）。如果您尝试使用邻接矩阵（多维数组）将此图存储在内存中，则存储的大小将是O(|v|^2)（其中 v 是顶点集）。如果将其存储为数组，该数组是包含每个顶点的边列表的顶点长度，则大小将为O(|v|*|e|)（其中 e 是边的集合）。如果边的数量远远少于顶点（许多图都是这种情况），那么使用边列表方法可能是一个不错的选择。在上面提到的这种情况下|e|最多 5 个，因此节省的内存是巨大的。通常，当您找到感兴趣的顶点时，您会先将与其关联的边加载到内存中，然后再开始对其进行操作。在这种情况下，这个想法主要是关于存储而不是随机访问迭代，因此如果您不使用它们，您不想为大量向后的指针付费。为了这forward_list将是一个合适的数据结构。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
