list

 Overview

The standard library provides list container.

Details

list is basically template based doubly linked 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 list;

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	a bidirectional iterator to value_type convertible to const_iterator
const_iterator	a bidirectional iterator to const value_type
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
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 links to the previous and next nodes.

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

Functionality

Constructors

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

Name	Description
list()	Default Constructor. Example: //v:{} list<int> v();
list(size_type n)	Constructs a container with n elements initialized with T(). Example: //v:{0,0,0,0,0} list<int> v(5);
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} list<int> v(5,10);
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} list<int> v(begin(a),end(a));
list(const list& x)	copy constructor.
list(list&& x)	move constructor.
list(initializer_list<value_type> il)	initializer_list constructor. Example: //v:{1,2,3,4,5} 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 << ' ';
reverse_iterator  rbegin() reverse_iterator  rend()	Returns reverse_iterator   to reverse beginning and reverse end of the list. Example: list<int> v{1,2,3,4,5}; //prints 5 4 3 2 1 for (auto itr=v.rbegin(); itr!=v.rend(); ++itr) cout << *itr << ' ';
const_iterator cbegin() const_iterator cend()	Returns const_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.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';
const_reverse_iterator crbegin() const_reverse_iterator crend()	Return const_reverse_iterator to reverse beginning and reverse end of the list. Example: list<int> v{1,2,3,4,5}; //prints 5 4 3 2 1 for (auto itr=v.crbegin(); itr!=v.crend(); ++itr) cout << *itr << ' ';

Capacity

Name	Description
size_type size()	Returns the number of elements. Example: list<int> v{1,2,3,4,5}; //prints 5 cout << v.size();
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
bool empty()	Test whether container is empty.

Element Access

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

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}; 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_back(const value_type val)	Adds val at the end of the list. Example: list<int> v{1}; //v:{1,2} v.push_back(2);
void pop_back()	Removes the last element from the list. Example: list<int> v{1,2}; //v:{1} v.pop_back();
void push_front(const value_type val)	Adds element at the front. Example: list<int> v{2}; //v:{1,2} v.push_front(1);
void pop_front()	Deletes first element. Example: list<int> v{1,2}; //v:{2} v.pop_back();
iterator insert(const_iterator pos, InputIterator first, InputIterator last) iterator insert(const_iterator pos, size_type n, const value_type& val) iterator insert(const_iterator pos, const value_type& val) iterator insert(const_iterator pos, const value_type&& val) iterator insert(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 first inserted element.
Example: int a[]{1,2,3}; list<int> v{}; //(1) v:{1,2,3} //it=begin(v)+0 auto it = v.insert(v.begin(),begin(a),end(a)); //(2) v:{1,2,3,4} //it=begin(v)+3 it = v.insert(v.end(),1,4); //(3) v:{1,2,3,4,5} //it=begin(v)+4 it = v.insert(v.end(),5); //(4) v:{1,2,3,4,5,6} //it=begin(v)+5 it = v.insert(v.end(),move(6)); //(5) v:{1,2,3,4,5,6,7} //it=begin(v)+6 it = v.insert(v.end(),{7});
iterator erase(const_iterator pos) iterator erase(const_iterator first, const_iterator last)	Erases element at pos. Erases element in the range. Returns an iterator that points to the element that was  located after the last erased element.
Example: list<int> v{1,2,3,4,5}; //(1) // v:{2,3,4,5} //it = begin(v) auto it = v.erase(cbegin(v)); //(2) // v:{2,3} //it = begin(v)+2 ++it;++it; it = v.erase(it,cend(v));
void swap(vector& v)	Swap content with v. Note T has to be same. Example: list<int> v{1,2,3,4,5}; 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. Example: list<int> v{1,2,3,4,5}; //v:{} v.clear();
iterator emplace((const_iterator pos, Args ...arg)	Construct and insert element in place using arg. Returns an iterator to the newly inserted element.  Example: list<int> v{1,2,3,5}; //v:{1,2,3,4,5} //it = begin(v) + 3 auto it = v.emplace(cbegin(v)+3,4);
void emplace_back(Args ...arg))	Construct and insert element at the end using arg. Example: list<int> v{1,2,3,4}; //v:{1,2,3,4,5} v.emplace_back(5);
void emplace_front(Args ...arg))	Construct and insert element at the beginning using arg. Example: 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: 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 (iterator pos, list& src); void splice (iterator pos, list& src, iterator i); void splice (iterator pos, list& src, iterator first, iterator last);	Removes elements from src and inserts them in pos of the current list.  Removes element pointed by itr from src and inserts them in pos of the current list.  Removes element in the range first to last from src and inserts them in pos of the current list.  In all the three cases, iterator pos is incremented by number of elements inserted.
Example: list<int>::const_iterator operator+ (list<int>::const_iterator it, list<int>::size_type i) { advance(it,i); return it; } list<int> v; list<int> v2; list<int>::iterator it; //(1) v.assign({1,2,3,4}); it = begin(v); v2.assign({5,6,7,8}); // v:{1,2,3,4,5,6,7,8} // v2:{} // begin(v)+4 v.splice(it,v2); //(2) v.assign({1,2,3,4}); it = begin(v); v2.assign({5,6,7,8}); // v:{7,1,2,3,4} // v2:{5,6,8} // begin(v)+1 v.splice(it,v2, v2.begin()+2); //(3) v.assign({1,2,3,4}); it = begin(v); v2.assign({5,6,7,8}); // v:{7,8,1,2,3,4} // v2:{5,6} // begin(v)+2 v.splice(it,v2, v2.begin()+2,v2.end());
void remove_if( UnaryPredicate p );	Removes the elements from the list that  returns true for the p. Example: list<int> v{1,2,3,4,5,2}; //v:{1,3,4,5} v.remove_if([](int i){return i == 2;});
void unique(size_type count) 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: list<int> v{1,2,2,3,4,5,2}; //(1) v:{1,2,3,4,5,2} v.unique(2); //(2) v:{1,4,3,5} 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: list<int> v{1,2,3,4,5,2}; //v:{1,3,4,5} v.remove(2);
void merge(list& tgt) void merge(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: list<int> v; 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: 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: 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();