Question about STL erase function

[Piotr]

In Effective STL item 9 "Choose carefully among erasing options", it
has this example:

bool badValue(int x); // returns whether x is 'bad'
c.erase ( remove_if(c.begin(), c.end(), badValue), c.end()); // this
is the best way to get rid of objects where badValue returns true when
c is a vector, string, or dequeue

c.remove_if(badValue); // this is the best way to get rid of objects
where badValue returns true when c is a list

My question is "For the first case, why we need to call c.erase() again
and pass in the return value of remove_if()?" Doesn't the call to
remove_if() remove the item from the container (in this case a vector)?
why we need to call erase() again?

Thank you.

 

[Thomas Tutone]

In Effective STL item 9 "Choose carefully among erasing options", it
has this example:

bool badValue(int x); // returns whether x is 'bad'
c.erase ( remove_if(c.begin(), c.end(), badValue), c.end()); // this
is the best way to get rid of objects where badValue returns true when
c is a vector, string, or dequeue

c.remove_if(badValue); // this is the best way to get rid of objects
where badValue returns true when c is a list

My question is "For the first case, why we need to call c.erase() again
and pass in the return value of remove_if()?" Doesn't the call to
remove_if() remove the item from the container (in this case a vector)?
why we need to call erase() again?

I believe the book you are reading has the answer to your question.
std::remove_if does not change the size of the container - it couldn't,
since you are only passing it a range specified by two iterators.
Instead, it returns a new iterator indicating the new end of the range.

See here for an explanation:

http://www.sgi.com/tech/stl/remove_if.html

Best regards,

Tom

 

[Heinz Ozwirk]

In Effective STL item 9 "Choose carefully among erasing options", it
has this example:

bool badValue(int x); // returns whether x is 'bad'
c.erase ( remove_if(c.begin(), c.end(), badValue), c.end()); // this
is the best way to get rid of objects where badValue returns true when
c is a vector, string, or dequeue

c.remove_if(badValue); // this is the best way to get rid of objects
where badValue returns true when c is a list

My question is "For the first case, why we need to call c.erase() again
and pass in the return value of remove_if()?" Doesn't the call to
remove_if() remove the item from the container (in this case a vector)?
why we need to call erase() again?

remove_if(first, last, pred) removes unwanted elements from the sequence
[first, last) and it copies the remaining elements to the places of the
removed elements. But it does not actually discard unused space from the end
of the sequence. For each element removed, you get a copy of another
element. Basically remove_if does something like

iterator free = first;
while (first != last)
{
if (badValue(*first))
++first;
else
*free++ = *first++;
}
return free;

HTH
Heinz

 

[Pete Becker]

My question is "For the first case, why we need to call c.erase() again
and pass in the return value of remove_if()?" Doesn't the call to
remove_if() remove the item from the container (in this case a vector)?
why we need to call erase() again?

Algorithms work on sequences designated by pairs of iterators. They do
not work on containers. remove_if "removes" elements from the sequence
that's passed to it by copying replacement elements on top of rejected
ones, and giving back a new end iterator that designates the end of the
new sequence. Typically that sequence is shorter than the original one,
and any elements pointed to by the end iterator and beyond are
irrelevant to the algorithm.

The algorithm doesn't know anything about the source of the sequence,
and cannot modify a container that might have been the source of the
sequence that was passed to it. But because it rearranges elements, you
can use the end iterator that it returns to tell you where the remaining
elements are in your container: they're the ones from the end iterator
returned by the algorithm to the actual end of the container. So you
erase 'em if that's appropriate.

If I haven't made too many typos, try this:

int data[] = { 1, 2, 3, 4, 5, 6, 7 }

struct is_odd
{
bool operator()(int val)
{
return val & 1;
}
};

int main()
{
int *begin = data;
int *end = data + sizeof(data) / sizeof(*data);

std::cout << "Original sequence: ";
std::copy(begin, end, std:stream_iterator<int>(std::cout, " ");
std::cout << '\n';

int *new_end = std::remove_if(begin, end, is_odd());
// nothing to erase, 'cause the container's size is fixed

std::cout << "Modified sequence: ";
std::copy(begin, new_end, std:stream_iterator<int>(std::cout, " ");
std::cout << '\n';

std::cout << "Original container: ";
std::copy(begin, end, std:stream_iterator<int>(std::cout, " ");
std::cout << '\n';

return 0;
}

Now modify it to use a vector<int> instead of an array.

 

[Piotr]

Thanks.
But why I don't need to do that for list?

 

[Thomas Tutone]

Thanks.
But why I don't need to do that for list?

Well, to quote your example (assume vec is a std::vector and list is a
std::list):

bool badValue(int x);

vec.erase(std::remove_if(vec.begin(),
vec.end(),
badValue), vec.end());

list.remove_if(badValue);

In the vector example, you are using an algorithm, std::remove_if. In
the list example, you are using a std::list member function,
std::list::remove_if. The algorithm does not erase the removed
elements. The list member function does erase the removed elements.
In other words, the algorithm and the member function are not the same.

If you can, get yourself a copy of Josuttis's The C++ Standard Library.
It is an excellent resource, and will answer all of your questions
like this.

Best regards,

Tom

 

[Ian Collins]

Thanks.
But why I don't need to do that for list?

Do what? Please quote.

 

[Pete Becker]

Thanks.
But why I don't need to do that for list?

Because list::remove_if is a member function of the template. Unlike the
standalone algorithm, it knows that it's working on a container.

 

[Piotr]

After the return of remove_if() to remove elements from the container
which matches the condition, how can I get the address of all the
removed elements and call their destructor?

Thank you.

 

[Thomas Tutone]

After the return of remove_if() to remove elements from the container
which matches the condition, how can I get the address of all the
removed elements and call their destructor?

Which remove_if() are you referring to? If you are referring to the
algorithm std::remove_if, then calling erase() as you showed in your
original example will results in the removed elements' destructors
being called automatically.

If you are referring to the std::list member function remove_if, that
function will result in the removed elements' destructors being called
automatically.

In neither case you should you explicitly call the elements'
destructors yourself.

Best regards,

Tom

 

[Richard Herring]

After the return of remove_if() to remove elements from the container
which matches the condition, how can I get the address of all the
removed elements and call their destructor?

No need. container.erase(remove_if(/*...*/), container.end()) will do
it for you.

(Note that the sequence bounded by remove_if() and container.end() is
stuff you no longer need, but not necessarily "the removed elements",
since some of the unwanted elements may have had wanted ones copied into
them.)