STL List Container

By Alex Allain

The Standard Template Library's list container is implemented as a doubly linked list. You might wonder why there are both list and vector containers in the STL -- the reason is that the underlying representations are different, and each representation has its own costs and benefits. The vector has relatively costly insertions into the middle of the vector, but fast random access, whereas the list allows cheap insertions, but slow access (because the list has to be traversed to reach any item). Some algorithms, such as merge sort, even have different requirements when applied to lists instead of vectors. For instance, merge sort on vectors requires a scratch vector, whereas merge sort on lists does not. Using the STL list class is about as simple as the STL vector container. In fact, to declare a list, all you need is to give the type of data to be stored in the list.

For instance, the following code declares a list storing integers:

std::list<int> integer_list;

Like the vector class, the list class includes the push_back and push_front functions, which add new elements to the front or back of the list respectively.

For instance,

std::list<int> integer_list;

integer_list.push_front(1);
integer_list.push_front(2);

creates a list with the element 2 followed by the element 1.

Correspondingly, it is possible to remove the front or back element using the pop_front() or pop_back() functions. Using these functions alone, it would be possible to create a queue or stack data structure based on the list class.

What about adding elements into the middle of the list -- that is, after all, one of the advantages of a list. The insert function can be used to do so: insert requires an iterator pointing to the position into which the element should be inserted (the new element will be inserted right before the element currently being pointed to will).

The insert function looks like this:

iterator insert(iterator position, const T& element_to_insert);

Fortunately, the list container supports both the begin -- returning an iterator to the beginning of the list -- and end -- returning an iterator past the last element of the list -- iterator functions, and you can declare iterators as with any other container, in the following manner:

list<type>::iterator iterator_name;

Note that the STL list container supports iterating both forward and in reverse (because it is implemented as a doubly linked list).

Using insert and the function end, the functionality of push_back, which adds an element to the end of the list, could also be implemented as

std::list<int> integer_list;
integer_list.insert(integer_list.end(), item);

The list class also includes the standard functions size and empty. There is one caveat to be aware of: the size function may take O(n) time, so if you want to do something simple such as test for an empty list, use the empty function instead of checking for a size of zero. If you want to guarantee that the list is empty, you can always use the clear function.

std::list<int> integer_list;
\\ bad idea
if(integer_list.size() == 0)
    ...
\\ good idea
if(integer_list.empty())
    ...

integer_list.clear();
\\ guaranteed to be empty now

Lists can also be sorted using the sort function, which is guaranteed to take time on the order of O(n*log(n)). Note that the sort algorithm provided by the STL works only for random access iterators, which are not provided by the list container, which necessitates the sort member function:

instance_name.sort();

Lists can be reversed using

instance_name.reverse();

One feature of using the reverse member function instead of the STL algorithm reverse (to be discussed later) is that it will not affect the values that any other iterators in use are pointing to.

Another potentially useful list function is the member function called unique; unique converts a string of equal elements into a single element by removing all but the first element in the sequence. For instance, if you had a list consisting of

1 1 8 9 7 8 2 3 3

the calling unique would result in the following output:

1 8 9 7 8 2 3

Notice that there are still two 8's in the above example: only sequential equal elements are removed! Unique will take time proportional to the number of elements in the list.

If you want each element to show up once, and only once, you need to sort the list first! Try the following code to see how this works and see many of the previous functions in action!

std::list<int> int_list;
int_list.push_back(1);
int_list.push_back(1);
int_list.push_back(8);
int_list.push_back(9);
int_list.push_back(7);
int_list.push_back(8);
int_list.push_back(2);
int_list.push_back(3);
int_list.push_back(3);
int_list.sort();
int_list.unique();

for(std::list<int>::iterator list_iter = int_list.begin(); 
    list_iter != int_list.end(); list_iter++)
{
    std::cout<<*list_iter<<endl;
}

Summary

The Good

Lists provide fast insertions (in amortized constant time) at the expensive of lookups
Lists support bidirectional iterators, but not random access iterators
Iterators on lists tend to handle the removal and insertion of surrounding elements well

The Gotchas

Lists are slow to search, and using the size function will take O(n) time
Searching for an element in a list will require O(n) time because it lacks support for random access

Previous: STL Associative Arrays (Maps)