Re: fast method of removing an element from STL list

Tech-Archive recommends: Fix windows errors by optimizing your registry

bob wrote:
> My current problem is that I have a list of pointers to class event.
> Class event has a data member called target (pointer to type
> event_handler). I wish to remove the event from the list depending upon
> the value of target. Since there is only one event with a prescribed
> value, the fastest way to do this would probably be:
>
> myList.erase(find_if(myList.begin(), myList.end(),
> someCriterion(target_to_remove));
>
> The problem stems from the need to define the removal criterion. I have
> tried the following:
>
> class someCriterion: public std::binary_function<event*,
> event_handler*, bool> {

Nope, the *_if() functions don't take a binary function but a predicate,
i.e. they feed the predicate an element of the sequence and the predicate
returns true or false. Using your strategy, you would have to use bind_2nd
to create a predicate from it.


> result_type operator()(first_argument_type ev, second_argument_type
> dest) {
> if(ev->target == dest) return true;
> else return false;
> } // () overload

Another good idea is to make operator() a const memberfunction of the
predicate class.

> From this forum, I learned that the functor must be derived from
> binary_function if bind2nd is to be used to permit a binary predicate
> to be used in place of a unary predicate.
>
> To remove the event I tried:
>
> std::list<event*>::iterator pos = find_if(myList.begin(), myList.end(),
> bind2nd(someCriterion(), target_to_remove));
> myList.erase(pos);

Ah, so you knew that already...

> From this forum and Josuttis' book I expected the event ptr in the list
> to act as the 1st argument of someCriterion and bind2nd to facilitate
> placing target_to_remove as the 2nd argument.
>
> The problem with this approach is that it generates an error:
> c:\Program Files\Microsoft Visual Studio .NET
> 2003\Vc7\include\functional(321): error C3848: expression having type
> 'const someCriterion' would lose some const-volatile qualifiers in
> order to call 'std::binary_function<_Arg1,_Arg2,_Result>::result_type
> sent_to::operator() (...)'

And here is where it fails because operator() is not a const memberfunction.

> class someCriterion: public std::binary_function<event*,
> event_handler*, bool> {
> public:
> someCriterion(first_argument_type ev) : local_event(ev) {};
> first_argument_type local_event;
> result_type operator()(second_argument_type dest) {
> if(local_event->target == dest) return true;
> else return false;
> } // () overload
> };
>
> This does not work either :(

It also doesn't make sense: binary function means a function taking two
parameters, but your operator() takes only one. Other than that, this is
the way to go.

> In this case, the line:
>
> std::list<event*>::iterator pos = find_if(myList.begin(), myList.end(),
> bind2nd(someCriterion(), target_to_remove));

Since you have a unary function, bind2nd makes no sense. Instead, you
omitted the argument to the ctor of someCriterion, but there is no ctor
taking no arguments:

> NET\scheduler.cpp(87): error C2512: 'someCriterion::someCriterion' : no
> appropriate default constructor available


> I have changed the line to:
>
> std::list<event*>::iterator pos = find_if(myList.begin(), myList.end(),
> someCriterion(target_to_remove));
>
> This unfortunately generated a different compiler error:
>
> d:\MyDocuments\Visual Studio Projects\802.11 NET\802.11
> NET\scheduler.cpp(87): error C2440: 'type cast' : cannot convert from
> 'event_handler *' to 'someCriterion'

This would have worked, but second_argument_type in the functor is
event_handler* and the algorithm tries to feed it objects of type event*.

> I am sure this must be a very simple problem to solve, however, I have
> been unable to find a solution on this forum.

You were soo close to the solution, I hope you see the picture now and the
different ways you could go.

Uli

--
http://got.to/quote
I won't help you unless you make your posts readable or provide a
fascinating problem.

.