Solved

Remove an element from a map while looping

Posted on 2011-09-27
15
391 Views
Last Modified: 2012-05-12
I need to loop through a map and delete the contents of it like so:

MyMap::iterator myMapIterator = m_myMap.begin();
while( m_myMap!= m_myMap.end() )
{
     if( someCondition == true )
     {
         m_myMap.erase(myMapIterator ++);
     }
}

Open in new window


This will result in a crash when the code goes to the while loop again.

How do I do this??


Thanks
0
Comment
Question by:Wanting2LearnMan
  • 4
  • 3
  • 3
  • +3
15 Comments
 
LVL 86

Accepted Solution

by:
jkr earned 167 total points
Comment Utility
Except for a 'std::list', all STL iterators are invalidated when an element is removed from the associated container, thus the crash. To avoid that, set the iterator ro something valid again after 'erase()', e.g.
MyMap::iterator myMapIterator = m_myMap.begin();
while( m_myMap!= m_myMap.end() )
{
     if( someCondition == true )
     {
         m_myMap.erase(myMapIterator);

         myMapIterator = m_myMap.begin();
     }
}

Open in new window

0
 
LVL 86

Assisted Solution

by:jkr
jkr earned 167 total points
Comment Utility
Or, to keep up some better performance:
MyMap::iterator myMapIterator = m_myMap.begin();

MyMapKeyType prev_key;
while( m_myMap!= m_myMap.end() )
{
     if( someCondition == true )
     {
         m_myMap.erase(myMapIterator);

         myMapIterator = m_myMap.find(prev_key);
     }

     prev_key = myMapIterator->first;
     myMapIterator++; // was missing in the ürev. snippet also, sorry
}

Open in new window

0
 

Author Comment

by:Wanting2LearnMan
Comment Utility
Excellent, thanks very much.

Can I ask how I would do this using a for loop? instead of a while??
(Just so I know for again :) )

Thanks
0
 
LVL 86

Expert Comment

by:jkr
Comment Utility
Are 'for' loop would be quite similar, e.g.
MyMapKeyType prev_key;
for ( MyMap::iterator myMapIterator = m_myMap.begin();
m_myMap!= m_myMap.end(); ++myMapIterator )
{
     if( someCondition == true )
     {
         m_myMap.erase(myMapIterator);

         myMapIterator = m_myMap.find(prev_key);
     }

     prev_key = myMapIterator->first;
    
}

Open in new window

0
 
LVL 28

Expert Comment

by:pepr
Comment Utility
The following was not in the older standard, but I believe it is in the C++11. It was earlier supported also by the Microsoft compiler: the map::erase(it) returns the iterator value to the element that "follows" the erased one.   I did not try to compile the code.  It could be something like:

MyMap::iterator it = m_myMap.begin();
while( it != m_myMap.end() )
{
    if( someCondition )
        it = m_myMap.erase(it);
    else
        ++it;
}

Open in new window

0
 
LVL 28

Expert Comment

by:pepr
Comment Utility
In the later case (when map::erase returns the iterator instead of void), you can use also the for loop:

for (MyMap::iterator it = m_myMap.begin(); ; it = (someCondition) ? m_myMap.erase(it) : ++it);

Open in new window


In C++11 should even be possible:

for (auto it = m_myMap.begin(); ; it = (someCondition) ? m_myMap.erase(it) : ++it);

Open in new window

0
 
LVL 28

Assisted Solution

by:pepr
pepr earned 167 total points
Comment Utility
Here is the tested example -- Microsoft Visual C++ 9.0 (2008):

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
    typedef map<string, int> mtype;
    
    mtype m;
    
    m["key0"] = 0;
    m["key1"] = 1;
    m["key2"] = 2;
    m["key3"] = 3;
    m["key4"] = 4;
    
    mtype::iterator it;
    
    for (it = m.begin(); it != m.end(); ++it)
        cout << it->first << " --> " << it->second << '\n';
    cout << "-----------------------------------------\n";

    it = m.begin();
    while (it != m.end())
    {
        if (it->second % 2 == 0)  
            it = m.erase(it);    // erase the items with even values
        else
            ++it;
    }
    
    for (it = m.begin(); it != m.end(); ++it)
        cout << it->first << " --> " << it->second << '\n';
        
    cout << "-----------------------------------------" << endl;
            
    return 0;
}

