forward_list

Overview

The standard library provides light weight  but flexible  forward_list. 

Details

forward_list is basically a template based singly linked list designed for fast addition, removal or moving anywhere in the list.

Syntax

The syntax is as below. Template parameter T represents the datatype to store and Alloc represents the allocator used for storage.

template < class T, class Alloc = allocator<T> > 
class forward_ist;

Members

 It defines following types

Name	Description
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer
const_pointer	allocator_traits<allocator_type>::const_pointer
iterator	forward access iterator to value_type convertible to const_iterator
const_iterator	forward access iterator to const value_type
difference_type	a signed integral type
size_type	an unsigned integral type

Operation

list can be graphically represented as below. Each node has links to the previous and next nodes.

New elements can be added or removed in the end or in the middle of the list. Each node has a link to the next node.

Complexity

Random access operation is not supported. Insertion or removal at the front or end is O(1). Insertion or removal at the middle is O(1) .

Functionality

Constructors

In following constructors use default allocator. Custom allocators can be used by passing them as an additional argument.

Name	Description
forward_list ()	Default Constructor. Example: //v:{} forward_list<int> v();
forward_list (size_type n)	Constructs a container with n elements initialized with T(). Example: //v:{0,0,0,0,0} forward_list<int> v(5);
forward_list (size_type n, const value_type& val)	Constructs a container with n elements initialized with with val. Example: //v:{10,10,10,10,10} forward_list<int> v(5,10);
forward_list (InputIterator first, InputIterator last)	Constructs a container and copies the elements in the range. Example: int a[5]{1,2,3,4,5}; //v:{1,2,3,4,5} forward_list<int> v(begin(a),end(a));
forward_list (const forward_list & x)	copy constructor.
forward_list (forward_list && x)	move constructor.
forward_list (initializer_list<value_type> il)	initializer_list constructor. Example: //v:{1,2,3,4,5} forward_list<int> v{1,2,3,4,5};

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end of the list. Example: list<int> v{1,2,3,4,5}; //prints 1 2 3 4 5 for (auto itr=v.begin(); itr!=v.end(); ++itr) cout << *itr << ' ';
iterator  before_begin() const_iterator  cbefore_begin()	Returns an iterator pointing to the position before the first element in the container. The iterator returned should not be dereferenced. Instead it should be used for inserting elements after it. Example: forward_list<int> v{2,3,4,5}; //v:{1,2,3,4,5} v.insert_after(v.before_begin(),1); //v:{0,1,2,3,4,5} v.insert_after(v.cbefore_begin(),0);
const_iterator cbegin() const_iterator cend()	Return const_iterator to beginning and end of the list. Example: forward_list<int> v{1,2,3,4,5}; //prints 1 2 3 4 5 for (auto itr=v.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';

Capacity

Name	Description
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
bool empty()	Test whether forward_list is empty.

Element Access

Name	Description
reference front()	Returns reference or const reference to the first element.  Exception is thrown for invalid input. Example: forward_list<int> v{1,2,3,4,5}; //prints 1. cout << v.front();

Modifiers

