std::erase_if delete an extra elements on std::vector?

Viewed 565

I use std::erase_if to erase half the elements from containers using a captured counter as follows. C++20 compiled with gcc10

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>

int main()
{
    {
        std::vector<int> container(10);
        std::cout << container.size() << std::endl;
        std::erase_if(container, [i = 0u](auto&&...) mutable { return i++ % 2 == 0; });
        std::cout << container.size() << std::endl;
    }
    std::cout << std::endl;
    {
        std::map<int, int> container;
        for (int i = 0; i < 10; i++) {
            container.emplace(i, i);
        }
        std::cout << container.size() << std::endl;
        std::erase_if(container, [i = 0u](auto&&...) mutable { return i++ % 2 == 0; });
        std::cout << container.size() << std::endl;
    }
    std::cout << std::endl;
    {
        std::unordered_map<int, int> container;
        for (int i = 0; i < 10; i++) {
            container.emplace(i, i);
        }
        std::cout << container.size() << std::endl;
        std::erase_if(container, [i = 0u](auto&&...) mutable { return i++ % 2 == 0; });
        std::cout << container.size() << std::endl;
    }
}

The output is unexpected. For vector, an extra element is removed:

10
4

10
5

10
5

I print out the result and it seems like vector[1] is the unexpectedly removed element

Granted that this is not usually a normal usage for erase_if but I'm still curious why it happens only for vector but not for the other map. I'd guess it has something to do with the iterator type shenanigan. Appreciate if someone could give a detailed explanation.

1 Answers

remove_if takes a Predicate. And the standard library requires that a Predicate type:

Given a glvalue u of type (possibly const) T that designates the same object as *first, pred(u) shall be a valid expression that is equal to pred(*first).

Your predicate changes its internal state. As such, calling it twice with the same element will yield different results. That means it does not fulfill the requirements of Predicate.

And therefore, undefined behavior ensues.

Related