STL Lists 1 (sstutor)

STL Lists 1

We’ve already written a program that makes use of the STL list container. Let’s take a deeper look into the list container in this section. The STL list container is a doubly linked-list. Thus each node has the element as well as two pointers pointing to the next and previous node of the list. Lists are advantageous if there are going to be many insertions and removals from the middle of the list (since all you need to do is modify the pointers). Lists do not support random access. Thus the list container supports the bidirectional iterator (not the random access iterator which is supported by the vector container).

Before going into an example program let’s take a look at the insert member function. The insert function is available in all the sequence containers and it has three forms:

intlist.insert(intlist.begin( ), val);

will insert the value ‘va’ at the beginning of the container.

intlist.insert(intlist.begin( ), n, val);

will insert the value ‘val’ n times at the beginning of the container.

intlist.insert(intlist.begin( ), iterator/pointer, iterator/pointer);

will insert the elements from the first pointer to the second pointer at the beginning of the container.

Note: You needn’t always insert at the beginning of a container. The first argument for the function insert ( ) specifies the location where you want to insert the values. By changing this iterator you can insert at different positions.

Member functions for the List container:

These two functions are available in the list and deque containers but not in the vector container:

push_front( )

pop_front( )

The following functions are available only in the list container:

splice( )

merge( )

unique( )

sort( )

reverse( )

remove( )

Note: The sort( ) function is available as an algorithm and also as a member function in a few containers. The algorithm sort form can be used across any container (but it requires a random access iterator). If the container you are using has a specific member function sort( ), then it is more efficient to use this function than the generic sort because member functions have been written knowing the internals of that particular container. The generic sort will not take advantage of the internal structure of the container since it has to work on all containers.

Go to the section on Member Functions in Lists (program)

Go back to Contents page 2.