Sunday, November 13, 2011

stl deque

Deques / deque standard template library

The term deque (it rhymes with "check" [3] ) is an abbreviation for "double-ended queue." It is a dynamic array that is implemented so that it can grow in both directions. Thus, inserting elements at the end and at the beginning is fast. However, inserting elements in the middle takes time because elements must be moved.

[3] It is only a mere accident that "deque" also sounds like "hack" :-).

The following example (linked above) declares a deque for floating-point values, inserts elements from 1.1 to 6.6 at the front of the container, and prints all elements of the deque:

In this example, with

#include <deque>

the header file for deques is included.

The declaration 

deque<float> coll;

creates an empty collection of floating-point values.

The push_front() function is used to insert elements:


push_front() inserts an element at the front of the collection. Note that this kind of insertion results in a reverse order of the elements because each element gets inserted in front of the previous inserted elements. Thus, the output of the program is as follows:

6.6 5.5 4.4 3.3 2.2 1.1

You could also insert elements in a deque by using the push_back() member function. The push_front() function, however, is not provided for vectors because it would have a bad runtime for vectors (if you insert an element at the front of a vector, all elements have to be moved). Usually, the STL containers provide only those special member functions that in general have "good" timing ("good" timing normally means constant or logarithmic complexity). This prevents a programmer from calling a function that might cause bad performance.

No comments:

Post a Comment