Erase Element in Vector While Iterating the Same Vector

Erase element in vector while iterating the same vector

In the line:

it2 = uc.erase(it2);

an element pointed by iterator it2 is removed from the vector, elements are shifted in memory in order to fill that gap which invalidates it2. it2 gets a new value and now points to the first element after the the removed one or the end of the vector (if removed element was the last one). This means that after erasing an element you should not advance it2. An alternative to proposed remove-erase idiom is a simple trick:

for(it2 = uc.begin(); it2 != uc.end();)
{
   ...   
   if(...)
   {
      it2 = uc.erase(it2); 
   }
   else
   {
      ++it2;
   }
   ...
}

You can read more about this here.

Edit:
Regarding your comment, you can use a flag to pass the information whether an element has been erased or not, and you can check it when you get out from the inner loop:

for(it2=uc.begin(); it2 != uc.end();)
{
   bool bErased = false;

   for(it3 = c.begin(); it3 != c.end(); ++it3)
   {
      if(adjacencyMatris[(*it2).id][(*it3).id] == 0 )
      {
         B.id = (*it2).id;
         it2 = uc.erase(it2);
         bErased = true;
         B.color = currentColor;
         c.push_back(B);
         break;
      }
   }

   if(!bErased)
      ++it2;
}

After you've erased an element from uc you need to break from the inner loop. In the next iteration of the outer loop you'll be able to access the next element in the uc through a valid iterator.

C++ how to erase from vector while iterating

erase returns next iterator.

if ((*a) == 2)
{
    delete a;
    it = intList.erase(it);
}

EDIT:
remove() and remove_if() will copy the elements(pointer here) and one will end up with multiple elements pointing to same integer and if you then try to free them, you'll be left with dangling pointers.

Consider the vector has 4 elements which look something like

0x196c160 0x196bec0 0x196c180 0x196bee0 

One might be tempted to use erase-remove idiom

auto temp = remove_if(vec.begin(),vec.end(),[](const auto &i){return *i==2;});

Now it looks like

0x144aec0 0x144b180 0x144b180 0x144aee0

temp would be pointing to 3rd element and a

for(auto it=temp;it!=vec.end();it++)
    delete *it;

Now the second element is a dangling pointer.

EDIT 2:
The above problem could be solved if you delete before the element is copied.Look at @Dietmar's answer.

How to erase or change element while iterating over vector in C++?

Instead of erasing elements in the middle of the vector, you should write the results from the beginning of the vector and eliminate the unused elements in the end of vector.

int finalSize = 0;
for(int i = 0; i < N; i++)
{
        if(result[i] != 0) {
                result[finalSize++] = i;
        }
}
result.resize(finalSize);

Remove elements of a vector inside the loop

You should not increment it in the for loop:

for (vector<Player>::iterator it=allPlayers.begin(); 
                              it!=allPlayers.end(); 
                              /*it++*/) <----------- I commented it.
{

   if(it->getpMoney()<=0) 
      it = allPlayers.erase(it);
  else 
      ++it;
 }

Notice the commented part;it++ is not needed there, as it is getting incremented in the for-body itself.

As for the error "'operator =' function is unavailable in 'Player’", it comes from the usage of erase() which internally uses operator= to move elements in the vector. In order to use erase(), the objects of class Player must be assignable, which means you need to implement operator= for Player class.

Anyway, you should avoid raw loop¹ as much as possible and should prefer to use algorithms instead. In this case, the popular Erase-Remove Idiom can simplify what you're doing.

allPlayers.erase(
    std::remove_if(
        allPlayers.begin(), 
        allPlayers.end(),
        [](Player const & p) { return p.getpMoney() <= 0; }
    ), 
    allPlayers.end()
); 

^{1. It's one of the best talks by Sean Parent that I've ever watched.}

Erase some of a vector's elements in a for-each loop without iterating the whole vector

You should still use std::remove_if, just call std::find beforehand.

auto el = std::find(vec.begin(), vec.end(), whatImLookingFor);
auto p = std::remove_if(vec.begin(), el, isInvalid);

