Remove algo code duplication
François Dumont
frs.dumont@gmail.com
Sat Apr 28 08:02:00 GMT 2012
Hi
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
iterator_traits<_RandomAccessIterator>::reference.
2012-04-27 François Dumont <fdumont@gcc.gnu.org>
* 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/2.cc: New.
* testsuite/25_algorithms/lexicographical_compare/3.cc: New.
* testsuite/25_algorithms/partial_sort_copy/3.cc: New.
Tested under linux x86_64 normal and debug mode.
François
-------------- next part --------------
A non-text attachment was scrubbed...
Name: algos.patch
Type: text/x-patch
Size: 107403 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20120428/c94e8445/attachment.bin>
More information about the Libstdc++
mailing list