Chapter 9. Sequential Containers


CONTENTS

Section 9.1 Defining a Sequential Container

307

Section 9.2 Iterators and Iterator Ranges

311

Section 9.3 Sequence Container Operations

316

Section 9.4 How a vector Grows

330

Section 9.5 Deciding Which Container to Use

333

Section 9.6 strings Revisited

335

Section 9.7 Container Adaptors

348

Chapter Summary

353

Defined Terms

353


This chapter completes our discussion of the standard-library sequential container types. It expands on the material from Chapter 3, which introduced the most commonly used sequential container, the vector type. Elements in a sequential container are stored and accessed by position. The library also defines several associative containers, which hold elements whose order depends on a key. Associative containers are covered in the next chapter.

The container classes share a common interface. This fact makes the library easier to learn; what we learn about one type applies to another. Each container type offers a different set of time and functionality tradeoffs. Often a program using one type can be fine-tuned by substituting another container without changing our code beyond the need to change type declarations.

A container holds a collection of objects of a specified type. We've used one kind of container already: the library vector type. It is a sequential container. It holds a collection of elements of a single type, making it a container. Those elements are stored and accessed by position, making it a sequential container. The order of elements in a sequential container is independent of the value of the elements. Instead, the order is determined by the order in which elements are added to the container.

The library defines three kinds of sequential containers: vector, list, and deque (short for "double-ended queue" and pronounced "deck"). These types differ in how elements are accessed and the relative run-time cost of adding or removing elements. The library also provides three container adaptors. Effectively, an adaptor adapts an underlying container type by defining a new interface in terms of the operations provided by the original type. The sequential container adaptors are stack, queue, and priority_queue.

Containers define only a small number of operations. Many additional operations are provided by the algorithms library, which we'll cover in Chapter 11. For those operations that are defined by the containers, the library imposes a common interface. The containers vary as to which operations they provide, but if two containers provide the same operation, then the interface (name and number of arguments) will be the same for both container types. The set of operations on the container types form a kind of hierarchy:

  • Some operations are supported by all container types.

  • Other operations are common to only the sequential or only the associative containers.

  • Still others are common to only a subset of either the sequential or associative containers.

In the remainder of this chapter, we look at the sequential container types and their operations in detail.

Table 9.1. Sequential Container Types

Sequential Containers

 

vector

Supports fast random access

list

Supports fast insertion/deletion

deque

Double-ended queue

Sequential Container Adaptors

stack

Last in/First out stack

queue

First in/First out queue

priority_queue

Priority-managed queue




C++ Primer
C Primer Plus (5th Edition)
ISBN: 0672326965
EAN: 2147483647
Year: 2006
Pages: 223
Authors: Stephen Prata

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net