Deleting elements from a vector

Question

The following C++ code fills a vector with a number of objects and then removes some of these objects, but it looks like it deletes the wrong ones:

vector<Photon>  photons;

photons = source->emitPhotons();    // fills vector with 300 Photon objects

for (int i=0; i<photons.size();  i++) {
    bool useless = false;

    // process photon, set useless to true for some

    // remove useless photons
    if (useless) {
        photons.erase(photons.begin()+i);
    }
}

Am I doing this correctly? I'm thinking the line photons.erase(photons.begin()+i); might be the problem?

score 7 · Answer 1 · answered Feb 10 '12 at 13:47

7

Definietly the wrong way of doing it, you never adjust i down as you delete..

Work with iterators, and this problem goes away!

e.g.

for(auto it = photons.begin(); it != photons.end();)
{
  if (useless)
    it = photons.erase(it);
  else
    ++it;
}

There are other ways using algorithms (such as remove_if and erase etc.), but above is clearest...

answered Feb 10 '12 at 13:47

Nim

33,299
2
62
101

`warning: 'auto' will change meaning in C++0x; please remove it|`, `error: ISO C++ forbids declaration of 'it' with no type|` – Ben Feb 10 '12 at 13:53
1

@Ben, I was being lazy, `auto` is a keyword in c++11 which is very handy, you need to change `auto` to a type, e.g. in this case: `vector::iterator` – Nim Feb 10 '12 at 13:55
+1 It reminds me [this pull request](https://github.com/TrinityCore/TrinityCore/pull/5015). People often do this error. – LihO Feb 10 '12 at 13:56
Thx, short follow-up question though: How can I add an additional photon using this approach, i.e. in the else case? – Ben Feb 10 '12 at 14:43
@Ben, adding to the vector will invalidate the iterators, and there is no recovery from that (atleast not during a loop - unless you restart from the begining again), an alternative approach may be to put it in a new vector and then once the loop is complete, copy all the items from the new to the `photons` vector. – Nim Feb 10 '12 at 15:24
Thx, but that's not really feasible as, for the new photons, I need to go through the same for loop again. Would using a list solve that problem? – Ben Feb 10 '12 at 15:46
@Ben, you can do this with a list, which allows you to insert at the current position - so that may be a better approach if you do this a lot (remove and insert in the middle - a lot). – Nim Feb 10 '12 at 16:04

Karl von Moor · Answer 2 · 2012-02-10T13:58:16.860

4

the elegant way would be:

std::vector<Photon> photons = source->emitPhotons();
photons.erase(
      std::remove_if(photons.begin(), photons.end(), isUseless),
      photons.end());

and:

bool isUseless(const Photon& photon) { /* whatever */ }

edited Feb 10 '12 at 13:58

answered Feb 10 '12 at 13:51

Karl von Moor

8,484
4
40
52

Nice. Would you also recommend to use a list instead of the vector? And in case of the list, would it allow me to insert an element into the data structure inside the "for loop"? – Ben Feb 10 '12 at 15:33
@Ben If you use the [erase-remove-idiom](http://en.wikipedia.org/wiki/Erase-remove_idiom) as I showed there won't be a for-loop. There's also no way to modify `photons` inside `isUseless()`. – Karl von Moor Feb 10 '12 at 16:02
@Karl von Moor Again, would you recommend to change your erase-remove-idom to using an std::list instead of the std::vector in my case? – Ben Feb 10 '12 at 16:17
1

@Ben I'd recommend std::vector, see [here](http://stackoverflow.com/a/1905424/211359) – Karl von Moor Feb 10 '12 at 16:21

score 1 · Answer 3 · answered Feb 10 '12 at 13:50

The proper version will look like:

for (vector<Photon>::iterator i=photons.begin(); i!=photons.end(); /*note, how the advance of i is made below*/) {
   bool useless = false;

   // process photon, set useless to true for some

   // remove useless photons
   if (useless) {
     i = photons.erase(i);
   } else {
     ++i;
   }
}

Jason · Answer 4 · 2012-02-10T13:54:50.107

Erasing elements in the middle of a vector is very inefficient ... the rest of the elements need to be "shifted" back one slot in order to fill-in the "empty" slot in the vector created by the call to erase. If you need to erase elements in the middle of a list-type data-structure without incurring such a penalty, and you don't need O(1) random access time (i.e., you're just trying to store your elements in a list that you'll copy or use somewhere else later, and you always iterate through the list rather than randomly accessing it), you should look into std::list which uses an underlying linked-list for its implementation, giving it O(1) complexity for modifications to the list like insert/delete.

score 0 · Answer 5 · answered Feb 10 '12 at 13:53

0

You should work with stl::list in this case. Quoting the STL docs:

Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed.

So this would go along the lines of:

std::list<Photon> photons;
photons = source->emitPhotons();
std::list<Photon>::iterator i;
for(i=photons.begin();i!=photons.end();++i)
{
    bool useless=false;
    if(useless)
        photons.erase(i);
}

answered Feb 10 '12 at 13:53

Thomas Wana

837
2
8
19

That crashes my program. I've modified it to take `i++` out of the for loop and put it in the else case instead. And adding `it =` in front of the delete. This works, however it actually feels like it takes a lot longer than the vector approach I used earlier!? – Ben Feb 10 '12 at 15:11

Deleting elements from a vector

5 Answers5

Linked