Solved

Remove an element from a map while looping

Posted on 2011-09-27
15
401 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 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
[Live Webinar] The Cloud Skills Gap

As Cloud technologies come of age, business leaders grapple with the impact it has on their team's skills and the gap associated with the use of a cloud platform.

Join experts from 451 Research and Concerto Cloud Services on July 27th where we will examine fact and fiction.

 
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 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
 
LVL 34

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 29

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 34

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

The Orion Papers

Are you interested in becoming an AWS Certified Solutions Architect?

Discover a new interactive way of training for the exam.

Question has a verified solution.

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

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Have you ever been frustrated by having to click seven times in order to retrieve a small bit of information from the web, always the same seven clicks, scrolling down and down until you reach your target? When you know the benefits of the command l…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
Suggested Courses

626 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