CODEWITHSUNDEEP
c++vector
Ben
Ben

Reputation: 16641

Deleting elements from a vector

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?

Upvotes: 1

Views: 821

Answers (5)

Karl von Moor
Karl von Moor

Reputation: 8614

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 */ }

Upvotes: 4

Jason
Jason

Reputation: 32490

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.

Upvotes: 0

Thomas Wana
Thomas Wana

Reputation: 847

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);
}

Upvotes: 0

Arty
Arty

Reputation: 763

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;
   }
}

Upvotes: 1

Nim
Nim

Reputation: 33655

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...

Upvotes: 7

Related Questions