STL Containers: Forward list
Syntax
Defined in header <forward_list>
|
1 2 3 4 |
template< class T, class Allocator = std::allocator<T> > class forward_list; |
Definitions
List definition
|
1 2 3 4 5 |
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 }; |
Forward list definition
|
1 2 3 4 |
struct _Flist_node { // forward_list node _Voidptr _Next; // successor node _Value_type _Myval; // the stored value }; |
The main difference between a list and a forward list is the pointer to the previous node.
About forward list
- is a container that supports fast insertion and removal of elements from anywhere in the container.
- Fast random access is not supported.
- It is implemented as a singly-linked list and essentially does not have any overhead compared to its implementation in C.
- Compared to std::list this container provides more space efficient storage when bidirectional iteration is not needed.
- cannot be iterated backwards and its individual elements cannot be accessed directly.
Good to know
std::forward_list::before_begin
- returns an iterator just before the beginning of the list — much as the more familiar end() is just past the end.
- You can’t dereference it
The functions insert, erase, and emplace cannot be used due to the forward list iterators way of going only forward.
Before_begin can be used with the following methods:
- insert_after
- erase_after
- emplace_after
- splice_after
This iterator allows you to use these operations to modify the node at the head of the list.
std::forward_list::
- Reverse – after the function is called, the list will contain the elements in a reversed order
- Sort – after the function is called, the list will contain the elements in a sorted order
- Unique – after the function is called, the list will remove the consecutive duplicate elements
It is very important to note that the unique function will NOT remove all the duplicate elements, in case they are not consecutive.
eg.
{1, 2, 2 } = after unique is called, we will have {1, 2}
{1, 2, 2, 1} = after unique is called, we will have { 1, 2, 1}
More information about forward_list can be read on cppreference webpage.
