[c++] How to remove from a map while iterating it?

How do I remove from a map while iterating it? like:

std::map<K, V> map;
for(auto i : map)
    if(needs_removing(i))
        // remove it from the map

If I use map.erase it will invalidate the iterators

The C++20 draft contains the convenience function std::erase_if.

So you can use that function to do it as a one-liner.

std::map<K, V> map_obj;
//calls needs_removing for each element and erases it, if true was reuturned
std::erase_if(map_obj,needs_removing);
//if you need to pass only part of the key/value pair
std::erase_if(map_obj,[](auto& kv){return needs_removing(kv.first);});

In short "How do I remove from a map while iterating it?"

• With old map impl: You can't
• With new map impl: almost as @KerrekSB suggested. But there are some syntax issues in what he posted.

From GCC map impl (note GXX_EXPERIMENTAL_CXX0X):

#ifdef __GXX_EXPERIMENTAL_CXX0X__
      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // DR 130. Associative erase should return an iterator.
      /**
       *  @brief Erases an element from a %map.
       *  @param  position  An iterator pointing to the element to be erased.
       *  @return An iterator pointing to the element immediately following
       *          @a position prior to the element being erased. If no such 
       *          element exists, end() is returned.
       *
       *  This function erases an element, pointed to by the given
       *  iterator, from a %map.  Note that this function only erases
       *  the element, and that if the element is itself a pointer,
       *  the pointed-to memory is not touched in any way.  Managing
       *  the pointer is the user's responsibility.
       */
      iterator
      erase(iterator __position)
      { return _M_t.erase(__position); }
#else
      /**
       *  @brief Erases an element from a %map.
       *  @param  position  An iterator pointing to the element to be erased.
       *
       *  This function erases an element, pointed to by the given
       *  iterator, from a %map.  Note that this function only erases
       *  the element, and that if the element is itself a pointer,
       *  the pointed-to memory is not touched in any way.  Managing
       *  the pointer is the user's responsibility.
       */
      void
      erase(iterator __position)
      { _M_t.erase(__position); }
#endif

Example with old and new style:

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;
typedef map<int, int> t_myMap;
typedef vector<t_myMap::key_type>  t_myVec;

int main() {

    cout << "main() ENTRY" << endl;

    t_myMap mi;
    mi.insert(t_myMap::value_type(1,1));
    mi.insert(t_myMap::value_type(2,1));
    mi.insert(t_myMap::value_type(3,1));
    mi.insert(t_myMap::value_type(4,1));
    mi.insert(t_myMap::value_type(5,1));
    mi.insert(t_myMap::value_type(6,1));

    cout << "Init" << endl;
    for(t_myMap::const_iterator i = mi.begin(); i != mi.end(); i++)
        cout << '\t' << i->first << '-' << i->second << endl;

    t_myVec markedForDeath;

    for (t_myMap::const_iterator it = mi.begin(); it != mi.end() ; it++)
        if (it->first > 2 && it->first < 5)
            markedForDeath.push_back(it->first);

    for(size_t i = 0; i < markedForDeath.size(); i++)
        // old erase, returns void...
        mi.erase(markedForDeath[i]);

    cout << "after old style erase of 3 & 4.." << endl;
    for(t_myMap::const_iterator i = mi.begin(); i != mi.end(); i++)
        cout << '\t' << i->first << '-' << i->second << endl;

    for (auto it = mi.begin(); it != mi.end(); ) {
        if (it->first == 5)
            // new erase() that returns iter..
            it = mi.erase(it);
        else
            ++it;
    }

    cout << "after new style erase of 5" << endl;
    // new cend/cbegin and lambda..
    for_each(mi.cbegin(), mi.cend(), [](t_myMap::const_reference it){cout << '\t' << it.first << '-' << it.second << endl;});

    return 0;
}

prints:

main() ENTRY
Init
        1-1
        2-1
        3-1
        4-1
        5-1
        6-1
after old style erase of 3 & 4..
        1-1
        2-1
        5-1
        6-1
after new style erase of 5
        1-1
        2-1
        6-1

Process returned 0 (0x0)   execution time : 0.021 s
Press any key to continue.

I personally prefer this pattern which is slightly clearer and simpler, at the expense of an extra variable:

for (auto it = m.cbegin(), next_it = it; it != m.cend(); it = next_it)
{
  ++next_it;
  if (must_delete)
  {
    m.erase(it);
  }
}

Advantages of this approach:

• the for loop incrementor makes sense as an incrementor;
• the erase operation is a simple erase, rather than being mixed in with increment logic;
• after the first line of the loop body, the meaning of it and next_it remain fixed throughout the iteration, allowing you to easily add additional statements referring to them without headscratching over whether they will work as intended (except of course that you cannot use it after erasing it).

Assuming C++11, here is a one-liner loop body, if this is consistent with your programming style:

using Map = std::map<K,V>;
Map map;

// Erase members that satisfy needs_removing(itr)
for (Map::const_iterator itr = map.cbegin() ; itr != map.cend() ; )
  itr = needs_removing(itr) ? map.erase(itr) : std::next(itr);

A couple of other minor style changes:

• Show declared type (Map::const_iterator) when possible/convenient, over using auto.
• Use using for template types, to make ancillary types (Map::const_iterator) easier to read/maintain.

Pretty sad, eh? The way I usually do it is build up a container of iterators instead of deleting during traversal. Then loop through the container and use map.erase()

std::map<K,V> map;
std::list< std::map<K,V>::iterator > iteratorList;

for(auto i : map ){
    if ( needs_removing(i)){
        iteratorList.push_back(i);
    }
}
for(auto i : iteratorList){
    map.erase(*i)
}