list stl

list stl c++ / stl list

A list is implemented as a doubly linked list of elements. This means each element in a list has its own segment of memory and refers to its predecessor and its successor. Lists do not provide

random access. For example, to access the tenth element, you must navigate the first nine elements by following the chain of their links. However, a step to the next or previous element is possible in constant time. Thus, the general access to an arbitrary element takes linear time (the average distance is proportional to the number of elements). This is a lot worse than the amortized constant time provided by vectors and deques.

The advantage of a list is that the insertion or removal of an element is fast at any position. Only the links must be changed. This implies that moving an element in the middle of a list is very fast compared with moving an element in a vector or a deque.

The following example creates an empty list of characters, inserts all characters from 'a' to 'z', and prints all elements by using a loop that actually prints and removes the first element of the collection:

Example:

using list in STL

As usual, the header file for lists, <list>, is used to define a collection of type list for character values:

list<char> coll;

The empty() member function returns whether the container has no elements. The loop continues as long as it returns true (that is, the container contains elements):

while (! coll.empty()) {

   ...

}

Inside the loop, the front() member function returns the actual first element:

cout << coll.front() << ' ';

The pop_front() function removes the first element:

coll.pop_front();

Note that pop_front() does not return the element it removed. Thus, you can't combine the previous two statements into one. The output of the program depends on the actual character set. For the ASCII character set, it is as follows [4] :

[4] For other character sets the output may contain characters that aren't letters or it may even be empty (if 'z' is not greater than 'a').

a b c d e f g h i j k l m n o p q r s t u v w x y z

Of course it is very strange to "print" the elements of a list by a loop that outputs and removes the actual first element. Usually, you would iterate over all elements. However, direct element access by using operator [] is not provided for lists. This is because lists don't provide random access, and thus using operator [] would cause bad performance. 

See Also:

Standard Template Library Concepts and sample codes in C++