Could method Vec::retain be optimized?


#1

Hi,

I was checking how method Vec::retain is implemented and I noticed that it performs a swap moving at the end of the vector the elements are not satisfying the passed predicate and then performs a truncate.

Why elements are swapped instead of just copied? There is no way to get it since the truncate throws them away.

I was wondering if it could be optimized as in STL C++ remove_if, that doesn’t perform any swap and just copy (taken from GCC source code ./libstdc++-v3/include/bits/stl_algo.h):

  template<typename _ForwardIterator, typename _Predicate>                                                        
 _ForwardIterator                                                                                              
  __remove_if(_ForwardIterator __first, _ForwardIterator __last,                                                
     _Predicate __pred)                                                                                        
 {                                                                                                             
   __first = std::__find_if(__first, __last, __pred);                                                          
   if (__first == __last)                                                                                      
 return __first;                                                                                               
   _ForwardIterator __result = __first;                                                                        
   ++__first;                                                                                                  
   for (; __first != __last; ++__first)                                                                        
 if (!__pred(__first))                                                                                         
   {                                                                                                           
     *__result = _GLIBCXX_MOVE(*__first);                                                                      
     ++__result;                                                                                               
  }                                                                                                           
   return __result;                                                                                            
 }

Thank you.


#2

It’s to preserve ownership semantics (the user suppiled closure can panic at any point, so the vec must be consistent through the whole operation). It could be simplified as a specialization for Copy elements (they don’t have destructors or move semantics).


#3

If it didn’t have to preserve order, it could do something like swap_remove to replace items from the end (and then recheck that index).


#4

Sorry for the necroposting, but I was checking my old posts (I am a gloomy guy :blush:) and I found this.

Could you please me explain me better your points.
I can understand that the closure can panic along its evaluation through vector elements, but I am not sure to have clearly understood what you meant with:

Why its implementation couldn’t drop the value and then copy the other value over it as the closure is evaluated on it?


#5

dropping a value can panic, so the vec is inconsistent during unwinding in that case.