Standard Template Class list

The list class manages its elements as a doubly linked list. This is fundamentally different to vector and deque. The list does not support random access; to do so would require code to count down from the beginning each time an element is accessed. This would be exceedingly inefficient. Inserting and removing elements anywhere in a list is very efficient, as no other elements will need to be moved. As no elements are moved during insertions and deletions external references and pointers will not be invalidated (unless the element being deleted is the one referenced!). Lists do not support the concept of capacity because it is not needed, they have no need to over-allocate storage. Though it is possible that some implementations may still do some sort of pre-allocation in order to try and keep stored elements in the same page in a paged memory architecture.

The list class supports all the same operations as deque along with a number of others to perform operations such as splicing and merging, which can be handled very efficiently, as all that needs to be done is redirect a number of pointers.

To use the list class the header file <list> must be included.

© Focus Software Soutions Limited 2005