Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 405
  • Last Modified:

Remove an element from a map while looping

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
Wanting2LearnMan
Asked:
Wanting2LearnMan
  • 4
  • 3
  • 3
  • +3
6 Solutions
 
jkrCommented:
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
 
jkrCommented:
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
 
Wanting2LearnManAuthor Commented:
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
Granular recovery for Microsoft Exchange

With Veeam Explorer for Microsoft Exchange you can choose the Exchange Servers and restore points you’re interested in, and Veeam Explorer will present the contents of those mailbox stores for browsing, searching and exporting.

 
jkrCommented:
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
 
peprCommented:
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
 
peprCommented:
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
 
peprCommented:
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
 
sarabandeCommented:
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
 
evilrixSenior Software Engineer (Avast)Commented:
>>  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
 
peprCommented:
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
 
satsumoSoftware DeveloperCommented:
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
 
evilrixSenior Software Engineer (Avast)Commented:
Semantically, it is identical to what I've already posted above.
0
 
satsumoSoftware DeveloperCommented:
@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
 
evilrixSenior Software Engineer (Avast)Commented:
>>  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
 
sarabandeCommented:
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

Prepare for your VMware VCP6-DCV exam.

Josh Coen and Jason Langer have prepared the latest edition of VCP study guide. Both authors have been working in the IT field for more than a decade, and both hold VMware certifications. This 163-page guide covers all 10 of the exam blueprint sections.

  • 4
  • 3
  • 3
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now