How to efficiently move (some) items from one std::map to another?

Question

I have two std::map<> objects a and b and would like to move (extract + insert) some elements (nodes) from one map to the other based on some predicate p.

for (auto i = a.begin(); i != a.end(); ++i)
    if (p(*i))
        b.insert(a.extract(i))

This code segfaults in clang. I assume the problem is the increment of i after its node has been extracted from a.

Is the right/only way to fix this by using a post-increment?, E.g.:

for (auto i = a.begin(); i != a.end();)
    if (p(*i))
        b.insert(a.extract(i++))
    else
        ++i;

EDIT: I removed the part about "why this works in gcc?", because I can't reproduce this on my current setup. I'm convinced it used to at some point in time but with gcc 9.2.1 I get a deadlock (instead of a segfault). Either way, incrementing after extract() is not working.

Answer 1

I assume the problem is the increment of i after it's node has been extracted from a.

Indeed. Extraction invalidates iterators to the extracted element, and i is such iterator. The behaviour of incrementing or indirecting through an invalid iterator is undefined.

Why does this seemingly work in gcc but not in clang?

Because the behaviour of the program is undefined.

Is the right/only way to fix this with a post-increment?

It is a right way to fix this. It is not a particularly bad way. If you'd prefer to not repeat the increment, an approach is to use a variable:

for (auto i = a.begin(); i != a.end();) {
    auto current = i++;
    if (p(*current)) {
        // moving is probably unnecessary
        b.insert(a.extract(std::move(current)));
    }
}