285

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

Improve this question
4

6 Answers 6

Reset to default
405

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

22 Comments

@skyhisi: Indeed. This is one of the legitimate uses of the post-increment: First increment it to get the next, valid iterator, and then erase the old one. It doesn't work the other way round!
I read somewhere that in C++11, 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.
why would you call it++ in the if and else blocks? wouldn't it be enough to call it once after these?
@Ewat: No, that's fine.It's the erasing that invalidates the erased iterator; the increment happens before the erasing. This is a poster-child example of the use of post-increment.
it = m.erase(it); is valid for all containers (now, although it wasn't always in the past). m.erase(it++); is valid only for containers that guarantee that only the erased iterator and no other iterators are invalidated on erase operations (which includes std::map but not std::vector; ymmv for other containers). So the posted code is correct for std::map and should be correct for most associative containers, but not necessarily all (e.g. it's very likely to be wrong for a flat_map). To be safe you should use the variant in the comment unless you can't use C++11.
|
69

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 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).
Improve this answer

4 Comments

I can think of another advantage actually, if the loop calls into code which erases that entry being iterated over or previous ones (and the loop is unaware of it) it will work without any harm done. The only restriction is whether something is erasing what is being pointed to by next_it or successors. A totally cleared list/map can be tested against as well.
This answer is simple and clear, even if the loop is more complex and has multiple levels of logic to decide whether or not to delete, or do other various tasks. I've proposed an edit, though, to make it a little simpler. "next_it" can be set to "it" in the for's init to avoid typos, and since the the init and iteration statements both set it and next_it to the same values, you don't need to say "next_it = it;" at the start of the loop.
Keep in mind anyone who uses this answer: You must have "++next_it" inside the for loop, and not in the iteration expression. If you try to move it into the iteration expression as "it = next_it++", then on the last iteration, when "it" is going to be set equal to "m.cend()", you will attempt to iterate "next_it" past "m.cend()", which is erroneous.
I see all the advantages as disadvantages.
20

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); });
Improve this answer

Comments

12

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:

  • Show declared type (Map::const_iterator) when possible/convenient, over using auto.
  • Use using for template types, to make ancillary types (Map::const_iterator) easier to read/maintain.
Improve this answer

2 Comments

is it possible that this causes a memory leak? It does in my case. But really not sure why.
Not any more than the other answers. I'd look for the memory leak in or involving the destructor(s) for the std::map key and/or value types.
8

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.

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.
Improve this answer

3 Comments

I don't get it. What is the problem with mi.erase(it++); ?
@lvella see op. "If I use map.erase it will invalidate the iterators".
Your new method will not work if after erasing, the map becomes empty. In that case, the iterator will be invalidated. So, soon after erasing, its better to insert if(mi.empty()) break;.
5

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) }
Improve this answer

3 Comments

But after erasing one the rest will be invalid
Nope: stackoverflow.com/questions/263945/…
@Dani: Not in a map. Erasure in map only invalidates iterator to the erased item.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.