Sign in to follow this  
wild_pointer

have I misunderstood remove_if behavior?

Recommended Posts

class Foo {
  bool foo_;
public:
  Foo(bool foo) : foo_(foo) {}

  bool Bar() { return foo_; }
};

int main() {
  std::vector<Foo*> foos;
  foos.push_back(new Foo(false));
  foos.push_back(new Foo(true));
  foos.push_back(new Foo(true));
  foos.push_back(new Foo(true));

  for(std::vector<Foo*>::iterator i = foos.begin(); i != foos.end(); ++ i)
  {
    std::cout << "Bar() = " << (*i)->Bar() ? "true" : "false" << std::endl;
  }

  std::cout << std::endl;

  struct IsBar {
    bool operator() (Foo* foo) {
      return foo->Bar();
    }
  };

  std::remove_if(foos.begin(), foos.end(), IsBar());

  for(vector<Foo*>::iterator i = foos.begin(); i != foos.end(); ++ i)
  {
    std::cout << "Bar() = " << (*i)->Bar() ? "true" : "false" << std::endl;
  }
}


Output is:
false
true
true
true

true
true
true
true
Shouldn't the second block of output end with false? remove_if moves elements that satisfy the predicate to the end of the range, correct? I'm really confused by this :(

Share this post


Link to post
Share on other sites
Nope! [smile] See here (note 1). The basic problem is, remove_if operates on iterators, not containers. Iterators have no way to actually erase their elements from a container, so the actual erasure is left to the user. remove_if just makes the erasure part easy.

Share this post


Link to post
Share on other sites
remove_if can be kinda confusing

Quote:
Remove_if removes from the range [first, last) every element x such that pred(x) is true. That is, remove_if returns an iterator new_last such that the range [first, new_last) contains no elements for which pred is true. [1] The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified.


Or to put it another way, remove_if returns an iterator, and the value of elements after the iterator could be anything.

edit: beat by Sneftel

Share this post


Link to post
Share on other sites
A standard useage pattern of remove_if:


std::vector<whatever> foos;
foos.erase(
std::remove_if(foos.begin(), foos.end(), IsBar()),
foos.end()
);



Alternatively:

template<typename Container, typename Pred>
Container::iterator remove_stuff( Container& container, Pred pred )
{
return
container.erase(
std::remove_if(container.begin(), container.end(), pred ),
container.end()
);
}



Now, simple replace:
  std::remove_if(foos.begin(), foos.end(), IsBar());

with
  remove_stuff(foos, IsBar());

Share this post


Link to post
Share on other sites
Quote:
Original post by Will F
The iterators in the range [new_last, last) are all still dereferenceable, but the elements that they point to are unspecified.


That's the bit I missed. I always thought it just shuffled around the elements in the container.

But then it would just be partition :D I guess I'm looking for partition.

[Edited by - wild_pointer on October 1, 2006 10:40:16 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this