Thursday, May 10, 2012

deque stl

A deque (pronounced "deck") is very similar to a vector. It manages its elements with a dynamic 
array, provides random access, and has almost the same interface as a vector. The difference is that with a deque the dynamic array is open at both ends. Thus, a deque is fast for insertions and deletions at both the end and the beginning (Figure below).

Figure a: Logical Structure of a Deque

To provide this ability, the deque is implemented typically as a bunch of individual blocks, with the first block growing in one direction and the last block growing in the opposite direction (Figure b).

Figure b: Internal Structure of a Deque

To use a deque, you must include the header file <deque>:

Note: In the original STL, the header file for deques was <deque.h>.

#include <deque>

There, the type is defined as a template class inside namespace std:

namespace std {
   template <class T,
   class Allocator = allocator<T> >
   class deque;

As with vectors, the type of the elements is passed as a first template parameter and may be of any type that is assignable and copyable. The optional second template argument is the memory model, with allocator as the default.

Note: In systems without support for default template parameters, the second argument is typically missing.

We will be covering the following under the deque:
  1. Abilities of Deque
  2. Deque Operations
  3. Examples of Using Deques
See Also:

No comments:

Post a Comment