STL LIST

STL LIST

• Lists are a kind of sequence containers. As such, their elements are ordered following a linear sequence.
• List containers are implemented as doubly-linked lists. Doubly linked lists can store each of the elements they contain in different and unrelated storage locations.
• Efficient insertion and removal of elements anywhere in the container (constant time).
• Efficient moving elements and block of elements within the container or even between different containers (constant time).
• Iterating over the elements in forward or reverse order (linear time).

COMPARISON TO OTHER SEQUENCE CONTAINERS- DEQUEUES AND VECTORS

Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

Example:

// swap lists
# include < iostream >
# include < list >
using namespace std;

main ()
{
  list< int > first (3,100);   // three ints with a value of 100
  list< int > second (5,200);  // five ints with a value of 200
  list< int >::iterator it;

  first.swap(second);

  cout << "first contains:";
  for (it=first.begin(); it!=first.end(); it++) cout << " " << *it;

  cout << "\nsecond contains:";
  for (it=second.begin(); it!=second.end(); it++) cout << " " << *it;

  cout << endl;

  return 0;
}