C++ how to erase from vector while iterating

Question

std::vector<int *>intList;
int *a = new int;
*a = 3;
int *b = new int;
*b = 2;
int *c = new int;
*c = 1;

intList.push_back(a);
intList.push_back(b);
intList.push_back(c);

std::vector<int *>::iterator it;

for (it = intList.begin(); it != intList.end();)
{
    int *a = (int*)*it;

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

This code crashes at the start of the for loop when something is erased from the vector. I do not understand why. I am using Visual Studio 2015 if that helps

There is a common pattern for this, called the [`erase`-`remove` idiom](https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom). — BoBTFish, Aug 16 '18 at 06:08
@BoBTFish Might be a bit over-complicated in this case, where a call to `delete` is needed. It think it would require two passes. — juanchopanza, Aug 16 '18 at 06:10
Why not let `intList` hold plain `int`s rather than pointers and then do `intList.erase(std::remove_if(intList.begin(), intList.end(), [](const auto &elem) { return elem == 2; }), intList.end());` or `intList.erase(std::remove(intList.begin(), intList.end(), 2), intList.end());` ? — Jesper Juhl, Aug 16 '18 at 06:12
Possible duplicate of [Erasing elements from a vector](https://stackoverflow.com/questions/347441/erasing-elements-from-a-vector) — hellow, Aug 16 '18 at 06:40

Gaurav Sehgal · Accepted Answer · 2018-08-16T06:47:15.900

12

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.

edited Aug 16 '18 at 06:47

answered Aug 16 '18 at 06:08

Gaurav Sehgal

7,422
2
18
34

The problem is in calling `delete` after `remove_if`. `remove_if` just copies the eligible elements(which should not be deleted) to front leaving the same value from where they are copied. – Gaurav Sehgal Aug 16 '18 at 06:55
I thought "removed" elements were moved to the back of the vector, but I was able to reproduce what you said, so this is clearly not the case – Remy Lebeau Aug 16 '18 at 09:18

score 4 · Answer 2 · answered Aug 16 '18 at 06:37

Better to use std::vector<std::unique_ptr<int>> (or even std::vector<int> if you don't need pointer).

then just use erase-remove idiom:

std::vector<int> intList{3, 2, 1};

intList.erase(std::remove(intList.begin(), intList.end(), 2), intList.end());

or

std::vector<std::unique_ptr<int>> intList;
intList.puch_back(std::make_unique<int>(3));
intList.puch_back(std::make_unique<int>(2));
intList.puch_back(std::make_unique<int>(1));

intList.erase(std::remove_if(intList.begin(), intList.end(),
                             [](const auto& p){ return *p == 2; }),
              intList.end());

If you really need raw owning pointer, you may use a variant using partition:

std::vector<int*> intList{ new int {3}, new int {2}, new int{1} };

auto it = std::partition(intList.begin(), intList.end(),
                         [](const auto& p){ return *p != 2; });

std::foreach (it, intList.end(), [](int* p) { delete p; });
intList.erase(it, intList.end());

Finally, if you really need to do it manually, you have to fix your erase line to:

it = intList.erase(it);

to have:

std::vector<int*> intList{ new int {3}, new int {2}, new int{1} };

for (auto it = intList.begin(); it != intList.end(); /*Empty*/) {
    int *p = *it;

    if (*p == 2) {
        delete p;
        it = intList.erase(it);
    } else {
        ++it;
    }
}

score 2 · Answer 3 · answered Aug 16 '18 at 06:10

That code is causing iterator invalidation.

You're deleting a then expecting your iterator (which is just a pointer) to know what just happened.

If you have to iterate through the whole vector then consider a temporary vector of what to keep/throwaway and use that.

Or better yet just use find http://www.cplusplus.com/reference/algorithm/find/

Raxvan · Answer 4 · 2018-08-16T07:14:18.377

2

If you take a look at documentation the erase function returns next iterator. In your case using it = intList.erase(it) is the solution. After c++11 all erase functions from other containers follow the same idea.

edited Aug 16 '18 at 07:14

answered Aug 16 '18 at 06:10

Raxvan

6,257
2
25
46

"*All erase functions from other containers follow the same idea*" - not always. For instance, `std::map.erase()` and `std::set::erase()` didn't return an `iterator` to the next element until C++11. In those cases, you can use `erase(it++)` instead. – Remy Lebeau Aug 16 '18 at 06:59
@Remy Lebeau true, i changed the answer to include that. – Raxvan Aug 16 '18 at 07:15

score 2 · Answer 5 · answered Aug 16 '18 at 06:35

2

The simple anser is: you don’t! Instead you use a two stage approach: first get rid of the elements, then resize the container. The use of raw pointers slightly complicates things but it is still doable:

auto end = std::remove_if(intList.begin(), intList.end(),
    [](int *ptr){ return *ptr == 2 && (delete ptr, true); });
intList.erase(end, endList.end());

Trying to erase individual elements while iterating over std::vector has non-linear worst case complexity.

answered Aug 16 '18 at 06:35

Dietmar Kühl

150,225
13
225
380

I prefer to use `std::partition` with raw owning pointers in that case (with negated predicate). – Jarod42 Aug 16 '18 at 06:40
@Jarod42: In principle: maybe :-) I did consider using `partition()` but there are two problems: it is more involved than `remove_if()` (although still linear) and it doesn’t make a guarantee on the order of elements. `stable_partition()` would address the second problem at the cost of further increasing the first one. My preference is never to have non-owning raw pointers: I can’t cope with manual clean-up - it is too conplex for me to handle correctly. – Dietmar Kühl Aug 16 '18 at 10:08

C++ how to erase from vector while iterating

5 Answers5

Linked

Related