如何从一个地图,而迭代它?

我如何从一个地图,而迭代它?如:

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

如果我使用map.erase,它将使迭代器无效

161505 次浏览

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

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

注意,这里我们实际上需要一个普通的for循环,因为我们正在修改容器本身。基于范围的循环应该严格保留在只关心元素的情况下。RBFL的语法甚至没有公开循环体中的容器,这一点很清楚。

在c++ 11之前,你不能擦除const-iterator。你可能会说:

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

从容器中删除一个元素与元素的常量性并不矛盾。通过类比,delete p总是完全合法的,其中p是指向常量的指针。刚毅并不束缚一生;c++中的const值仍然可以停止存在。

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

简而言之,“如何在迭代映射时从映射中删除?”

  • 用旧地图impl:你不能
  • 新地图impl:几乎像@KerrekSB建议的那样。但是他发布的内容有一些语法问题。

从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

新旧风格的例子:

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

打印:

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.

我个人更喜欢这种模式,它更清晰更简单,但牺牲了一个额外的变量:

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

这种方法的优点:

  • for循环的增量器作为增量器是有意义的;
  • 擦除操作是简单的擦除,而不是与增量逻辑混合在一起;
  • 在循环体的第一行之后,itnext_it的含义在整个迭代过程中保持固定,允许您轻松添加引用它们的额外语句,而不必担心它们是否会像预期的那样工作(当然,除了在删除it后不能使用它)。

假设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);

其他一些较小的风格变化:

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

c++ 20草案包含方便函数std::erase_if

你可以用这个函数来做一行代码。

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