// returns the iterator, not the element itself.
// if the element is not found, el will be vec.end()
return vec.erase(p, el);

This will usually be more efficient than removing one element at a time.

Erasing vector elements while in a range-based loop vs. standard loop

In the first case, for each iteration std::vector::size function is being called. Thus, if you delete all the elements in the first iteration, std::vector::size function which is called before the start of second iteration will return 0. Therefore, second iteration won't happen because the condition i < test.size() is not satisfied.

In the second case, range-based for loop uses iterators instead of std::vector::size function. When you call std::vector::erase you invalidate all the iterators including the end() iterator. Therefore, second case is actually UB (Undefined Behavior) and you should never rely on that.

From the docs:

std::vector::erase

... Invalidates iterators and references at or after the point of the
erase, including the end() iterator.

delete an object both from vector and memory while iterating

The loop is not correct, since

1. you are invalidating the j iterator, and subsequent to that, issuing a delete call on the dereferenced, invalid iterator.

2. The j iterator is not incremented at all in that loop.

The easiest way to issue a delete and erase is a simple std::for_each, followed by a vector::clear().

#include <algorithm>
//...
std::for_each(std::begin(customersList), std::end(customersList), [](Customer *c){delete c;});
customersList.clear();

or even simply:

for (Customer* c : customersList )
    delete c;
customersList.clear();

Nested loop of same vector - Erase–remove idiom

Your job could be easier if you use indices instead, as per below code. I have a slightly modified live demo which shows this works. (I replaced the dist function with something that returns just abs(x-y) for integers).

for(size_t i=0; i<candidates.size();){

    bool deleted = false;

    for (size_t j = 0; j < candidates.size();) {

        if(i==j) {
             ++j;
             continue;
        }

        if(dist.transformed_distance(candidates[i], candidates[j]) <=  dist.transformed_distance(candidates[i], q)
                && dist.transformed_distance(candidates[i], q) <= dist.transformed_distance(candidates[j], q)){

            bool dec_i = false;

            if(i < j) --j;
            else dec_i = true;

            candidates.erase(std::next(candidates.begin(), i));                
            candidates.erase(std::next(candidates.begin(), j));            

            if(dec_i) --i;
            deleted = true;
            break;
        }
        else 
            ++j;
    }
    if(!deleted)
        ++i;
}

Note that you can have an alternative implementation that marks the elements to be deleted in a first pass, and then deletes them. In this case behaviour is different: as elements are not deleted they are still considered for later pair matching. Thus a single element can be paired to more than one other one for deletion, and in the end potentially more elements are removed than with the above. This time the cost is O(n^2) rather than O(n^3). Live demo here:

std::vector<int> deleteIndices;
deleteIndices.reserve(candidates.size());

for(size_t i=0; i<candidates.size(); ++i){

    for (size_t j = 0; j < candidates.size(); ++j) {

        if(i==j) {
             continue;
        }

        if(dist.transformed_distance(candidates[i], candidates[j]) <=  dist.transformed_distance(candidates[i], q)
                && dist.transformed_distance(candidates[i], q) <= dist.transformed_distance(candidates[j], q)){
            deleteIndices.push_back(i);
            deleteIndices.push_back(j);    
        }
    }
}

std::sort(deleteIndices.begin(), deleteIndices.end());
auto unique_end = std::unique(deleteIndices.begin(), deleteIndices.end());

//I'm using this complicated thing as the template param just because I don't know what your element type is
std::vector<std::remove_reference_t<decltype(candidates[0])>> output;
output.reserve(candidates.size() - deleteIndices.size());

auto it = deleteIndices.begin();
auto i = 0;
std::copy_if(candidates.begin(), candidates.end(), std::back_inserter(output), [&it,&i,unique_end](int elem)
    { 
        if(it==unique_end) { 
            ++i; 
            return true; 
        } 
        if(i == *it) { 
            ++i; 
            ++it; 
            return false; 
        } 
        ++i; 
        return true; 
    });

---

Related Topics