Deque

Deque

Overview

The deque (pronounced "deck") container is an implementation of a double-ended queue. A deque is not a FIFO data structure like a queue. Instead, a double-ended queue allows elements to be inserted or removed from either the beginning or end of the sequence. The STL deque container provides additional capabilities above some deque implementations such as inserting or removing elements at arbitrary points in a sequence. It also provides efficient random-access to the elements contained by the deque, although random access is not as efficient as with the vector container.

To declare an instance of a deque, you must #include <deque>. You can then write a declaration similar to the following:

std::deque<int> dequeOfIntegers;

A deque's elements can be accessed by the [] operator and the at() method, just like with a vector. Look at the documentation for vector for explanations and examples of how to access elements of a deque.

Vector or Deque? How to Decide Which is Better for a Given Application

From the viewpoint of the client, the vector and deque containers are remarkably similar. Here are some of the differences between vector and deque:

Deque allows constant time insertion/removal of elements from the beginning and end of a sequence. Vector only allows elements to be inserted/removed from the end of a sequence in amortized constant time.
Deque allows elements to be inserted/removed from arbitrary points in a sequence more efficiently than a vector can, although not in constant time.
Random access to elements contained in a deque is slightly less efficient when compared to a vector due to an additional level of indirection.
For sequences that consist of a large number of elements, a vector will allocate one large, contiguous block of memory while a deque will allocate several, smaller blocks of memory. Several small allocations tend to result in better performance under most operating systems.
Deques provide all the capability needed to function as a stack or a queue.
Deques grow more efficiently than vectors. This is because a deque will allocate a new block of memory when the memory buffer is exausted and begin using it to store the new elements. A vector will allocate a new, larger block of memory to replace the previously used memory block and copy all of the elements to the new memory block. Vector's method for expanding is clearly less efficient.

Like vectors, deques provide random access iterators.

Methods

Deque defines the following methods:

Operation	Description	Time Complexity
operator=	Allows assignment of one deque into another. Both deques must contain elements of the same data type. Ex: deque1 = deque2;	O(n)
swap	Swaps elements with another deque. Ex: deque1.swap(deque2);	O(1)
begin	Returns an iterator to the first value in the sequence contained by the deque. Ex: itr = deque1.begin();	O(1)
end	Returns an iterator to an object that is one element beyond the last valid value in the sequence. This iterator should not be dereferenced, as it is intended to indicate the end of a sequence. Ex: if (itr == deque1.end()) // end of sequence detected ;	O(1)
front	Returns the first element in the deque.	O(1)
back	Returns the last element in the deque.	O(1)
empty	Returns true if the deque is empty.	O(1)
size	Returns the size of the deque. The size of a deque is the number of elements it contains.	O(1)
push_front	Inserts an element at the beginning of the sequence contained by a deque. Ex: deque1.push_front(3);	O(1)
push_back	Inserts an element at the end of the sequence contained by a deque.	O(1)
insert	Inserts a value into the sequence before the element implied by an iterator. deque1.insert(itr, 3); // insert the value 3 before itr	O(n)
pop_front	Removes the first element of the deque. The deque should not be empty.	O(1)
pop_back	Removes the last element of the deque. The deque should not be empty.	O(1)
erase	There are two forms of this member function. The first accepts a single iterator and removes the element implied by that iterator from the sequence. Ex: deque1.erase(deque1.begin()); The second is intended to erase a subsequence. It accepts a starting and ending iterator and erases the subsequence from [starting, ending). The time complexity of the operation depends on the length of the subsequence being erased. Ex: deque1.erase(deque1.begin(), deque1.end()); // erase the entire deque	O(n)

Notes on Interpreting the Above Table

For the above examples, #include <deque> is assumed to appear at the top of the source file. Also, the following declarations are assumed:

std::deque<int> deque1;

std::deque<int> deque2;

std::deque<int>::iterator itr;

Look in the document for the list container for more notes.