Double-Ended Queues using std::deque

Iterator invalidation rules for std::deque

When do std::deque operations invalidate iterators?

Vector art representing computer hardware

An iterator is considered invalidated if it no longer points to the same element it originally pointed to.

For std::deque, the iterator invalidation rules are as follows:

  1. End iterators: The end iterator (the one returned by end()) is always invalidated when the deque is modified.
  2. Insertion: Insertion in the middle of the deque invalidates all iterators. Insertion at either end (using push_front(), emplace_front(), push_back(), emplace_back()) only invalidates the end iterator.
  3. Erasure: Erasing an element in the middle of the deque invalidates all iterators. Erasing an element at either end (using pop_front() or pop_back()) only invalidates the end iterator and the iterators to the erased elements.
  4. Clear: Calling clear() invalidates all iterators.
  5. Swap: Calling swap() invalidates all iterators.

Here's an example demonstrating iterator invalidation:

#include <deque>
#include <iostream>

int main() {
  std::deque<int> d{1, 2, 3, 4, 5};

  auto it = d.begin();
  auto end = d.end();


  // This is fine, it still points to the element 1
  std::cout << *it << "\n"; 
  // This is invalid, end iterator is invalidated
  std::cout << *(end - 1) << "\n"; 

  d.insert(it + 2, 10);  
  // This is invalid, it no longer points to 1
  std::cout << *it << "\n"; 

The previous example results in undefined behaviour. With debug flags enabled, the compiler may detect the problem and throw a run time error:

cannot deference out of range deque iterator

To avoid issues with iterator invalidation, it's often best to reacquire iterators after any operation that could potentially invalidate them.

Answers to questions are automatically generated and may not have been reviewed.

Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved