C++ 映射擦除循环中的元素会使迭代器无效吗？ (C++03)

Question

我有这个代码：

#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;
}

产生以下输出：

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

如您所见，5:five 应该已被删除，但事实并非如此。我不完全明白为什么。

我试过 m_map.erase () 的两个重载产生相同的结果。我找不到地图的 std::remove_if 版本。

我必须指出这个 必须在 C++03 中，我只找到了 C++11/14 的答案。你能告诉我如何解决这个问题吗？

Answer 1

是的，这是未定义的行为。

erase() 使指向已删除映射值的迭代器无效。然后循环尝试递增无效的迭代器。 erase() 是直接在循环内部调用，还是在循环调用的函数中调用都没有关系。无论哪种方式，这都是未定义的行为。 C++03、C++11 和 C++14 都是如此。从根本上说，这就是地图的工作原理。

Answer 2

正如@sam 回答的那样，std::map::erase 将使指向已删除元素的迭代器无效。之后无效的迭代器用于for循环中的增量操作，这是未定义的行为。

References and iterators to the erased elements are invalidated.

为了解决这个问题，从 C++11 开始，您可以使用 erase 的 return 值，它是被删除元素之后的迭代器。但是对于 C++03，您必须手动执行此操作。例如

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;
          }
      }
  }
};

上面代码的要点是增量是在 erase 发生之前执行的（而 it 仍然是一个有效的迭代器）。我们利用 it++ 将 return it 的原始值这一事实。因此求值顺序为： (1) it 递增； (2)将it的原值传给erase； (3) 元素为erased。

C++ 映射擦除循环中的元素会使迭代器无效吗？ (C++03)

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

c++

dictionary

iterator

c++03

erase