The vector data structure is a container of relatively fixed size. While the C++ Standard Library provides facilities for dynamically changing the size of a vector, such operations are costly and should be used only rarely. Yet in many problems, the size of a collection may be difficult to predict in advance, or may vary widely during the course of execution. For cases that suggest an alternative data structure, we examine the list datatype in this chapter.
A list corresponds to the intuitive idea of holding elements in a linear sequence that is not necessarily ordered. New values can be added to or removed from either the front or the back of the list. By using an iterator to denote a position, elements can also be added to or removed from the middle of a list. In all cases the insertion or removal operations are efficient; they are performed in a constant amount of time that is independent of the number of elements being maintained in the collection.
A list is a linear structure. In general, elements of a list can only be accessed by a linear traversal of all values, not by subscript.
Whenever you use a list, you must include the list header file:
#include <list>