Computing › Stl › Containers › Sequences ›

List

A sequence that supports both forward and backward traversal and insertion of elements to the front or back of the list in constant time

View version details

Contents

Definition
Description
Performance
List Operations
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Definition

The list template is defined in the standard header <list>, and in the nonstandard backward-compatibility header <list.h>.

#include <list>
namespace std {
   template <class T, class Allocator = allocator<T> >
   class list;
}

Description

A list is a Sequence that supports both forward and backward traversal, and constant time insertion and removal of elements at the beginning or the end, or in the middle. A list contain elements which are ordered following a linear sequence.

Short example:

list<int> L; //Creates a list with L elements of type int
L.push_back(0); // Insert a new element at the end
L.push_front(0); // Insert a new element at the beginning
L.insert(++L.begin(),2); // Insert "2" before position of first argument

Performance

Lists have the property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed.

The ordering of iterators may be changed but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.

List Operations

Create, Copy and Destroy Operations

Operation	Effect
list< El > c	Creates an empty list with no elements
list< El > c1(c2)	Creates a copy of another list of the same type (all elements are copied)
list< El > c(nr)	Creates a list with nr elements that are created by the default constructor
list< El > c(nr,el)	Creates a list initialized with nr copies of element el
list< El > c (beg,end)	Creates a list initialized with the elements of the range [beg,end)
c.~list< El >()	Destroys all elements and frees the memory

Nonmodifying Operations

Operation	Effect
c.size()	Returns the actual number of elements
c.empty()	Returns if the container is empty (equivalent to size()==0)
c.max_size()	Returns the maximum number of elements possible
c1==c2	Returns if c1 is equal to c2
c1!=c2	Returns if c1 is not equal to c2 (equivalent to !(c1==c2))
c1<c2	Returns if c1 is less than c2
c1>c2	Returns if c1 is greater than c2 (equivalent to c2<c1)
c1<=c2	Returns if c1 is less than or equal to c2 (equivalent to !(c2<c1) )
c1>=c2	Returns if c1 is greater than or equal to c2 (equivalent to !(c1<c2))

Assignments

Operation	Effect
c1=c2	Assigns all elements of c2 to c1
c.assign(nr,el)	Assigns nr copies of element el
c.assign(beg,end)	Assigns the elements of the range [beg,end)
c1.swap(c2)	Swaps the data of c1 and c2
swap(c1,c2)	Same (as global function)

Element Access

Operation	Effect
c.front()	Returns the first element (without range checking if a first element exists)
c.back()	Returns the last element (without range checking if a last element exists)

Iterator Functions

Operation	Effect
c.begin()	Returns a bidirectional iterator for the first element
c.end()	Returns a bidirectional iterator for the position after the last element
c.rbegin()	Returns a reverse iterator for the first element of a reverse iteration
c.rend()	Returns a reverse iterator for the position after the last element of a reverse iteration

Inserting and Removing Elements

Operation	Effect
c.insert(pos,el)	Inserts at iterator position pos a copy of el and returns the position of the new element
c.insert(pos,nr,el)	Inserts at iterator position pos nr copies of el (returns nothing)
c.insert(pos,beg,end)	Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)
c.push_back(el)	Appens a copy of el at the end
c.pop_back()	Removes the last element (does not return it)
c.push_front(el)	Inserts a copy of el at the beginning
c.pop_front()	Removes the first element (does not return it)
c.remove(v)	Removes all elements with value v
c.remove_if(op)	Removes all elements for which op(elem) yields true
c.erase(pos)	Removes the element at iterator position pos and returns the position of the next element
c.erase(beg,end)	Removes all elements of the range [beg,end) and returns the position of the next element
c.resize(nr)	Changes the number of elements to nr (if size() grows, new elements are created by their default constructor)
c.resize(nr, el)	Changes the number of elements to nr (if size() grows, new elements are copies of el)
c. clear()	Removes all elements (makes the list empty)

Splice Functions

Operation	Effect
c.unique()	Removes duplicates of consecutive elements with the same value
c.unique(op)	Removes duplicates of consecutive elements, for which op() yields true
c1.splice(pos,c2)	Moves all elements of c2 to c1 in front of the iterator position pos
c1.splice(pos,c2,c2pos)	Moves the element at c2pos in c2 in front of pos of list c1 (c1 and c2 may be the same)
c1.splice(pos,c2,c2beg,c2end)	Moves all elements of the range [c2beg,c2end) in c2 in front of pos of list c1 (c1 and c2 may be the same)
c.sort()	Sorts all elements with operator <
c.sort(op)	Sorts all elements with op()
c1.merge(c2)	Assuming both list contain the elements sorted, moves all elements of c2 into c1 so that all elements are merged and still sorted
c1.merge(c2,op)	Assuming both list contain the elements sorted due to the sorting criterion op(), moves all elements of c2 into c1 so that all elements are merged and still sorted according to op()
c.reverse()	Reverses the order of all elements

List Operations with Special Guarantees in Face of Exceptions

Operation	Guarantee
push_back()	Either succeeds or has no effect
push_front()	Either succeeds or has no effect
insert()	Either succeeds or has no effect
pop_back()	Doesn't throw
pop_front()	Doesn't throw
erase()	Doesn't throw
clear()	Doesn't throw
resize()	Either succeeds or has no effect
remove()	Doesn't throw if comparing the elements doesn't throw
remove_if()	Doesn't throw if the predicate doesn't throw
unique()	Doesn't throw if comparing the elements doesn't throw
splice()	Doesn't throw
merge()	Either succeeds or has no effect if comparing the elements doesn't throw
reverse()	Doesn't throw
swap()	Doesn't throw

References:

http://www.sgi.com
Nicolai M. Josuttis: "The C++ Standard Library"

Example:

Example - operations for lists - Linux

Problem

This program on data type int illustrates some simple operations for lists.

Workings

#include <iostream>
#include <list>
 
using namespace std;
 
main()
{
 list<int> LIST;
 LIST.push_back(1); // Insert a new element at the end
 LIST.push_front(1); // Insert a new element at the beginning
 LIST.insert(++LIST.begin(),3); 
 // Insert "3" before position of first argument
 // (Place before second argument)
 
 LIST.push_back(10);
 LIST.push_back(11);
 
 list<int>::iterator i;
 for(i=LIST.begin(); i != LIST.end(); ++i)
 cout << *i << " ";
 cout << endl;
 return 0;
}

Solution

Output:
1 3 1 10 11