Jump to content
  • Advertisement
Sign in to follow this  
Entheo

Question about Sequence.erase()

This topic is 4158 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey fellas. I ran into a problem which seems a little screwy to me. Basically I have a vector of objects and I wanted to delete an element.
std::vector<Tac>::iterator start(vTac.begin());
for (; start != vTac.end(); ++start)
   if (start->mouse_clicked_tac())
      vector.erase(start);


Now this will cause a seg fault because Tac has member variables which are pointers to memory on the freestore and for some reason erase isn't cleaning them up properly. If, however, I do it like this:
      std::insert_iterator<std::vector<Tac> > ii(vTacs, vTacs.begin()); 
      std::vector<Tac> v2;
      std::remove_copy_if(vTacs.begin(), vTacs.end(), 
	                  std::back_inserter(v2),
		          std::bind2nd(hole_equals(), Tac::hole_ID)
                         );
      vTacs.clear();
      std::copy(v2.begin(), v2.end(), ii);


It does the job as it is supposed to. Can someone explain why this may be without me having to provide the definitions of Tac? If not I can certainly provide those...

Share this post


Link to post
Share on other sites
Advertisement
erase() returns an iterator pointing at the next valid element in the sequence after the erase. So your look should look like:

std::vector<Tac>::iterator start(vTac.begin());
while(start != vTac.end())
{
if (start->mouse_clicked_tac())
start = vector.erase(start);
else
++start;
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Entheo
Hey fellas. I ran into a problem which seems a little screwy to me.

Basically I have a vector of objects and I wanted to delete an element.

*** Source Snippet Removed ***

Now this will cause a seg fault because Tac has member variables which are pointers to memory on the freestore and for some reason erase isn't cleaning them up properly.


That's not the problem ('erase' will call the destructor of your object; so all that you need to do is implement the destructor properly... if you have a segfault, it's because your Tac class itself is broken; and since the other version works...).

The problem is that you modify a sequence while you are manually iterating over it. You have to be very careful when you do this.

Quote:

If, however, I do it like this:
*** Source Snippet Removed ***

It does the job as it is supposed to. Can someone explain why this may be without me having to provide the definitions of Tac? If not I can certainly provide those...


Again, if your Tac class doesn't have any serious problems, you don't need to remove_copy_if and then copy back into the container. (BTW, even then, you shouldn't construct the insert_iterator at the beginning, do your stuff, clear the vector and *then* use the insert_iterator. Instead, you would construct the insert_iterator *after* clearing the vector. A general application of the "declare and initialize near first use" guideline.) Just use remove_if. The remove_if algorithm correctly implements "being careful" for iterating over the container while removing items, and for a std::vector, is also faster than calling .erase() for every element that needs to be erased.

When you .erase() an element, everything after it in the vector has to be "shifted" down, because a vector can't have any "holes" in it. What remove_if does is to keep two iterators: a "read head" and a "write head", both initialized at the beginning of the provided range. The read head iterates over the whole range; each element that should be *kept* gets written to the current write-head position (and the write head is advanced after that). When an element should be *discarded*, the write-head is untouched and unused. Net result, all the *kept* elements are copied in order at the beginning of the container, the write-head is positioned at the "end of kept elements" range, and the rest of the elements are what they were before (technically, unspecified). Then, you can use the *range* version of .erase() to clean up all the "garbage" elements in one go.

It looks like this:


// The remove_if function returns the final value of the "write head", so we
// can pass that to the .erase() member function of the container. We erase the
// range from the write head to the container end, i.e. all the garbage.
vTacs.erase(std::remove_if(vTacs.begin(), vTacs.end(),
std::bind2nd(hole_equals(), Tac::hole_ID)),
vTacs.end());

// Alternately, when using the member function:
vTacs.erase(std::remove_if(vTacs.begin(), vTacs.end(),
std::mem_fun_ref(&Tac::mouse_clicked_tac)),
vTacs.end());

Share this post


Link to post
Share on other sites
Thanks for the replies. First: Evil_Steve, you're right that it would invalidate the iterator start after the erase call, but that was merely a flaw in the example. My actual code had a return statement directly after. So once the call to erase happened the iterator would never be used again.

To Zahlman, I have a question for you... You are certain that it is my Tac destructor that isn't cleaning up properly but then this statement left an air of ambiguity for me: "it's because your Tac class itself is broken; and since the other version works...)"

Does that mean the other version never calls the destructor? I'm pretty sure both do don't they?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!