Removing item from vector while iterating? [duplicate]

Question

I have a vector that holds items that are either active or inactive. I want the size of this vector to stay small for performance issues, so I want items that have been marked inactive to be erased from the vector. I tried doing this while iterating but I am getting the error "vector iterators incompatible".

vector<Orb>::iterator i = orbsList.begin();

    while(i != orbsList.end()) {
        bool isActive = (*i).active;

        if(!isActive) {
            orbsList.erase(i++);
        }
        else {
            // do something with *i
            ++i;
        }
    }

See this related question: stackoverflow.com/questions/347441/… — Naveen
– Naveen, Commented Jan 17, 2011 at 12:30
this sometimes invelidates iterator but this one works safe when digit is a vector and arr is an array for (auto a = digit.begin(); a != digit.end();) { for (auto b= arr.begin(); b != arr.end();) { if ((*a) == (*b)) { a = digit.erase(a); if(!(a==digit.begin())) --a; } ++b; } ++a; } — cen dum
– cen dum, Commented Nov 15 at 14:33

Robert F. · Accepted Answer · 2016-10-29 15:55:19Z

80

The most readable way I've done this in the past is to use std::vector::erase combined with std::remove_if. In the example below, I use this combination to remove any number less than 10 from a vector.

(For non-c++0x, you can just replace the lambda below with your own predicate:)

// a list of ints
int myInts[] = {1, 7, 8, 4, 5, 10, 15, 22, 50. 29};
std::vector v(myInts, myInts + sizeof(myInts) / sizeof(int));

// get rid of anything < 10
v.erase(std::remove_if(v.begin(), v.end(), 
                       [](int i) { return i < 10; }), v.end());

edited Oct 29, 2016 at 15:55

Robert F.

4653 silver badges14 bronze badges

answered Jan 17, 2011 at 13:20

Moo-Juice

38.9k11 gold badges83 silver badges132 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Josh Sanders Over a year ago

While elegant in the simple case, I'm dubious of its effectiveness in the real world. This wouldn't even work at all with a dynamic size vector.

jhasse Over a year ago

"This wouldn't even work at all with a dynamic size vector." Why not?

daparic Over a year ago

While the std::remove_if lambda looks nice, but if I only want to delete exactly one element that matches the condition, it still goes through each element to the end. Therefore, I prefer manual iteration so I can break from the loop any time.

DanSkeel · Accepted Answer · 2015-03-12 21:57:47Z

78

I agree with wilx's answer. Here is an implementation:

// curFiles is: vector < string > curFiles;

vector< string >::iterator it = curFiles.begin();

while(it != curFiles.end()) {

    if(aConditionIsMet) {

        it = curFiles.erase(it);
    }
    else ++it;
}

edited Mar 12, 2015 at 21:57

DanSkeel

4,03539 silver badges56 bronze badges

answered Oct 27, 2012 at 17:18

Vassilis

2,9981 gold badge31 silver badges43 bronze badges

Comments

wilx · Accepted Answer · 2011-01-17 12:31:48Z

20

You can do that but you will have to reshuffle your while() a bit, I think. The erase() function returns an iterator to the element next after the erased one: iterator erase(iterator position);. Quoting from the standard from 23.1.1/7:

The iterator returned from a.erase(q) points to the element immediately following q prior to the element being erased. If no such element exists, a.end() is returned.

Though maybe you should be using the Erase-remove idiom instead.

answered Jan 17, 2011 at 12:31

wilx

18.3k7 gold badges66 silver badges123 bronze badges

2 Comments

Naveen Over a year ago

Also, to downsize the vector(as it seems to what the OP wants to do) the swap trick can be used. Details here:stackoverflow.com/questions/253157/how-to-downsize-stdvector

jakebman Over a year ago

It might be enough to say i=orbsList.erase(i) instead of orbsList.erase(i++)

Pierre · Accepted Answer · 2019-04-04 19:56:45Z

11

