Is it safe to traverse a container during std::remove_if execution?

After the predicate returns true the first time, there will be one unspecified value in the range. That means any subsequent calls of the predicate will count an unspecified value. The count is therefore potentially incorrect, and you may either leave values unaffected that you intend to be discarded, or discard values that should be retained.

You could modify the predicate so it keeps a count of how many times it has returned true, and reduce the range accordingly. For example;

std::size_t count = 0;
auto to_remove = std::remove_if(vec.begin(), vec.end(), [&vec, &count](int n)
{
    bool once = (std::count(vec.begin(), vec.end() - count, n) == 1);
    if (once) ++count;
    return once;
 });

Subtracting an integral value from a vector's end iterator is safe, but that isn't necessarily true for other containers.


You misunderstood how std::remove_if works. The to-be-removed values are not necessarily shifted to the end. See:

Removing is done by shifting (by means of move assignment) the elements in the range in such a way that the elements that are not to be removed appear in the beginning of the range. cppreference

This is the only guarantee for the state of the range. According to my knowledge, it's not forbidden to shift all values around and it would still satisfy the complexity. So it might be possible that some compilers shift the unwanted values to the end but that would be just extra unnecessary work.

An example of possible implementation of removing odd numbers from 1 2 3 4 8 5:

   v               - read position
   1 2 3 4 8 5     - X will denotes shifted from value = unspecified
   ^               - write position
     v          
   1 2 3 4 8 5     1 is odd, ++read
   ^
       v
   2 X 3 4 8 5     2 is even, *write=move(*read), ++both
     ^   
         v
   2 X 3 4 8 5     3 is odd, ++read
     ^
           v
   2 4 3 X 8 5     4 is even, *write=move(*read), ++both
       ^
             v
   2 4 8 X X 5     8 is even, *write=move(*read), ++both
         ^

   2 4 8 X X 5     5 is odd, ++read
         ^         - this points to the new end.

So, in general, you cannot rely on count returning any meaningful values. Since in the case that move==copy (as is for ints) the resulting array is 2 4 8|4 8 5. Which has incorrect count both for the odd and even numbers. In case of std::unique_ptr the X==nullptr and thus the count for nullptr and removed values might be wrong. Other remaining values should not be left in the end part of the array as there were no copies done.

Note that the values are not unspecified as in you cannot know them. They are exactly the results of move assignments which might leave the value in unspecified state. If it specified the state of the moved-from variables ( asstd::unique_ptr does) then they would be known. E.g. if move==swap then the range will be permuted only.


I added some outputs:

#include <algorithm>
#include <iostream>
#include <vector>
#include <mutex>

int main() {
    std::vector<int> vec = {1, 2, 6, 3, 6, 2, 7, 4, 4, 5, 6};

    auto to_remove = std::remove_if(vec.begin(), vec.end(), [&vec](int n) {

        std::cout << "number " << n << ": ";
        for (auto i : vec) std::cout << i << ' ';
        auto c = std::count(vec.begin(), vec.end(), n);
        std::cout << ", count: " << c << std::endl;
        return c == 1;
    });

    vec.erase(to_remove, vec.end());

    for (int i : vec) std::cout << i << ' ';
}

and got

number 1: 1 2 6 3 6 2 7 4 4 5 6 , count: 1
number 2: 1 2 6 3 6 2 7 4 4 5 6 , count: 2
number 6: 2 2 6 3 6 2 7 4 4 5 6 , count: 3
number 3: 2 6 6 3 6 2 7 4 4 5 6 , count: 1
number 6: 2 6 6 3 6 2 7 4 4 5 6 , count: 4
number 2: 2 6 6 3 6 2 7 4 4 5 6 , count: 2
number 7: 2 6 6 2 6 2 7 4 4 5 6 , count: 1
number 4: 2 6 6 2 6 2 7 4 4 5 6 , count: 2
number 4: 2 6 6 2 4 2 7 4 4 5 6 , count: 3
number 5: 2 6 6 2 4 4 7 4 4 5 6 , count: 1
number 6: 2 6 6 2 4 4 7 4 4 5 6 , count: 3
2 6 6 2 4 4 6 

As you can see the counts can be wrong. I'm not able to create an example for your special case but as a rule you have to worry about wrong results.

First the number 4 is counted twice and in the next step the number 4 is counted thrice. The counts are wrong and you can't rely on them.