Topic: STL (specification) BUG: lost function object state in remove_if()


Author: Nico Josuttis <nico@bredex.de>
Date: 1996/04/11
Raw View
Hi,
the big advantage of the usage of function objects with algorithms is,
that they have a state. But there is a problem, this state may get lost
IN THE MIDDLE of a running algorithm like remove_if().

This is due to the fact that the implementation calls two function:
 > template <class ForwardIterator, class Predicate>
 > ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
 >                           Predicate pred) {
 >   first = find_if(first, last, pred);
 >   ForwardIterator next = first;
 >   return first == last ? first : remove_copy_if(++next, last, first, pred);
 > }
But both, find_if() and remove_copy_if(), are called with call-by-value for
pred. This is a problem if for example i want to delete the first occurence
of a value. It results in removing the first and the second value, the first,
because find_if() finds it, the second because remove_copy_if() finds that
as first. Its pred doesn't know that find_if()s-pred has the state changed
into "found".
Tricky problem, isn't it ?

I think, we have to change algorithms here so that all internal calls
a made with call by reference.
If this results in prefomance penalties, we should implement the algorithm
in another way.

Anyway a big hint should be made in the specification either that this danger
exists or, if it is fixed, that the function object is the original object
operator() is called for every elem.

Any meanings ?
--------
Nico                             address: BREDEX GmbH
email:   nico@bredex.de                   Nicolai Josuttis
                                          Fallersleber-Tor-Wall 23
phone:   +49 531 24330-0                  D-38100 Braunschweig
fax:     +49 531 24330-99                 Germany
--------
---
[ comp.std.c++ is moderated.  To submit articles: try just posting with      ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu         ]
[ FAQ:      http://reality.sgi.com/employees/austern_mti/std-c++/faq.html    ]
[ Policy:   http://reality.sgi.com/employees/austern_mti/std-c++/policy.html ]
[ Comments? mailto:std-c++-request@ncar.ucar.edu                             ]