何时使用C++ forward_list

Question

我是C++的新手,并且阅读了"The C++ Programming Language(4th edition)"一书.阅读"STL容器"一章时,本书介绍了forward_list:

forward_list(单链表)基本上是针对空列表和非常短列表优化的列表.空的forward_list只占用一个单词.令人惊讶的是,大多数都是空的列表有很多用途(其余的都很短).

我想知道一份清单有多短暂考虑？谁能举一个简单的例子来利用forward_list？

Answer 1

一般来说,当您担心存储大小而不是随机访问迭代时,您希望使用类似转发列表的内容.这是一种可用于存储各种稀疏数据的数据结构.如果您有大量的条目是某些默认值,那么假设所有条目都是默认值会变得更便宜(就内存而言),除非明确指出它们不是.

我最后一次使用的forward_list是表示带有列表列表方法的稀疏矩阵.这节省了大量内存,因为只有非常少量的条目非零,并且矩阵的尺寸非常大.

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

Answer 2

这是std::list和中使用的节点结构std::forward_list:

struct _List_node      // list node
{   
  _Voidptr _Next;      // successor node, or first element if head
  _Voidptr _Prev;      // predecessor node, or last element if head
  _Value_type _Myval;  // the stored value, unused if head
};

struct _Flist_node     // forward_list node
{   
  _Voidptr _Next;      // successor node
  _Value_type _Myval;  // the stored value
};

空间计算:

sizeof(_List_node)  = 2 * sizeof(_Voidptr) + sizeof(_Value_type)
sizeof(_Flist_node) = 1 * sizeof(_Voidptr) + sizeof(_Value_type)

如果sizeof(_Value_type)相同或大致相等,sizeof(_Voidptr)那么我们有:

sizeof(_List_node)  ~ 3 * sizeof(_Voidptr)
sizeof(_Flist_node) ~ 2 * sizeof(_Voidptr)

如果sizeof(_Value_type)>> sizeof(_Voidptr)那么节省可以忽略不计.但是,使用forward_list空间节省约1.5倍来存储较小的对象(假设您不需要反向迭代器.)