Could method Vec::retain be optimized?



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>                                                        
  __remove_if(_ForwardIterator __first, _ForwardIterator __last,                                                
     _Predicate __pred)                                                                                        
   __first = std::__find_if(__first, __last, __pred);                                                          
   if (__first == __last)                                                                                      
 return __first;                                                                                               
   _ForwardIterator __result = __first;                                                                        
   for (; __first != __last; ++__first)                                                                        
 if (!__pred(__first))                                                                                         
     *__result = _GLIBCXX_MOVE(*__first);                                                                      
   return __result;                                                                                            

Thank you.


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).


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).


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?


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