erase returns a pointer to the next iterator value (same as Vassilis):

vector <cMyClass>::iterator mit
for(mit = myVec.begin(); mit != myVec.end(); )
{   if(condition)
        mit = myVec.erase(mit);
    else
        mit++;
}

answered Apr 4, 2019 at 19:56

Pierre

4,5042 gold badges38 silver badges43 bronze badges

1 Comment

Eric Over a year ago

access the value at the iterator position using *mit

Gelldur · Accepted Answer · 2013-07-30 20:21:21Z

4

If someone need working on indexes

vector<int> vector;
for(int i=0;i<10;++i)vector.push_back(i);

int size = vector.size();
for (int i = 0; i < size; ++i)
{
    assert(i > -1 && i < (int)vector.size());
    if(vector[i] % 3 == 0)
    {
        printf("Removing %d, %d\n",vector[i],i);
        vector.erase(vector.begin() + i);
    }

    if (size != (int)vector.size())
    {
        --i;
        size = vector.size();
        printf("Go back %d\n",size);
    }
}

answered Jul 30, 2013 at 20:21

Gelldur

11.6k7 gold badges60 silver badges71 bronze badges

3 Comments

user1122069 Over a year ago

Why not just size-- i-- next to erase?

Gelldur Over a year ago

@user1122069 my good practices forbids such things, a lot of people do not understand difference between --i nad i--

Everyone Dec 26, 2024 at 10:21

The size variable is unnecessary altogether, compilers won't optimize when the vector is non-const and especially when you are mutating the vector in the loop body. So vector.size() will be called every iteration and you can just decrement i in the same scope you are erasing the item, and eliminate the second scope altogether. stackoverflow.com/a/55823447/6871623

Maxim Egorushkin · Accepted Answer · 2011-01-17 12:41:52Z

1

As they said, vector's iterators get invalidated on vector::erase() no matter which form of iterator increment you use. Use an integer index instead.

answered Jan 17, 2011 at 12:41

Maxim Egorushkin

138k19 gold badges201 silver badges293 bronze badges

3 Comments

harper Over a year ago

Using the return value of erase you get a valid iterator back. So it's only necessary to assign the returned value to the iterator -- no performance issue here.

Oliver Charlesworth Over a year ago

@harper: Actually, there's a big performance issue here; erasing an item from the middle of a vector requires all the rest of them to be moved down, which involves O(N) constructor and destructor calls each time.

harper Over a year ago

And the use of an index has what befinit? How is the erasing performance increased? I just annotated the statement "iterators get invalidated .. no matter which form"...

Raedwald · Accepted Answer · 2011-01-17 13:02:50Z

1

You might want to consider using a std::list instead of a std::vector for your data structure. It is safer (less bug prone) to use when combining erasure with iteration.

answered Jan 17, 2011 at 13:02

Raedwald

49.2k49 gold badges162 silver badges250 bronze badges

Comments

Oliver Charlesworth · Accepted Answer · 2011-01-17 12:43:48Z

0

Removing items from the middle of a vector will invalidate all iterators to that vector, so you cannot do this (update: without resorting to Wilx's suggestion).

Also, if you're worried about performance, erasing items from the middle of a vector is a bad idea anyway. Perhaps you want to use an std::list?

edited Jan 17, 2011 at 12:43

answered Jan 17, 2011 at 12:30

Oliver Charlesworth

274k34 gold badges591 silver badges687 bronze badges

1 Comment

EFreak Over a year ago

I know its a little late but you might wanna read this. Its contrary to what most people would expect but it comes from the creator of C++ bulldozer00.com/2012/02/09/vectors-and-lists

Collectives™ on Stack Overflow

Removing item from vector while iterating? [duplicate]

8 Answers 8

3 Comments

Comments

2 Comments

1 Comment

3 Comments

3 Comments

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

3 Comments

Comments

2 Comments

1 Comment

3 Comments

3 Comments

Comments

1 Comment

Linked

Related