Open in new window


The command line compilation stored in the batch file:

compile.bat
call "%VS90COMNTOOLS%vsvars32.bat"
cl /EHsc main.cpp

Open in new window


It prints on my console:

c:\tmp\___C++\Wanting2LearnMan\Q_27343477>main
key0 --> 0
key1 --> 1
key2 --> 2
key3 --> 3
key4 --> 4
-----------------------------------------
key1 --> 1
key3 --> 3
-----------------------------------------

Open in new window

0
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 83 total points
Comment Utility
to add to pepr's solution:

the iterator returned by std::map::erase(iterator) always is a valid iterator pointing beyond the currently removed entry. when erasing the last entry the return value equals to end() iterator of the map.

that behavior is c++ standard and even supported by the vc6 stl which was released before c++ standard.

Sara
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 83 total points
Comment Utility
>>  all STL iterators are invalidated when an element is removed
That's not actually true. In the case of map, the only iterator invalidated is the one removed.

There is a much simpler (and efficient) way of doing this whilst keeping within the C++03 standard (erase does not return an iterator... this was added in C++11 but it's still not a widely adopted standard as of yet as it was only approved in August 2011).
#include <map>
#include <iostream>

int main()
{
   // set up some test data
   std::map<int, int> m;
   m[0] = 0;
   m[1] = 1;
   m[2] = 0;
   m[3] = 1;
   m[4] = 0;;

   // enumerate the map and remove items that have a value of 1
   std::map<int, int>::iterator itr = m.begin();
   while(itr != m.end())
   {
      // take a copy of 'this' iterator and then move itr on to the next (this will NOT get invalidated)
      std::map<int, int>::iterator tmp = itr++;
      if(tmp->second == 1)
      {
         // remove 'this' item, itr is still going to be either a valid iterator or end
         m.erase(tmp);
      }
   }

   // display the result
   for(itr = m.begin() ; itr != m.end() ; ++itr)
   {
      std::cout << itr->first << ":" << itr->second << std::endl;
   }
}

Open in new window

0
 
LVL 28

Assisted Solution

by:pepr
pepr earned 167 total points
Comment Utility
I agree with evilrix.  I was about to write that the C++98 (the ISO/IEC 14882:1998, also known as the first edition) actually defined the map::erase(it) as returning void. (The C++03 is the ISO/IEC 14882:2003, known also as the second edition.)

I agree that it may be wise to keep closely to the standard.  On the other hand, you cannot make a mistake when the code is to be compiled only by the Microsoft compiler.  If neccessary, it is easy to fix that.

I suggest not to discuss about what approach is better as it was already answered by the C++11.
0
 
LVL 12

Expert Comment

by:satsumo
Comment Utility
I'm only answering this for the sake amusement.  This might even be wrong given that I don't use iterators very often.  If it is wrong will somebody explain why it doesn't work?

MyMap::iterator myMapIterator = m_myMap.begin ();

while (m_myMap! = m_myMap.end())
{
     MyMap::iterator myNextIterator = myMapIterator;
     myNextIterator++;
     
     if (someCondition == true)
     {
          m_myMap.erase (myMapIterator);
     }

     myMapIterator = myNextIterator;
}

Open in new window

0
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
Semantically, it is identical to what I've already posted above.
0
 
LVL 12

Expert Comment

by:satsumo
Comment Utility
@evilrix, I guess it is the same.  As I say I don't use iterators (or STL), this was based on what I do on C/C++ when deleting items from a linked list.  I only answered because its something I do often, not trying to steal anybody's glory (weary sigh).
0
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
>>  not trying to steal anybody's glory
I think you miss my point. You asked, "If it is wrong will somebody explain why it doesn't work?"

And by implication, since it's semantically the same as what I wrote it must be correct (assuming I am, which I know I am) :)

>>  this was based on what I do on C/C++ when deleting items from a linked list
You can do that but list::erase does return you an iterator, which can be used to make life just slightly easier.
0
 
LVL 32

Expert Comment

by:sarabande
Comment Utility
the 'while (m_myMap! = m_myMap.end())' is not correct (and so probably syntactically and semantically different to the right code of evilrix) cause the left term 'm_myMap' of the comparision is not the iterator but the map. also the '!' and '=' seem to be separated by a space what will not compile.

Sara
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now