Deitel & Associates, Inc. Logo

Back to
digg.png delicious.png blinkit.png furl.png
C++ How to Program, 5/e

© 2005
pages: 1500
Buy the Book!
Amazon logo
InformIT logo

STL containers are data structures capable of storing objects of any type. There are three major categories of containers—sequence containers, associative containers and container adapters. The sequence containers represent linear data structures. In the next four tutorials, we introduce sequence containers, then discuss the vector sequence container, the list sequence container and the deque sequence container .

Before You Begin: Download the code examples for these tutorials

[Note: This tutorial is an excerpt (Sections 23.2) of Chapter 23, Standard Template Library (STL), from our textbook C++ How to Program, 5/e. These tutorials may refer to other chapters or sections of the book that are not included here. Permission Information: Deitel, Harvey M. and Paul J., C++ HOW TO PROGRAM, ©2005, pp.1124-1136. Electronically reproduced by permission of Pearson Education, Inc., Upper Saddle River, New Jersey.]

23.2 Sequence Containers

The C++ Standard Template Library provides three sequence containers—vector, list and deque. Class template vector and class template deque both are based on arrays. Class template list implements a linked-list data structure similar to our List class presented in Chapter 21, but more robust.

One of the most popular containers in the STL is vector. Recall that we introduced class template vector in Chapter 7 as a more robust type of array. A vector changes size dynamically. Unlike C and C++ “raw” arrays (see Chapter 7), vectors can be assigned to one another. This is not possible with pointer-based, C-like arrays, because those array names are constant pointers and cannot be the targets of assignments. Just as with C arrays, vector subscripting does not perform automatic range checking, but class template vector does provide this capability via member function at (also discussed in Chapter 7).

Performance Tip
Performance Tip 23.4
Insertion at the back of a vector is efficient. The vector simply grows, if necessary, to accommodate the new item. It is expensive to insert (or delete) an element in the middle of a vector — the entire portion of the vector after the insertion (or deletion) point must be moved, because vector elements occupy contiguous cells in memory just as C or C++ “raw” arrays do.

Figure 23.2 presented the operations common to all the STL containers. Beyond these operations, each container typically provides a variety of other capabilities. Many of these capabilities are common to several containers, but they are not always equally efficient for each container. The programmer must choose the container most appropriate for the application.

Performance Tip
Performance Tip 23.5
Applications that require frequent insertions and deletions at both ends of a container normally use a deque rather than a vector. Although we can insert and delete elements at the front and back of both a vector and a deque, class deque is more efficient than vector for doing insertions and deletions at the front.
Performance Tip
Performance Tip 23.6
Applications with frequent insertions and deletions in the middle and/or at the extremes of a container normally use a list, due to its efficient implementation of insertion and deletion anywhere in the data structure.

In addition to the common operations described in Fig. 23.2, the sequence containers have several other common operations—front to return a reference to the first element in the container, back to return a reference to the last element in the container, push_back to insert a new element at the end of the container and pop_back to remove the last element of the container.

Tutorial Index