Deque (C++)

C++ Standard Library
fstream iomanip ios iostream sstream string
Standard Template Library
algorithm bitset deque functional iterator list map set stack queue vector
C++11
array forward_list unordered_map unordered_set
C Standard Library
Data types Character classification Strings Mathematics File input/output Date/time Localization Memory allocation Program control Miscellaneous headers: <assert.h> <errno.h> <iso646.h> <setjmp.h> <signal.h> <stdarg.h> <wchar.h>
v · d · e

In the C++ Standard Library, std::deque is a container class template that implements a double-ended queue. It provides similar computational complexity to std::vector for most operations, with the notable exception that it provides amortized constant-time insertion and removal from both ends of the element sequence. Unlike vector, deque uses discontiguous blocks of memory, and provides no means to control the capacity of the container and the moment of reallocation of memory. Like vector, deque offers support for random access iterators, and insertion and removal of elements invalidates all iterators to the deque.

deque was already part of the Standard Template Library on which the C++ Standard Library was based.

Design

The deque data structure is defined in header file <deque>. This, like all other standard library components, is contained in namespace std.

Deque is a generalized version of stack and queue. Deque is the sequential data structure. In deque data can be inserted both at the back as well as at the front of the container(tail and head in case of queue).

deque has standard functions for accessing elements, for entering elements at the back and at the front, removing elements from back and the front and finding the size of deque. All the entered elements in deque should be of similar datatypes.

Properties observed with the deque sequences are :

• Position index can be used to have an access to any individual element.
• No particular order is fixed for doing any kinda iteration over the elements
• Removal and addition of elements can be done efficiently from the beginning and the end of the list.

Overview of Functions

• • deque::deque(constructor) - Constructs the deque from variety of sources
  • deque::~deque(destructor) - Destructs the deque and the contained elements
  • deque::operator= - Assigns values to the deque
  • deque::assign - Assigns values to the deque
  • deque::get_allocator - Returns the allocator used to allocate memory for the elements
• Element access
  • deque::at - Accesses specified element with bounds checking.
  • deque::operator[] - Accesses specified element
  • deque::front - Accesses the first element
  • deque::back - Accesses the last element
• Iterators
  • deque::begin - Returns an iterator to the beginning of the deque
  • deque::end - Returns an iterator to the end of the deque
  • deque::rbegin - Returns a reverse iterator to the reverse beginning of the deque
  • deque::rend - Returns a reverse iterator to the reverse end of the deque
• Capacity
  • deque::empty - Checks whether the deque is empty
  • deque::size - Returns the number of elements in the deque.
  • deque::max_size - Returns the maximum possible number of elements in the deque.
  • deque::shrink_to_fit (C++11) - Reduces memory usage by freeing unused memory
• Modifiers
  • deque::clear - Clears the contents
  • deque::insert - Inserts elements
  • deque::emplace (C++11) - Constructs elements in-place
  • deque::erase - Erases elements
  • deque::push_front - Inserts elements to the beginning
  • deque::emplace_front (C++11) - Constructs elements in-place at the beginning
  • deque::pop_front - Removes the first element
  • deque::push_back - Inserts elements to the end
  • deque::emplace_back (C++11) - Constructs elements in-place at the end
  • deque::pop_back - Removes the last element
  • deque::resize - Changes the number of stored elements
  • deque::swap - Swaps the contents with another deque

Implementation of a deque can be realised in many ways, but the two most important and most efficient ways are

• Doubly linked list
• Dynamic array

Basic Algorithms and Operations of the functions

The basic operations done in deque are :

• Adding an element to the deque.

In doubly linked lists, it is possible to add the elements from any position in the queue. But however elements can be added to the double ended queue from both the ends i.e. it is possible to enque elements into the queue through head and tail only. This is what makes deque different from other doubly linked list. To add an element in the start position, function named push_front.

Example

// deque::push_front example
#include <iostream>
#include <deque>
 
int main ()
{
    std::deque<int> example(2, 200);     // two ints with a value of 200
    example.push_front(400);
    example.push_front(333);
    std::cout << "example contains:";
    for (auto i = example.begin(); i != example.end(); ++i) {
        std::cout << " " << *i;
    }
    std::cout << std::endl;
}

The time complexity of this function is constant. Being a void function, the return value of this function is none.

References

• Josuttis, Nicolai M. (1999). The C++ Standard Library. Addison-Wesley. ISBN 0-201-37926-0. 

External links

• C++ reference for std::deque