Iterate over std::multimap and delete certain entries

Question

I want to iterate over all items in a std::multimap (all values of all keys), and delete all entries that satisfy some condition:

#include <map>

typedef int KEY_TYPE;
typedef int VAL_TYPE;

bool shouldRemove(const KEY_TYPE&, const VAL_TYPE&);

void removeFromMap(std::multimap<KEY_TYPE,VAL_TYPE>& map){
    for (auto it = map.begin(); it != map.end(); it++){
        if (shouldRemove(it->first,it->second))
            map.erase(it);
    }
}

The iteration works unless the first item gets deleted, and the following error is thrown then:

map/set iterator not incrementable

How can the removeFromMap function be rewritten in order to work properly? The code should work for all kinds of key- and value types of the map.

I am using C++ 11 and Visual Studio 2013.

Normally one use the return value of map.erase(iterator), since it returns the iterator to the next element or end, if it was the last element — AquilaRapax, Jun 10 '14 at 13:24
@KarlNicoll However after digging more deeply, the Erase-remove idiom is not applicable on `std::set`, `std::map` and friends, because their value type is not `MoveAssignable`. And I have no idea how to implement it on such containers anyway, as it works by shifting elements. — Erbureth, Jun 10 '14 at 14:09

Karl Nicoll · Accepted Answer · 2014-06-10T15:07:55.473

5

You need to increment your iterator before you do the erase. When you do map.erase(it); the iterator it becomes invalid. However, other iterators in the map will still be valid. Therefore you can fix this by doing a post-increment on the iterator...

auto it = map.begin();
const auto end = map.end();

while (it != end)
{
    if (shouldRemove(it->first,it->second))
    {
        map.erase(it++);
                 // ^^ Note the increment here.
    }
    else
    {
       ++it;
    }
}

The post-increment applied to it inside the map.erase() parameters will ensure that it remains valid after the item is erased by incrementing the iterator to point to the next item in the map just before erasing.

map.erase(it++);

... is functionally equivalent to...

auto toEraseIterator = it;    // Remember the iterator to the item we want to erase.
++it;                         // Move to the next item in the map.
map.erase(toEraseIterator);   // Erase the item.

As @imbtfab points out in the comments, you can also use it = map.erase(it) to do the same thing in C++11 without the need for post-incrementing.

Note also that the for loop has now been changed to a while loop since we're controlling the iterator manually.

Additionally, if you're looking to make your removeFromMap function as generic as possible, you should consider using template parameters and pass your iterators in directly, rather than passing in a reference to the multi-map. This will allow you to use any map-style container type, rather than forcing a multimap to be pased in.

e.g.

template <typename Iterator>
void removeFromMap(Iterator it, const Iterator &end){
    ...
}

This is how the standard C++ <algorithm> functions do it also (e.g. std::sort(...)).

edited Jun 10 '14 at 15:07

answered Jun 10 '14 at 13:16

Karl Nicoll

16,090
3
51
65

that works for me, thanks! However, I do not understand why using the post-increment way fixes the problem - why do `erase(it); it++;` and `erase(it++);` differ? – muffel Jun 10 '14 at 13:26
1

When you do `erase(it)`, the variable `it` is no longer usable. Trying to increment `it` after it has been erased is *undefined behaviour*. By doing `erase(it++)`, you increment `it` *before* erase is called, but still pass the old un-incremented iterator into the `erase` function. It is equivalent to the following: `auto newIt = std::next(it); map.erase(it); it = newIt;`. You might get a better understanding by [seeing how the post-increment operator works](https://stackoverflow.com/questions/484462/difference-between-i-and-i-in-a-loop). – Karl Nicoll Jun 10 '14 at 13:33
@Karl: In your comment, you want `auto newIt = std::next(it)` (or something else. What you have is incrementing it as well as assigning the incremented value to newIt. – Dave S Jun 10 '14 at 13:36
2

Since this is C++11, avoid the confusion, just use `it = map.erase(it);` – imbtfab Jun 10 '14 at 13:40
@imbtfab - You should add that as another answer, rather than letting me take all the credit for it :-) – Karl Nicoll Jun 10 '14 at 13:42
Help yourself, there's enough answers here already...and I'd just be copying most of yours anyway ;) – imbtfab Jun 10 '14 at 14:04

Iterate over std::multimap and delete certain entries

1 Answers1