Using std::deque::iterator (in C++ STL) for searching and deleting certain elements

Question

I have encountered a problem invoking the following code:

#include<deque>
using namespace std;

deque<int> deq = {0,1,2,3,4,5,6,7,8};

for(auto it = deq.begin(); it != deq.end(); it++){
    if(*it%2 == 0)
        deq.erase(it);
}

which resulted in a segmentation fault. After looking into the problem I found that the problem resides in the way the STL manages iterators for deques: if the element being erased is closer to the end of the deque, the iterator used to point to the erased element will now point to the NEXT element, but not the previous element as vector::iterator does. I understand that modifying the loop condition from it != deq.end() to it < deq.end() could possibly solve the problem, but I just wonder if there is a way to traverse & erase certain element in a deque in the "standard form" so that the code can be compatible to other container types as well.

Solution 1

http://en.cppreference.com/w/cpp/container/deque/erase

All iterators and references are invalidated [...]

Return value : iterator following the last removed element.

This is a common pattern when removing elements from an STL container inside a loop:

for (auto i = c.begin(); i != c.end() ; /*NOTE: no incrementation of the iterator here*/) {
  if (condition)
    i = c.erase(i); // erase returns the next iterator
  else
    ++i; // otherwise increment it by yourself
}

Or as chris mentioned you could just use std::remove_if.

Solution 2

To use the erase-remove idiom, you'd do something like:

deq.erase(std::remove_if(deq.begin(),
                         deq.end(),
                         [](int i) { return i%2 == 0; }),
          deq.end());

Be sure to #include <algorithm> to make std::remove_if available.