When to use C++ forward_list

Question

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:

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).

I am wondering how short a list is considering short? And could anyone give a simple example to take the advantage of forward_list?

Answer 1

Here is the node structure used in the std::list and 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
};

Space calculation:

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

if sizeof(_Value_type) is same or approximately equal to sizeof(_Voidptr) then we have:

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

If sizeof(_Value_type) >> sizeof(_Voidptr) then the savings is negligible. But for storing smaller objects using forward_list has ~1.5x savings in space (provided you don't need a reverse iterator.)

Answer 2

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.

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.

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.