C++ 如何在迭代时从地图中删除？

How to remove from a map while iterating it?

提问by Dani

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.eraseit will invalidate the iterators

如果我使用map.erase它会使迭代器失效

回答by Kerrek SB

The standard associative-container erase idiom:

标准的关联容器擦除习惯用法：

for (auto it = m.cbegin(); it != m.cend() /* not hoisted */; /* no increment */)
{
  if (must_delete)
  {
    m.erase(it++);    // or "it = m.erase(it)" since C++11
  }
  else
  {
    ++it;
  }
}

Note that we really want an ordinary forloop here, since we are modifying the container itself. The range-based loop should be strictly reserved for situations where we only care about the elements. The syntax for the RBFL makes this clear by not even exposing the container inside the loop body.

请注意，我们真的想要一个普通的for循环，因为我们正在修改容器本身。基于范围的循环应该严格保留用于我们只关心元素的情况。RBFL 的语法通过甚至不暴露循环体内的容器来清楚地说明这一点。

Edit.Pre-C++11, you could not erase const-iterators. There you would have to say:

编辑。在 C++11 之前，您无法擦除常量迭代器。在那里你必须说：

for (std::map<K,V>::iterator it = m.begin(); it != m.end(); ) { /* ... */ }

Erasing an element from a container is not at odds with constness of the element. By analogy, it has always been perfectly legitimate to delete pwhere pis a pointer-to-constant. Constness does not constrain lifetime; const values in C++ can still stop existing.

从容器中擦除元素与元素的常量性并不矛盾。以此类推，指向常量指针的delete pwhere一直是完全合法的p。稳定性不限制寿命；C++ 中的 const 值仍然可以停止存在。

回答by D Coetzee

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 itand next_itremain 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 itafter erasing it).

• for 循环增量器作为增量器是有意义的；
• 擦除操作是简单的擦除，而不是与增量逻辑混在一起；
• 在循环体的第一行之后，it和的含义next_it在整个迭代过程中保持不变，使您可以轻松添加引用它们的其他语句，而无需担心它们是否会按预期工作（当然，it擦除后无法使用） .

回答by Kashyap

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.

• 使用旧地图实现：你不能
• 使用新地图实现：几乎就像@KerrekSB 建议的那样。但是他发布的内容存在一些语法问题。

From GCC map impl (note GXX_EXPERIMENTAL_CXX0X):

来自 GCC 地图 impl（注意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.

回答by Michael Daum

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

很伤心吧？我通常这样做的方式是建立一个迭代器容器，而不是在遍历过程中删除。然后循环遍历容器并使用 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)
}

回答by PeterT

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

C++20 草案包含便利功能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);});

回答by Matt

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

假设 C++11，这是一个单行循环体，如果这与您的编程风格一致：

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 usingfor template types, to make ancillary types (Map::const_iterator) easier to read/maintain.

• Map::const_iterator在可能/方便时显示声明的类型 ( )，而不是使用auto.
• 使用using模板类型，使辅助类型（Map::const_iterator）更易于阅读/维护。