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
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 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 for
loop 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.
Edit. Pre-C++11, you could not erase const-iterators. There you would have to say:
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 p
where p
is a pointer-to-constant. Constness does not constrain lifetime; const values in C++ can still stop existing.
for (int i = 0; i < v.size(); i++)
. Here we have to say v[i]
inside the loop, i.e. we must explicitly mention the container. The RBFL on the other hand introduces the loop variable that is directly usable as the value, and so no knowledge of the container is required inside the loop. This is a clue to the intended usage of the RBFL for loops that do not have to know about the container. Erasing is the complete opposite situation, where it's all about the container.
Commented
Nov 22, 2011 at 22:41
it
to get the next, valid iterator, and then erase the old one. It doesn't work the other way round!
Commented
Nov 22, 2011 at 22:55
it = v.erase(it);
now works for maps too.That is, erase() on all associative elements now returns the next iterator. So the old kludge that required a post-increment++ within the delete(), is no longer needed. This (if true) is a Good Thing, as the kludge relied on overridden-post-increment-within-a-function-call magic, "fixed" by newbie maintainers to take the increment out of the function call, or to swap it to a preincrement "because that's just a style thing", etc.
Commented
Jan 29, 2015 at 23:11
it++
in the if
and else
blocks? wouldn't it be enough to call it once after these?
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:
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).C++20 has a convenience overload of std::erase_if
for std::map
.
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 returned
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); });
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:
Map::const_iterator
) when possible/convenient, over using auto
.using
for template types, to make ancillary types (Map::const_iterator
) easier to read/maintain.std::map
key and/or value types.
In short "How do I remove from a map while iterating it?"
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.
if(mi.empty()) break;
.
Commented
Jun 10, 2020 at 8:28
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)
}