Removing elements from a C++ map through a for-loop

Question

My STL is a bit rusty, so forgive me for asking a possibly trivial question. Consider the following piece of code:

map<int,int> m;
...
for (auto itr = m.begin(); itr != m.end(); ++itr) {
    if (itr->second == 0) {
        m.erase(itr);
    }
}

The question is: Is it safe to erase elements while looping over the map?

On second thought, I probably should use something like `remove_if`. However, I am still interested in the answer to the question. — Petter, Mar 04 '11 at 09:02
I don't get it - why do you need a loop for this? a map can only ever contain a single key with the value 0. Hence a `find` and then if found, `erase` of that iterator should do the trick! — Nim, Mar 04 '11 at 09:17
Nim, my example was a bit stupid. A better example would be `if (itr->second == 0)` — Petter, Mar 04 '11 at 09:20
@Ben: You should not use `remove_if` on sorted range, it violates the "sorted" assumption by rearranging elements. — Matthieu M., Mar 04 '11 at 09:32

score 26 · Answer 1 · answered Mar 04 '11 at 09:02

26

Yes, but not the way you do it. You're invalidating itr when you erase, then incrementing the invalid iterator.

auto itr = m.begin();
while (itr != m.end()) {
  if (itr->first == 0) {
    m.erase(itr++);
  } else {
    ++itr;
  }
}

answered Mar 04 '11 at 09:02

Erik

88,732
13
198
189

2

auto tmp = ++itr; m.erase(iter); itr = tmp; // This would be more understable ( IMO ). – Jagannath Mar 04 '11 at 09:09
3

It'd also be wrong, you're incrementing before you erase... Did you perhaps intend e.g. `auto tmp=itr; ++itr; m.erase(tmp);` ? – Erik Mar 04 '11 at 09:10
9

@Ben, @Erik: A warning, there are two kinds of `erase` methods in the standard, for node-based containers (`list`, `map`, `set`, ...) use this method, for containers whose `erase` method returns an iterator (like `vector`), the `erase` line should read `itr = m.erase(itr)`. This signature quirk effectively throw a damp on the whole "interchangeability" thing... and so is corrected in C++0x so that all `erase` that did not return anything now return an iterator to the next element :) – Matthieu M. Mar 04 '11 at 09:38
For my own understanding since I use this pattern quite often, can you confirm that this means the `m.erase(itr++);` line can become `itr = m.erase(itr++);` for all containers in C++0x? – dlanod Mar 05 '11 at 21:32
5

@dlanod lose the `++`: `itr = m.erase(itr);` is what it should be, see e.g. http://en.cppreference.com/w/cpp/container/map/erase – rubenvb Jan 13 '13 at 15:37

score 12 · Accepted Answer · edited Jun 02 '15 at 07:44

12

I think that you shouldn't use removed iterator at all - in case of lists this causes serious problems, shouldn't be different for maps.

EDIT by Matthieu M: this code is well-formed in C++0x and allowed as an extension by MSVC.

map<int,int> m;
...
auto itr = m.begin();
while (itr != m.end())
{
    if (itr->second == 0) {
        itr = m.erase(itr);
    }
    else 
    {
        itr++;
    }
}

edited Jun 02 '15 at 07:44

Francesco V.

119
2
10

answered Mar 04 '11 at 09:14

XAder

676
4
12

2

Standard c++ map::erase does *not* return a new iterator, that's a MSVC extension. – Erik Mar 04 '11 at 09:16
This code is ill-formed. There is no version of the erase function that returns an *iterator*. The Visual C++ standard library implementation provides such a return type, but specifically notes that it doesn't conform to the C++ Standard – decltype Mar 04 '11 at 09:17
2

@Xader: I've reverted your edit and added a disclaimer, this code is well-formed in C++0x and is **the** canonical way of removing elements in a container, so the best answer given. (The disclaimer is so that people who don't understand that `auto` means C++0x don't get confused). Standard reference for the nay-sayers: n3225 23.5.1.2 element access. – Matthieu M. Mar 04 '11 at 09:42
@Matthieu: I agree. Since the OP wrote "C++" in his question, I assumed that *auto* was simply being used in the sense "this type is painfully long to write out in C++03, so I'll borrow the C++0x type specifier *auto*, but the example should otherwise be considered C++03," or some such ;) – decltype Mar 04 '11 at 09:53
Thanks, I am using C++0x (as the auto keyword and the c++0x tag suggests) so looks like a good solution. – Petter Mar 06 '11 at 09:41

score 8 · Answer 3 · answered Mar 04 '11 at 09:14

For the example given, It would actually be easier to use the erase overload that takes a key as an argument. This function erases all elements in the map with the given key (for a map, this is always either zero or one element)

map<int,int> m; 
// ...
m.erase(0); // erase all elements with key equivalent to 0

Removing elements from a C++ map through a for-loop

3 Answers3

Linked