Remove algo code duplication

François Dumont
Sat Apr 28 08:02:00 GMT 2012


     Here is an other attempt to remove duplication of code in 
implementation of Standard algos. There are several enhancements on the 
last proposal:

1. No usage of C++11 lambdas anymore, code works fine in C++98 and code 
has been really deleted this time. About 700 lines removed in stl_algo.h 
for instance.

2. Compatible with existing code, code submitted by Christopher last 
time will still compile. To do so I used 
std::iterator_traits<>::reference type so that if the iterator is not 
const then the operator do not have to take const reference or to be 
const qualified neither. For the same reason I have also avoided some 
const qualifiers on the introduced functors.

3. It is less complex than in libstdcxx_so_7 branch: Introduced functors 
always have one operator() so that ambiguity between different overloads 
is impossible. To do so I used 2 techniques:
     - For equal_range and lexicographical_compare algos, the ones that 
really need 2 overloads, I simply pass 2 functors, one to do lhs < rhs 
and one for rhs < lhs; when the functor comes from the user code it is 
the same that is passed twice.
     - In other more complex situation where an algorithm calls other 
internal algos resulting in the functor being called with potentially 
many slightly different parameter types I use a rebind technique. When 
there is a call to an internal algo that need a specific functor 
signature I rebind the input functor to match it. In _RebindHelper I 
detect when the functor is my newly introduced __gnu_cxx::__ops::less 
functor and change it in this case, otherwise it remains unchanged.

In libstdcxx_so_7 branch the algo version using operators was calling 
the version taking a functor. The result was that concept checks on the 
operator version was performed twice. It is not a big concern when it is 
really pure concept checks but in trunk there is also the debug checks 
that can be quite expensive, checking that a range is sorted for 
instance. So I prefer to introduce an internal implementation that 
contains only the algo implementation without any concept checks and 
have it call from the Standard algos. Those pure implementations are 
also the one used for internal purpose.

Note that doing this job I introduce 2 small unrelated changes:
- __move_merge used to have 2 template iterator types but was called 
only with one, I simplify it.
- __unguarded_partition used to have 3 template parameters: 
_RandomAccessIterator, _Tp and _Compare. It was taking a const reference 
to _Tp which was a useless constraint for the functor. So it now only 
have 2 template parameters, const _Tp& has been replaced by 

2012-04-27  François Dumont <>

     * include/bits/predefined_ops.h: New.
     * include/bits/stl_algobase.h: Use functors from latter file to remove
     duplication of algorithm implementation.
     * include/bits/stl_algo.h: Likewise.
     * include/bits/stl_heap.h: Likewise.
     * testsuite/25_algorithms/lexicographical_compare/ New.
     * testsuite/25_algorithms/lexicographical_compare/ New.
     * testsuite/25_algorithms/partial_sort_copy/ New.

Tested under linux x86_64 normal and debug mode.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: algos.patch
Type: text/x-patch
Size: 107403 bytes
Desc: not available
URL: <>

More information about the Libstdc++ mailing list