 |
ISBN: |
[Note: This tutorial is an excerpt (Sections 23.1) 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.1112-1123. Electronically reproduced by permission of Pearson Education, Inc., Upper Saddle River, New Jersey.]
23.1.1 Introduction to Containers
The STL container types are shown in Fig. 23.1. The containers are divided into three major categories—sequence containers, associative containers and container adapters.
| Standard Library container class | Description |
| Sequence containers | |
vector |
rapid insertions and deletions at back direct access to any element |
deque |
rapid insertions and deletions at front or back direct access to any element |
list |
doubly linked list, rapid insertion and deletion anywhere |
| Associative containers | |
set |
rapid lookup, no duplicates allowed |
multiset |
rapid lookup, duplicates allowed |
map |
one-to-one mapping, no duplicates allowed, rapid key-based lookup |
multimap |
one-to-many mapping, duplicates allowed, rapid key-based lookup |
| Container adapters | |
stack |
last-in, first-out (LIFO) |
queue |
first-in, first-out (FIFO) |
priority_queue |
highest-priority element is always the first element out |
Fig. 23.1 Standard Library container classes.
STL Containers Overview
The sequence containers (also referred to as sequential containers) represent linear data structures, such as vectors and linked lists. Associative containers are nonlinear containers that typically can locate elements stored in the containers quickly. Such containers can store sets of values or key/value pairs. The sequence containers and associative containers are collectively referred to as the first-class containers. As we saw in Chapter 21, stacks and queues actually are constrained versions of sequential containers. For this reason, STL implements stacks and queues as container adapters that enable a program to view a sequential container in a constrained manner. There are four other container types that are considered “near-containers”—C-like pointer-based arrays (discussed in Chapter 7), strings (discussed in Chapter 18), bitsets for maintaining sets of flag values and valarrays for performing high-speed mathematical vector operations (this last class is optimized for computation performance and is not as flexible as the first-class containers). These four types are considered “near containers” because they exhibit capabilities similar to those of the first-class containers, but do not support all the first-class-container capabilities.