Does C++ map erase elements in loop invalidates iterator? (C++03)

Question

I have this code:

#include <cstdlib>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
#include <stdint.h>

class Table
{
public:
  std::map<uint32_t, std::string> m_map;

  typedef std::map<uint32_t, std::string>::iterator Iterator_t;
  typedef std::map<uint32_t, std::string>::const_iterator ConstIterator_t;

  Table () : m_map () { }

  void
  Erase (Iterator_t entry_it, const std::string & reason)
  {
    std::cout << reason << " " << entry_it->first << ":" << entry_it->second << "\n";
    m_map.erase (entry_it);
//        m_map.erase (entry_it->first);
  }

  bool
  Insert (const uint32_t & key, const std::string & value)
  {
    ConstIterator_t found_it = m_map.find (key);

    if (found_it != m_map.end ())
      {
        std::cout << "Key [" << key << "] already exists\n";
        return false;
      }

    m_map.insert (std::make_pair (key, value));
    std::cout << key << ":" << value << " inserted\n";
    return true;
  }

  void
  Print () const
  {
    std::cout << "Table: ";
    for (ConstIterator_t it = m_map.begin (); it != m_map.end (); ++it)
      {
        std::cout << it->first << ":" << it->second << " ";
      }
    std::cout << "\n";
  }

  void
  Purge ()
  {
    for (Iterator_t it = m_map.begin (); it != m_map.end (); ++it)
      {
        if (it->second.length () <= 4)
          {
            Erase (it, "Erase entry ");
          }
      }
  }
};

int
main (int argc, char** argv)
{
  Table table;

  table.Insert (1, "one");
  table.Insert (2, "two");
  table.Insert (3, "three");
  table.Insert (4, "four");
  table.Insert (5, "nine");
  table.Insert (6, "six");
  table.Insert (7, "seven");
  table.Insert (8, "eight");
  table.Insert (9, "nine");
  table.Print ();
  std::cout << "\n";

  table.Purge ();
  table.Print ();
  std::cout << "\n";

  return 0;
}

That produces the following output:

1:one inserted
2:two inserted
3:three inserted
4:four inserted
5:five inserted
6:six inserted
7:seven inserted
8:eight inserted
9:nine inserted
Table: 1:one 2:two 3:three 4:four 5:nine 6:six 7:seven 8:eight 9:nine 

Erase entry  1:one
Erase entry  2:two
Erase entry  4:four
Erase entry  6:six
Erase entry  9:nine
Table: 3:three 5:five 7:seven 8:eight 

As you can see the 5:five should have been erased, but it wasn't. I don't fully understand why.

The two overloads of m_map.erase () I tried produce the same result. And I couldn't find a version of std::remove_if for maps.

I must point out that this has to be in C++03, and I found only answers for C++11/14. Can you please tell me how to solve this?

Answer 1

As @sam answered, std::map::erase will invalidate the iterator to the erased element. After that the invalid iterator is used for increment operation in for loop, which is undefined behavior.

References and iterators to the erased elements are invalidated.

To solve it, since C++11 you could use the return value of erase, which is the iterator following the removed element. But for C++03, you have to do that manually. e.g.

class Table
{
public:
  ...    
  void
  Purge ()
  {
    for (Iterator_t it = m_map.begin (); it != m_map.end (); )
      {
        if (it->second.length () <= 4)
          {
            Erase (it++, "Erase entry ");
          }
        else
          {
            ++it;
          }
      }
  }
};

The point of the above code is that the increment is performed before erase happens (while it is still a valid iterator). And we take advantage of the fact that it++ will return the original value of it. Thus the evaluation order would be: (1) it is incremented; (2) the original value of it is passed to erase; (3) the element is erased.

Answer 2

Yes, this is undefined behavior.

erase() invalidates the iterator to the removed map value. The loop then attempts to increment the invalidated iterator. It doesn't matter if erase() is called directly inside the loop, or in a function called from the loop. Either way, this is undefined behavior. This is true for both C++03, C++11, and C++14. This is, fundamentally, how maps work.