Deque (std::deque)

Deque (std::deque)

A deque (short for double-ended queue) can grow and shrink from both ends, unlike a vector which only grows well at the back.

Create it

#include <deque>

std::deque<int> d;

Work both ends with push and pop

d.push_back(3);    // {3}
d.push_front(1);   // {1, 3}
d.push_back(4);    // {1, 3, 4}
d.pop_front();     // {3, 4}
d.pop_back();      // {3}

• push_front(v) / push_back(v) add from either side.
• pop_front() / pop_back() remove from either side.

Read the ends

d.front()   // the leftmost element
d.back()    // the rightmost element

Why both ends matter

A vector is great at the back but a pain at the front, because every element must shift a spot. A deque is designed so adding or removing at both ends stays cheap, and like a vector it still offers index access such as d[1].

TL;DR

• A deque adds and removes cheaply at both ends.
• push_front / push_back, and pop_front / pop_back do the work.
• front() and back() read the two ends.
• It keeps the index access of a vector but is stronger at the front end.
• Pick a deque when your algorithm touches both ends of the data.