2

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.

frankelot
  • 13,666
  • 16
  • 54
  • 89
  • 1
    I think this is undefined behavior. Follow the pattern in this answer https://stackoverflow.com/questions/8628951/remove-elements-of-a-vector-inside-the-loop – wcochran Oct 21 '20 at 02:33
  • C++ usually does not do that kind of validation at run-time. But some DEBUG library might do. – Phil1970 Oct 21 '20 at 02:44
  • @wcochran I check that question but didn't really find the answer I'm looking for – frankelot Oct 21 '20 at 02:48
  • @Phil1970 mm so you're implying this IS BAD and it's just failing silently for me? I should not do this? – frankelot Oct 21 '20 at 02:49
  • Mostly... if you want to do that kind of thing, you have to read the documentation as rules vary according to container type. See **iterator validity** in http://www.cplusplus.com/reference/map/map/erase/ for more information. – Phil1970 Oct 21 '20 at 03:00
  • The docs say "The elements removed are modified. Concurrently accessing other elements is safe, although iterating ranges in the container is not."... Honestly I don't know what to make of it. – frankelot Oct 21 '20 at 03:06
  • Also "All other iterators, pointers and references keep their validity. " I'm not using iterators (at least not explicitly that is)... This sounds like I can get away with what I'm doing here? I find the documentation very open ended – frankelot Oct 21 '20 at 03:08
  • I have a personal rule of never modifying a container that you're iterating over, and that rule has probably saved me countless times over the years. But I think the tree data structure behind a `map` is safe to modify this way because of the guarantees by the standard. Unable to quote the relevant rules though. – Mark Ransom Oct 21 '20 at 03:10
  • The loop `for (auto& [key, value] : mymap)` definitely has an iterator to the current item thus deleting that item either by key or iterator will invalidate that iterator and cause undefined behavior. Even if it appears to works, it might broke using another compiler, changing compiler option or even depending on the exact code. – Phil1970 Oct 21 '20 at 03:15
  • @FRR If you want to write correct C++ code, you need to learn how to properly interpret the documentation! **Buy a few good C++ books and read them!** – Phil1970 Oct 21 '20 at 03:29

2 Answers2

5

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.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • That is for the details answer!! For future reference, where are the rules of this contract? Is it this one: "Invalidates iterators and references at or after the point of the erase, including the end() iterator. " From: https://en.cppreference.com/w/cpp/container/vector/erase – frankelot Oct 21 '20 at 03:34
  • @FRR In you question, you are talking about a `map` and not `vector`. **You have to read the appropriate documentation for the container you are using!** – Phil1970 Oct 21 '20 at 03:37
  • I’ve usually heard it called a *narrow* contract, not a weak one. – Davis Herring Oct 21 '20 at 04:01
  • You are rigth, apologies it was late and I was on my phone. For map it says "References and iterators to the erased elements are invalidated. Other references and iterators are not affected."... does this mean my original code is fine? – frankelot Oct 21 '20 at 09:59
  • @FRR `if (erase) mymap.erase(key);` that line invalidates the current iterator in the `for(:)` loop generated code. `for(:)` loops are defined as generating certain code. – Yakk - Adam Nevraumont Oct 21 '20 at 12:55
  • @Yakk-AdamNevraumont correct, it invalidates the current iterator, so as long as I don't touch that one anymore, I should be fine, right? – frankelot Oct 21 '20 at 21:52
  • 2
    @frr no, because loop then does a `++` to get the next one. – Yakk - Adam Nevraumont Oct 21 '20 at 23:54
  • This is the answer I was looking for!! Thanks @Yakk this makes a lot of sense in hindsight – frankelot Oct 23 '20 at 00:25
2

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.

Phil1970
  • 2,605
  • 2
  • 14
  • 15
  • Since C++11 you don't need to have a copy. Look at the C++11 tab in your link. – 273K Oct 21 '20 at 03:29
  • @S.M. No, it will not handle the case where you are deleting the last item as `it` would pointing to the end and be incremented once again by the for loop before the check. – Phil1970 Oct 21 '20 at 03:35
  • Your are right, the OP wished to remove over one element. Missed it. – 273K Oct 21 '20 at 03:40
  • Thank you for your reply! This is what I'm looking for, right: "Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity.". This means my original code should work OK – frankelot Oct 21 '20 at 10:15
  • You are incorrect. You are invalidating current item iterator so advancing to next position is undefined behavior. See https://en.cppreference.com/w/cpp/language/range-for for an explanation of range based for loop. In practice, for most container you cannot modify a container from inside a range-based for loop (except if you break out of the loop immediatly of course) and when using iterators, you need to be careful as rules are different for every containers. – Phil1970 Oct 22 '20 at 01:43
  • Why we have incremented the iterator in the for (;;++it)? when already we incremented the iterator inside the for loop. – Prakash GiBBs Jan 13 '23 at 07:39
  • @PrakashGiBBs If you look original code, it seems that he wants to remove every other item (as mentionned in my first sentence). That's why the iterator is incremented twice (once for the item to remove and once for the item to skip). – Phil1970 Jan 14 '23 at 13:21