CODEWITHSUNDEEP
c++stl
ultraman
ultraman

Reputation:

Erase/Remove contents from the map (or any other STL container) while iterating it

Allegedly you cannot just erase/remove an element in a container while iterating as iterator becomes invalid. What are the (safe) ways to remove the elements that meet a certain condition? please only stl, no boost or tr1.

EDIT Is there a more elegant way if I want to erase a number of elements that meet a certain criteria, perhaps with using functor and for_each or erase algorithm ?

Upvotes: 29

Views: 24663

Answers (9)

TimW
TimW

Reputation: 8447

template <class Container, class Predicate>
void eraseIf( Container& container, Predicate predicate  ) {
    container.erase( remove_if( container.begin(), container.end(), predicate ), container.end() );
}   

// pre-c++11 version
template<class K, class V, class Predicate> 
void eraseIf( std::map<K,V>& container, Predicate predicate) {
    typename std::map<K,V>::iterator iter = container.begin();
    while(iter!=container.end()) { 
        iterator current = iter++;
        if(predicate(*current))
            container.erase(current);
    }
}

// c++11 version
template<class K, class V, class Predicate> 
void eraseIf( std::map<K,V>& container, Predicate predicate) {
    auto iter = container.begin();
    while(iter!=container.end()) {
        if(predicate(*iter))
            iter = container.erase(iter);
        else
            ++iter;
    }
}

Upvotes: 1

Steephen
Steephen

Reputation: 15854

1.For std::vector<> :

std::vector <int> vec;
vec.erase(std::remove(vec.begin(),vec.end(), elem_to_remove), vec.end());

2.For std::map<> always use std::map::erase()

std::map<int,std::string> myMap;
myMap.emplace(std::make_pair(1, "Hello"));
myMap.emplace(std::make_pair(2, "Hi"));
myMap.emplace(std::make_pair(3, "How"));
myMap.erase( 1);//Erase with key
myMap.erase(myMap.begin(), ++myMap.begin() );//Erase with range
for( auto &ele: myMap)
{
    if(ele.first ==1)
    {
        myMap.erase(ele.first);//erase by key 
        break; //You can't use ele again properly 
               //wthin this iteration, so break.
    }
}
  1. For std::list use std::list::erase()

Upvotes: 2

Chad Webb
Chad Webb

Reputation: 11

Use the fact that the post-decrement operator returns a copy of the iterator before it decrements. Since the decremented iterator is still valid after erasing the current element, the for loop continues to operate as intended.

#include <list>
std::list<int> myList;
for(int i = 0; i < 10; ++i )
{
   myList.push_back(i);
}

int cnt = 0;
for(std::list<int>::iterator iter = myList.begin(); iter != myList.end(); ++iter)
{
   if( cnt == 5 )
   {
      myList.erase(iter--);
   }
   ++cnt;
}

Edit: Doesn't work if you attempt to erase the first element in the list....

Upvotes: 1

idbrii
idbrii

Reputation: 11966

Viktor's solution has the upside of being able to do something with the element before removing. (I wasn't able to do this with remove_if or remove_copy_if.) But I prefer to use std::find_if so I never have to increment the iterator myself:

typedef vector<int> int_vector;
int_vector v;

int_vector::iterator itr = v.begin();
for(;;)
{
    itr = std::find_if(itr, v.end(), Predicate(4));
    if (itr == v.end())
    {
        break;
    }

    // do stuff with *itr here

    itr = v.erase(itr);  // grab a new, valid iterator
}

Where Predicate could be bind1st( equal_to<int>(), 4 ) or something like this:

struct Predicate : public unary_function<int, bool>
{
    int mExpected;
    Predicate(int desired) : mExpected(desired) {}
    bool operator() (int input)
    {
        return ( input == mExpected );
    }
};

Upvotes: 3

Pascal
Pascal

Reputation: 126

markh44 is the most STL-ish response. Note, however, that in general, iterators are invalidated by modifying the container, but set and map are exceptions. There, you can remove items and still go on using the iterators, except if you delete the very item your iterator is referencing.

Upvotes: 1

Kirill V. Lyadvinsky
Kirill V. Lyadvinsky

Reputation: 99725

I prefer version with while:

typedef std::list<some_class_t> list_t;
void f( void ) {
  // Remove items from list
  list_t::iterator it = sample_list.begin();
  while ( it != sample_list.end() ) {
    if ( it->condition == true ) {
      it = sample_list.erase( it );
    } else ++it;    
  }
}

With while there is no danger to increment it twice as it could be in for loop.

Upvotes: 2

markh44
markh44

Reputation: 6070

bool IsOdd( int i )
{
    return (i&1)!=0;
}

int a[] = {1,2,3,4,5};
vector<int> v( a, a + 5 );
v.erase( remove_if( v.begin(), v.end(), bind1st( equal_to<int>(), 4 ) ), v.end() );
// v contains {1,2,3,5}
v.erase( remove_if( v.begin(), v.end(), IsOdd ), v.end() );
// v contains {2}

Upvotes: 9

Aaron Saarela
Aaron Saarela

Reputation: 4036

You can as long as you don't invalidate your iterator after you've erased it:

MyContainer::iterator it = myContainer.begin();
while(it != myContainer.end())
{
    if (*it == matchingValue)
    {
       myContainer.erase(it++);
    }
    else
    {
        ++it;
    }
}

Upvotes: 35

Viktor Sehr
Viktor Sehr

Reputation: 13139

Example with std::vector

#include <vector>

using namespace std;

int main()
{

   typedef vector <int> int_vector;

   int_vector v(10);

   // Fill as: 0,1,2,0,1,2 etc
   for (size_t i = 0; i < v.size(); ++i){
      v[i] = i % 3;
   }

   // Remove every element where value == 1    
   for (int_vector::iterator it = v.begin(); it != v.end(); /* BLANK */){
      if (*it == 1){
         it = v.erase(it);
      } else {
         ++it;
      }
   }

}

Upvotes: 12

Related Questions