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

[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.

Page 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12

Tutorial Index