deque: two-ended operations and the limits of stability

Random access does not mean physical contiguity

deque fits work queues that keep adding at one end and removing at the other, and it can still reach a middle element by subscript in constant time. The standard does not require the elements to be contiguous, so &d[0] is not the start of an array covering the whole container and must not be handed to a function that needs a contiguous buffer. Choose vector for that interface, or copy explicitly into contiguous storage.

Typical implementations use several data blocks plus a block map, which explains how they combine two-ended growth with random access. Block size, map layout, and memory overhead are not standard promises. deque has no capacity() or reserve() like vector, so you cannot reserve one total capacity and then deduce iterator stability from that reservation. Address arithmetic that assumes one slab of memory is therefore a category error even when every subscript happens to work.

The ends are cheap; the middle still moves

The standard gives constant-time complexity for inserting a single element at either end. Insertion at a general position is linear in the number of inserted elements plus the distance to the nearer end. Erasure in the middle can likewise move a prefix or a suffix. That complexity is not a latency bound for a real-time system; underlying allocation can still take non-trivial time.

If the main work is advancing from the ends, deque avoids the linear shift vector pays to erase the first element repeatedly. If the main work is a compact scan, vector often has better locality. Choose between them from access pattern and address requirements, not from seeing a constant-complexity claim and asserting that deque is always faster. A tight inner loop that walks every element still cares about cache lines, and a blocky layout can lose there even while both ends stay cheap to update.

Judge element references, iterators, and end separately

Insertion at the ends does not invalidate references and pointers to existing elements, but it invalidates all iterators. Insertion in the middle invalidates existing references as well. That distinction is a standard interface guarantee. You cannot infer that an old iterator may still be incremented, compared, or dereferenced merely because "the address did not change." The example keeps only an element pointer across a tail insert, then obtains an iterator again afterwards.

Erasing the last element invalidates the old past-the-end iterator and handles to the erased element. Erasing only the first element, without also erasing the last, invalidates only handles to the erased element. Erasing a middle range that contains neither the first nor the last element invalidates all iterators and references. An empty deque must not call front, back, or pop. Check empty first, and do not cache end across a changing queue.

Pitfalls

• After push_front or push_back, a saved element pointer can still be valid while a saved iterator is already invalid. The two must not be treated as the same kind of handle.
• The special stability of pop_front requires that the last element was not also erased. When only one element remains, that pop is also an erasure of the last element.

Minimum C++11 · complete program · Download .cpp

#include <cassert>
#include <deque>
#include <iostream>

int main() {
    std::deque<int> jobs{10, 20, 30};
    int* middle = &jobs[1];
    jobs.push_front(5);
    jobs.push_back(40);
    assert(*middle == 20 && middle == &jobs[2]);

    auto keep = jobs.begin() + 2;
    jobs.pop_front();
    assert(*keep == 20);
    assert(keep == jobs.begin() + 1);
    jobs.pop_back();
    assert(*keep == 20);
    assert((jobs == std::deque<int>{10, 20, 30}));
    std::cout << jobs.front() << ' ' << *keep << ' ' << jobs.back() << '\n';
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-deque.cpp -o example && ./example

Expected result

10 20 30

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A non-empty deque holds an int* p to the first element and an iterator it. Then push_back adds one element. Which handles can still access the original first element? How do you fix traversal code?

Check the sources

• Working draft [deque.modifiers]: position-dependent invalidation and complexity

Drafts and official chapters change. The version mark is only the example’s minimum.