CODEWITHSUNDEEP
c++c++11std
muffel
muffel

Reputation: 7390

Iterate over std::multimap and delete certain entries

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.

Upvotes: 1

Views: 2834

Answers (1)

Karl Nicoll
Karl Nicoll

Reputation: 16439

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(...)).

Upvotes: 5

Related Questions