Name	Description
void assign(InputIterator first, InputIterator last) void assign(size_type n, const value_type& val) void assign(initializer_list<value_type> il)	Replaces content with the  elements in the range. Replaces content  with n elements initialized with with val. Replaces content with the contents of il.
Example: int a[]{1,2,3,4,5}; forward_list<int> v{}; //(1) v:{3,4,5} v.assign(begin(a)+2,end(a)); //(2) v:{10,10,10,10,10} v.assign(5,10); //(3) v:{1,2,3} v.assign({1,2,3});
void push_front(const value_type val)	Adds element at the front. Example: forward_list<int> v{2}; //v:{1,2} v.push_front(1);
void pop_front()	Deletes first element. Example: forward_list<int> v{1,2}; //v:{2} v.pop_front();
iterator insert_after(const_iterator pos, InputIterator first, InputIterator last) iterator insert_after(const_iterator pos, size_type n, const value_type& val) iterator insert_after(const_iterator pos, const value_type& val) iterator insert_after(const_iterator pos, const value_type&& val) iterator insert_after(const_iterator pos,, initializer_list<value_type> il)	At pos, insert the  elements in the range. At pos, insert n elements initialized with with val. At pos, insert an element with value val. At pos, insert an element with value val moved. At pos, insert an element with the contents of il. All these returns an iterator to the last inserted element
Example: int a[]{1,2,3}; forward_list<int> v{}; //(1) v:{1,2,3} //it=begin(v)+2 auto it = v.insert_after(v.before_begin(),begin(a),end(a)); //(2) v:{1,2,3,4} //it=begin(v)+3 it = v.insert_after(it,1,4); //(3) v:{1,2,3,4,5} //it=begin(v)+4 it = v.insert_after(it,5); //(4) v:{1,2,3,4,5,6} //it=begin(v)+5 it = v.insert_after(it,move(6)); //(5) v:{1,2,3,4,5,6,7} //it=begin(v)+6 it = v.insert_after(it,{7});
iterator erase_after(const_iterator pos) iterator erase_after(const_iterator first, const_iterator last)	Erase element at pos Erase element in the range Returns an iterator that points to the element that was  located after the last erased element.
Example: forward_list<int> v{1,2,3,4,5}; //(1) v:{1,3,4,5} //it = beginv)+1 auto it = v.erase_after(cbegin(v)); //(2) v:{1,3} //it = beginv)+2 it = v.erase_after(cbegin(v)+1,cend(v));
void swap(vector& v)	Swap content with v. Note T has to be same. Example: forward_list<int> v{1,2,3,4,5}; forward_list<int> v2{5,4,3,2,1}; //v2:{1,2,3,4,5} //v:{1,2,3,4,5} v2.swap(v);
void clear()	Clear contents of vector. Example: forward_list<int> v{1,2,3,4,5}; //v:{} v.clear();
iterator emplace_after(const_iterator pos, Args ...arg)	Construct and insert element in place using arg after pos. Returns an iterator to the newly inserted element.  Example: forward_list<int> v{1,2,3,5}; //v:{1,2,3,4,5} //it = begin(v) + 3 auto it = v.emplace(cbegin(v)+2,4);
void emplace_front(Args ...arg)	Construct and insert element at the beginning using arg. Example: forward_list<int> v{2,3,4}; //v:{1,2,3,4} v.emplace_front(1);
void resize(size_type count) void resize(size_type count,  value_type val)	Resizes list size to count elements. New elements are initialized with default value. Resizes list size to count elements. New elements are initialized with val.
Example: forward_list<int> v{1,2,3,4,5}; //(1) v:{1,2,3} v.resize(3); //(2) v:{1,2,3,6,6} v.resize(5,6);
void splice_after (iterator pos, forward_list& src); void splice_after(iterator pos, forward_list& src, iterator i); void splice_after (iterator pos, forward_list& src, iterator first, iterator last);	Removes elements from src and inserts them in pos of the current list.  Removes element after by itr from src and inserts them in pos of the current list.  Removes elements in the range element after first to element before last from src and inserts them in pos of the current list.
Example: forward_list<int> v{4,5,6}; forward_list<int> v2{1,2,3}; forward_list<int>::const_iterator operator+ (forward_list<int>::const_iterator it, forward_list<int>::size_type i) { advance(it,i); return it; } //(1) // v:{1,2,3,4,5,6} // v2:{} v.splice_after(v.before_begin(),v2); //(2) v2.assign({7}); // v:{1,2,3,4,5,6,7} // v2:{} v.splice_after(begin(v)+5,v2,v2.before_begin()); //(3) v2.assign({8,9}); // v:v:{1,2,3,4,5,6,7,8,9} // v2:{} v.splice_after(begin(v)+6,v2,v2.before_begin(),v2.end());
void remove_if( UnaryPredicate p );	Removes the elements from the list that  returns true for the p. Example: forward_list<int> v{1,2,3,4,5,2}; //v:{1,3,4,5} v.remove_if([](int i){return i == 2;});
void unique() void unique(BinaryPredicate bp)	Removes duplicate elements in a consecutive  group from the list. Removes duplicate elements in a consecutive  group from the list that returns true for bp.
Example: forward_list<int> v{1,2,2,3,4,5,2}; //(1) v:{1,2,3,4,5,2} v.unique(); //(2) v:{1,3,4,5,2} v.unique([](int i, int j){return j / i == 2;});
void remove(const value_type& val)	Removes the elements of value val from the list.  Example: forward_list<int> v{1,2,3,4,5,2}; //v:{1,3,4,5} v.remove(2);
void merge(forward_list& tgt) void merge(forward_list& tgt, Compare cmp)	Merges the sorted lists resulting in quasi sorted list containing elements from both lists. tgt becomes empty. Merges the sorted lists by strict weak order comparison using cmp resulting in quasi sorted list containing elements from both lists. tgt becomes empty.
Example: forward_list<int> v; forward_list<int> v2; //(1) v.assign({1,2,3,4}); v2.assign({4,5,6,7}); // v:{1,2,3,4,4,5,6,7} // v2:{} v.merge(v2); //(2) v.assign({1,2,3,4}); v2.assign({4,5,6,7}); // v:{1,2,3,4,4,5,6,7} // v2:{} v.merge(v2,less<int>());
void sort() void sort(Compare cmp)	Sorts the elements using less<>(). Sorts the elements using cmp.
Example: forward_list<int> v; //(1) v.assign({1,3,2,5,4,5,6,4}); //v:{1,2,3,4,4,5,5,6} v.sort(); //(2) v.assign({1,3,2,5,4,5,6,4}); //v:{6,5,5,4,4,3,2,1} v.sort(greater<int>());
void reverse()	Reverses the elements in the list. Example: forward_list<int> v{1,3,2,5,4,5,6,4}; //v:{1,2,3,4,4,5,5,6} v.sort(); //v:{6,5,5,4,4,3,2,1} v.reverse();