Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Remove an element from a map while looping

Posted on 2011-09-27
15
Medium Priority
?
402 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 3
  • 3
  • +3
15 Comments
 
LVL 86

Accepted Solution

by:
jkr earned 668 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 668 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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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 29

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 29

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 29

Assisted Solution

by:pepr
pepr earned 668 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
 
LVL 35

Assisted Solution

by:sarabande
sarabande earned 332 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 332 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 29

Assisted Solution

by:pepr
pepr earned 668 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 35

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

Get your Disaster Recovery as a Service basics

Disaster Recovery as a Service is one go-to solution that revolutionizes DR planning. Implementing DRaaS could be an efficient process, easily accessible to non-DR experts. Learn about monitoring, testing, executing failovers and failbacks to ensure a "healthy" DR environment.

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
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 …
The goal of this video is to provide viewers with basic examples to understand recursion 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…

688 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