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. The following article discusses the deque sequence container. Also see the related articles that introduce sequence containers and discuss the list sequence container and the vector sequence container.

[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.3 deque Sequence Container

Class deque provides many of the benefits of a vector and a list in one container. The term deque is short for “double-ended queue.” Class deque is implemented to provide efficient indexed access (using subscripting) for reading and modifying its elements, much like a vector. Class deque is also implemented for efficient insertion and deletion operations at its front and back, much like a list (although a list is also capable of efficient insertions and deletions in the middle of the list). Class deque provides support for random-access iterators, so deques can be used with all STL algorithms. One of the most common uses of a deque is to maintain a first-in, first-out queue of elements. In fact, a deque is the default underlying implementation for the queue adaptor (Section 23.4.2).

Additional storage for a deque can be allocated at either end of the deque in blocks of memory that are typically maintained as an array of pointers to those blocks.3 Due to the noncontiguous memory layout of a deque, a deque iterator must be more intelligent than the pointers that are used to iterate through vectors or pointer-based arrays.

Performance Tip
Performance Tip 23.13
In general, deque has slightly higher overhead than vector.
Performance Tip
Performance Tip 23.14
Insertions and deletions in the middle of a deque are optimized to minimize the number of elements copied, so it is more efficient than a vector but less efficient than a list for this kind of modification.

Class deque provides the same basic operations as class vector, but adds member functions push_front and pop_front to allow insertion and deletion at the beginning of the deque, respectively.

Page 1 | 2

Tutorial Index