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.

Related to, or dup of: https://stackoverflow.com/questions/6438086/iterator-invalidation-rules — Eljay, Nov 13 '19 at 14:32
@Eljay In my opinion, the new map “[node handle](https://en.cppreference.com/w/cpp/container/node_handle)” splicing API in C++17 is sufficiently specialized to warrant its own question. I hope this isn’t closed as a duplicate. — NicholasM, Nov 13 '19 at 14:39
Possible duplicate of [Deleting elements from std::set while iterating](https://stackoverflow.com/questions/2874441/deleting-elements-from-stdset-while-iterating). `std::set` and `std::map` are very similar, and as far as I can tell `extract` has the same invalidation implications as `erase`. — François Andrieux, Nov 13 '19 at 14:40
What version of clang and gcc did you use? For me, using clang 8.0 and gcc 7.4, both result in a segfault. — Balázs Kovacsics, Nov 13 '19 at 14:44
I am surprised that this code would work in any compiler. You are not handling the invalidation causing by extract — Iman Kianrostami, Nov 13 '19 at 14:45
Possible duplicate: [better way to move elements from a map to another](https://stackoverflow.com/questions/35544203/better-way-to-move-elements-from-a-map-to-another) — Iman Kianrostami, Nov 13 '19 at 14:46
@Elja please note that I did not ask what the issue with my first version is (I already found out about the invalidation issue from the spec), my question is if there is no better solution than the second (verbose) version. — axxel, Nov 13 '19 at 14:58

eerorika · Accepted Answer · 2019-11-13T15:14:54.323

7

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)));
    }
}

edited Nov 13 '19 at 15:14

answered Nov 13 '19 at 14:57

eerorika

232,697
12
197
326

It's a good way, (reasonably) assuming that copying the iterator's state is less expensive than copying the node. – Spencer Nov 13 '19 at 15:13
@Spencer copying an iterator is usually trivial. But I added a move just in case. – eerorika Nov 13 '19 at 15:17
@Spencer `current` would be left in a moved from state. Whatever that state is won't matter since it is no longer used after that. – eerorika Nov 13 '19 at 16:35
@eeroika Thanks, I looked at your code a little more closely and realized that. – Spencer Nov 13 '19 at 16:36
I like your local variable better than having two icrements but I would suggest a minor improvement: limit the scope of `current` by using c++17s `if (auto current = ++i; p(*current))` syntax. – axxel Nov 13 '19 at 18:00
@axxel You must use post increment. But sure, if statement init (or whatever it's called) is an option. I find separate declaration more readable, and the scope is just as narrow in this case anyway. But if you wanted to write something within the loop after the if, and `current` isn't needed there, then limiting the scope would have merit. – eerorika Nov 13 '19 at 18:04
@eerorika the '++i' was a typo that I just wanted to fix, only to learn that comments can not be edited anymore after 5 minutes ;). – axxel Nov 13 '19 at 18:19

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

1 Answers1