Re: [boost] [ptr_container] erase_if implementation

From: Michael Marcin (mmarcin_at_[hidden])
Date: 2007-12-13 12:49:13

Thorsten Ottosen wrote:
> 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.
> 

I'll update ptr_container from 1.34.1 to trunk and give it a try.

Thanks,

Michael Marcin