CODEWITHSUNDEEP
c++iterator
frankelot
frankelot

Reputation: 14409

C++ Erase key-value in map while iterating over it

The following C++ code seems to work, and I'm curious to learn how:

    std::map<char,char> mymap;
    mymap['a'] = 'A'; mymap['b'] = 'B'; mymap['c'] = 'C';
    mymap['d'] = 'D'; mymap['e'] = 'E'; mymap['f'] = 'F';
    mymap['g'] = 'G'; mymap['h'] = 'H'; mymap['i'] = 'I';

    bool erase = true;
    for (auto& [key, value] : mymap) {
        if (erase) mymap.erase(key); // Erasing every other item!!
        erase = !erase;
    }

I'm modifying the map while iterating over it. Coming from the JVM world I was expecting a CuncurrentModificationException of sorts... but it seems to work fine in C++.

Is this actually breaking and I'm just getting lucky? If not, how does this work under the hood?

Most examples of doing this use iterators instead, I'm guessing there's a reason for that? This way look cleaner to me, I doubt someone would pick the more verbose and less legible for (auto& it = mymap::begin(); it != mymap::end; ) { it++ } approach without a good reason for it.

Upvotes: 2

Views: 1461

Answers (2)

Phil1970
Phil1970

Reputation: 2623

You mainly have to write something like that if you want to remove every other item:

for (auto it = mymap.begin, itEnd = mymap.end(); it != itEnd; ++it)
{
    auto itTemp = it;
    ++it;
    mymap.erase(itTemp);
    if (it == itEnd)
    {
        break;
    }
}

That is, you have to make a copy of the iterator so that you can still have a valid iterator after erase the item.

Note that the above code is correct for a map but would not works for a vector for example.

This is why you have to read the documentation each time you do an operation that might invalidate iterators, references or pointers to items if you don't know the rules.

For a map, see http://www.cplusplus.com/reference/map/map/erase/.

Update

The first 3 lines of the loop can be replaced in C++ 11 with

it = mymap.erase(it);

as the newer function returns an iterator to next element.

Upvotes: 2

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275500

C++ std uses narrow contracts to permit programs to be faster.

A narrow contract is one where not every operation has a guaranteed result. If you violate the terms of the contract, C++ places no guarantees on the behaviour of your program.

In this case, you destroy an element while using an iterator referring to it to iterate. This invalidates the iterator, and the implicit ++ advance operation in the for(;) loop then violates your contract with the std library.

With a wide contract, you'd get something like an exception here. With a weak contract, you get undefined behaviour. Sometimes it "works", sometimes it crashes, sometimes it emails your browser history to your grandmother and deletes your gmail account.

All are valid responses to violating the contract. The C++ standard places no restrictions on what the executable does. This can include time travel (and no, this one isn't a joke; UB permits the compiler to change what it did on lines before the program reached the UB).

I personally write a remove_erase_if algorithm to solve this problem once. And yes, it uses iterators.

Upvotes: 5

Related Questions