何时使用C ++ forward_list [英] When to use C++ forward_list

查看:91
本文介绍了何时使用C ++ forward_list的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我是C ++的新手,正在阅读《 C ++编程语言(第四版)》一书。在阅读 STL容器一章时,该书对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.

这篇关于何时使用C ++ forward_list的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