Easy C++


STL Tutorial - Lesson 2: Sequence Containers

Sequence Containers

by John Kopp

Support this site at no cost to you

The Standard Template Library, or STL, is a collection of container classes, generic algorithms and related components that can greatly simplify many programming tasks in C++. This lesson covers sequence containers. Sequence containers hold elements of a single type as a linear sequence. That is, they are ordered in the same way as they are added to the container. The STL provides three sequence containers: vector, deque and list. In addition, arrays, which are a built-in part of the language and the string class, which is part of the standard library, may be used as sequence containers. The generic algorithms will work with arrays and strings. Other types of data structures such as stacks, queues and priority queues are provided in the STL by the use of container adapters on the sequence containers. This will be covered in a later lesson. In later lessons, we'll also cover associative containers that store their elements in a sorted manner.

The first question that needs to be addressed is why is there more than one sequence container. As we will see, they are optimized for different uses. The vector class is optimized for insertions and deletions at its end, has compatibility with C-style arrays and provided random access iterators. Random access iterators allow constant time retrieval of any element and are required by certain generic algorithms. The deque (pronounced "deck") class is optimized for insertions and deletions at either end and also provides random access iterators. Lists allow constants time insertions and deletions anywhere. They provide only bidirectional iterators, and not random access, so they can't be used with certain generic algorithms. Just about all you need to know about iterators was covered in the overview lesson. Any other details will be discussed as needed.

Previous Page       Next Page