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