A list is a sequential container that is optimized for insertion and erasure at arbitrary points at the expense of giving up indexed based access. This section provides an overview of list .

Iterator Type

Implementation

A list is normally implemented as a doubly-linked list in which every node in the list has a pointer to the previous node and a pointer to the next node.

All list objects of a particular type share a common pool of free nodes. This reduces the amount of unnecessary heap access. When a node is no longer used by a list , it is placed back into the pool so it can be reused. When the number of list objects of a particular type drops to zero, the nodes in the associated common pool are deallocated.

For compilers that do not support templatized destruction, this pool approach cannot be used and a simpler but less efficient memory allocation strategy is used.

Insertion Notes

Inserting a single item into a list takes constant time with one call to the copy constructor.

Inserting multiple items into a list is linear in the number of items inserted. The number of calls to the copy constructor is equal to the number of items inserted.

Erasure Notes

Erasing a single item is a constant time operation with a single call to the destructor. Erasing a range in a list is linear time in the size of the range, and the number of calls to the destructor is equal to the size of the range. An erasure invalidates only the iterators and references to the erased items.

Common Uses

A list is useful when the order of items and fast arbitrary insertion and erasure are important. A list is not as efficient as a deque when insertion and erasure only take place at the extremities.

Interface

A list has a more elaborate interface than any of the other sequential containers. It includes functions for splicing, removing, filtering, merging, and sorting. This section contains examples of each of these features.

The splicing family of functions moves a group of one or more items from one list to another.

Example <ospace/osstd/examples/list2.cpp>


  #include <iostream>
#include <list>

int array1[] = { 1, 16 };
int array2[] = { 4, 9 };

void
main()
  {
  list< int > l1( array1, array1 + 2 );
  list< int > l2( array2, array2 + 2 );
  list< int >::iterator i = l1.begin();
  ++i;

  l1.splice( i, l2, l2.begin(), l2.end() );

  i = l1.begin();
  while ( i != l1.end() )
    cout << *i++ << "\n";
  }

1
4
9
16

The list container also contains several useful functions that perform the same tasks as the STL algorithms with the same name, except they are optimized for the internal architecture of a list .

remove

void
    remove( const T&

value )

Erases all elements that match value , using == to perform the comparison.

reverse

void
    reverse()

Reverses the order of the elements in the list . The time complexity is O(N).

unique

void
    unique()

Replaces all repeating sequences of a single element by a single occurrence of that element.

sort

void
    sort()

Sorts the list elements using operator< . The time complexity is O(NlogN). Note that unlike the algorithm equivalent of this operation, there is no variation of this function that takes a comparison operator.

Following is an example demonstrating each of these four functions.

Example <ospace/osstd/examples/list3.cpp>


  #include <iostream>
#include <list>

char array[] = { `x', `l', `x', `t', `s', `s' };

void
main()
  {
  list< char > str( array, array + 6 );
  list< char >::iterator i;

  cout << "original: ";
  for ( i = str.begin(); i != str.end(); ++i )
    cout << *i;
  cout << "\n";

  str.reverse();
  cout << "reversed: ";
  for ( i = str.begin(); i != str.end(); ++i )
    cout << *i;
  cout << "\n";

  str.remove( `x' );
  cout << "removed: ";
  for ( i = str.begin(); i != str.end(); ++i )
    cout << *i;
  cout << "\n";

  str.unique();
  cout << "uniqued: ";
  for ( i = str.begin(); i != str.end(); ++i )
    cout << *i;
  cout << "\n";

  str.sort();
  cout << "sorted: ";
  for ( i = str.begin(); i != str.end(); ++i )
    cout << *i;
  cout << "\n";
  }

original: xlxtss
reversed: sstxlx
removed: sstl
uniqued: stl
sorted: lst

The list container supplies a specialized version of the merge() algorithm optimized for merging lists.

merge

void
    merge( const list< T, Allocator >&

source )

Moves the elements of source into the list and sorts the result using the operator<. This operation assumes that both list and source are already sorted using operator<.

The following example illustrates the use of merge() .

Example <ospace/osstd/examples/list4.cpp>


  #include <iostream>
#include <list>

int array1[] = { 1, 3, 6, 7 };
int array2[] = { 2, 4 };

void
main()
  {
  list< int > l1( array1, array1 + 4 );
  list< int > l2( array2, array2 + 2 );

  l1.merge( l2 );
  for ( int_list::iterator i = l1.begin(); i != l1.end(); ++i )
    cout << *i << " ";
  cout << "\n";
  }

1 2 3 4 6 7