Boost logo

Boost :

From: Michael Marcin (mmarcin_at_[hidden])
Date: 2007-12-13 01:19:48


Hello,

I was looking at the implementation for ptr_sequence_adapter's erase_if
function and it seems a bit inefficient but I might be missing
something, as is usually the case.

Currently from what I can tell it loops through every item in the list
and deletes it if the predicate returns true and then marks the pointers
null. Afterwards it does a stable_partition on the whole list and erases
all null pointers.

stable_partition IIRC is a fairly expensive operation.

Wouldn't it make more sense the wrap the predicate in a functor that
intercepts the result of the predicate and deletes the pointer if the
result is true before returning that result. Then take that functor and
pass it into std::remove if and call c_private().erase with the result
of the remove_if?

i.e. something like the following (neither tested nor compiled)

template< class Fun, class Arg1 >
class void_ptr_delete_if
{
    Fun fun;
public:

    void_ptr_indirect_fun() : fun(Fun())
    { }

    void_ptr_indirect_fun( Fun f ) : fun(f)
    { }

    bool operator()( void* r ) const
    {
       BOOST_ASSERT( r != 0 );
       Arg1* arg1 = static_cast<Arg1*>(r);
       return fun( *arg1 ) ? delete arg1, true : false;
    }
};

template< class Pred >
void erase_if( iterator first, iterator last, Pred pred )
{
    this->c_private().erase(
          std::remove_if(first.iter_,last.iter_,
             void_ptr_delete_if<Pred,T>(pred)
          ) );
}

Thanks,

Michael Marcin


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk