Solved

Remove an element from a map while looping

Posted on 2011-09-27
15
396 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
ID: 36709735
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
ID: 36709754
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
ID: 36709839
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
ID: 36709884
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
ID: 36709933
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
ID: 36709996
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
ID: 36710610
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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 33

Assisted Solution

by:sarabande
sarabande earned 83 total points
ID: 36710732
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
ID: 36713055
>>  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
ID: 36713409
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
ID: 36893684
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
ID: 36894012
Semantically, it is identical to what I've already posted above.
0
 
LVL 12

Expert Comment

by:satsumo
ID: 36894828
@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
ID: 36895008
>>  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 33

Expert Comment

by:sarabande
ID: 36910889
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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

862 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

29 Experts available now in Live!

Get 1:1 Help Now