何时使用 C++ forward_list
我是 C++ 的新手，正在阅读《C++ 编程语言(第 4 版)》一书.阅读《STL Containers》章节时，书中对forward_list有介绍:
I am kind of new to C++, and reading the book "The C++ Programming Language (4th edition)". When reading chapter of "STL Containers", the book has a introduction to forward_list:
forward_list(单链表)基本上是一个优化的列表对于空的和非常短的列表.一个空的 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?
I am wondering how short a list is considering short? And could anyone give a simple example to take the advantage of forward_list?
推荐答案
一般来说，当您关心存储大小而不是随机访问迭代时，您希望使用前向列表之类的东西.这是一种数据结构，可用于存储各种类型的稀疏数据.当您有大量具有某些默认值的条目时，假设所有条目都是默认值会变得更便宜(就内存而言)，除非明确指定它们不是.
Generally speaking you want to use something like a forward list when you are concerned about storage size more than you are about random access iteration. This is a data structure that you can use to store various types of sparse data. When you have a large number of entries that are some default value it becomes cheaper (in regards to memory) to assume that all entries are a default value unless explicitly specified that they are not.
我最后一次使用 forward_list 是用一个列表表示一个 稀疏矩阵方法.这节省了很多内存，因为只有极少数条目是非零的并且矩阵的维度非常大.
The last time I used forward_list was representing a sparse matrix with a list of lists approach. This saved a lot of memory because only a very small number of entries were non-zero and the dimensions of the matrices were very large.
假设您有一个具有大量顶点但没有大量边的图，可能有数百万个顶点(节点)但每个顶点最多只有 5 个边(连接).如果您尝试使用邻接矩阵(多维数组)将此图存储在内存中，则存储的大小将是 O(|v|^2) (其中 v 是顶点集).如果将它存储为一个数组，该数组是包含每个顶点的边列表的顶点长度，那么大小将是 O(|v|*|e|) (其中 e 是集合边缘).如果边的数量远远少于顶点(许多图就是这种情况)，那么使用边列表方法可能是一个不错的选择.在上面提到的这种情况下，|e| 最多为 5，因此内存节省是巨大的.通常，当您找到感兴趣的顶点时，您会先将与其相关的边加载到内存中，然后再开始对其进行操作.在这种情况下，这个想法主要是关于存储而不是随机访问迭代，所以如果你不使用它们，你不希望为大量的反向指针付费.对于这个 forward_list 将是一个合适的数据结构.
Say you have a graph with a very large number of vertices but not a large number of edges, perhaps there's millions of vertices (nodes) but each only has at most 5 edges(connections). If you were to try to store this graph in memory using an adjacency matrix (multidimensional array) the size of the storage would by O(|v|^2) (where v is the set of vertices). If you stored it as an array that was the length of the vertices containing a list of edges for each vertex then the size would be O(|v|*|e|) (where e is the set of edges). If there's vastly less edges than vertices, which is the case with many graphs then going with the list of edges approach can be a good choice. In this case mentioned above |e| is at most 5 so the memory savings are huge. Often when you find a vertex of interest you load the edges associated with it into memory before you start doing operations on it. The idea is mostly about storage and not random access iteration in this case, so you don't want to have to pay for a large number of pointers going backwards if you don't use them. For this forward_list would be an appropriate data structure to use.
相关文章