Re: [boost] [ptr_container] erase_if implementation

From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2007-12-13 05:50:57

Michael Marcin skrev:
> 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.

It performs at most O(n * log(n)) swaps.

> 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)
>           )
, this_->c_private().end() );

  );
> }

Yes, I think your code will work and speed up the operation to have 
liniear complexity.

I'll apply this to trunk.

Thanks

-Thorsten