Difference between list and forward_list performance?

Question

As with c++11 we have two types of list:

std::list<int> lst = { 1, 2, 3, 4, 5 };

std::forward_list<int> flst = { 5, 4, 3, 2, 1};

As we know that the list is based on the doubly linked list and forward_list is based on the singly linked list.

How should we decide which one to used? Is there any performance benefit of any of the list above other?

Answer 1

How should we decide which one to used?

Decide if you need bidirectional iteration. If forward iteration is good enough, use std::forward_list, unless you need to support C++ versions older than C++11, which may only have std::list.

Is there any performance benefit of any of the list above other?

std::forward_list eliminates a pointer per node (with all the attendant benefits for the data cache and memory subsystem), while std::list provides constant-time iterator decrement.

But in practice, neither of these containers is as widely used as one might believe when attending computer science school. The real performance of std::vector is superior for many applications, and its memory usage is always less. More demanding applications requiring lists would do well to consider intrusive lists, which standard C++ does not provide.

Answer 2

In addition to what john-zwinck said, if you have to use linked-lists, bear in mind the followings when making your decision:

std::forward_list doesn't have the modifiers functions operating at the end due to its nature:

push_back, pop_back, emplace_back

Furthermore, std::forward_list doesn't provide a size member function for more efficiency according to the std::list. size function of the std::list gives the number of elements in constant time by C++11. On the other hand, it requires some extra storage for the internal counter and this makes inserting and removing slightly less efficient. In order to attain the size of a std::forward_list, the distance algorithm can be used with begin() and end() functions but this operation takes linear time.