https://gcc.gnu.org/bugzilla/show_bug.cgi?id=120386
--- Comment #3 from GCC Commits ---
The master branch has been updated by Jonathan Wakely :
https://gcc.gnu.org/g:ff2e49f444e851b005ba8abcf610a85bc1d7ae3a
commit r16-1056-gff2e49f444e851b005ba8abcf610a85bc1d7ae3a
Author: Jonathan Wakely
Date: Wed May 21 20:12:50 2025 +0100
libstdc++: Implement LWG 2439 for std::unique_copy [PR120386]
The current overload set for __unique_copy handles three cases:
- The input range uses forward iterators, the output range does not.
This is the simplest case, and can just compare adjacent elements of
the input range.
- Neither the input range nor output range use forward iterators.
This requires a local variable copied from the input range and updated
by assigning each element to the local variable.
- The output range uses forward iterators.
For this case we compare the current element from the input range with
the element just written to the output range.
There are two problems with this implementation. Firstly, the third case
assumes that the value type of the output range can be compared to the
value type of the input range, which might not be possible at all, or
might be possible but give different results to comparing elements of
the input range. This is the problem identified in LWG 2439.
Secondly, the third case is used when both ranges use forward iterators,
even though the first case could (and should) be used. This means that
we compare elements from the output range instead of the input range,
with the problems described above (either not well-formed, or might give
the wrong results).
The cause of the second problem is that the overload for the first case
looks like:
OutputIterator
__unique_copy(ForwardIter, ForwardIter, OutputIterator, BinaryPred,
forward_iterator_tag, output_iterator_tag);
When the output range uses forward iterators this overload cannot be
used, because forward_iterator_tag does not inherit from
output_iterator_tag, so is not convertible to it.
To fix these problems we need to implement the resolution of LWG 2439 so
that the third case is only used when the value types of the two ranges
are the same. This ensures that the comparisons are well behaved. We
also need to ensure that the first case is used when both ranges use
forward iterators.
This change replaces a single step of tag dispatching to choose between
three overloads with two step of tag dispatching, choosing between two
overloads at each step. The first step dispatches based on the iterator
category of the input range, ignoring the category of the output range.
The second step only happens when the input range uses non-forward
iterators, and dispatches based on the category of the output range and
whether the value type of the two ranges is the same. So now the cases
that are handled are:
- The input range uses forward iterators.
- The output range uses non-forward iterators or a different value type.
- The output range uses forward iterators and has the same value type.
For the second case, the old code used __gnu_cxx::__ops::__iter_comp_val
to wrap the predicate in another level of indirection. That seems
unnecessary, as we can just use a pointer to the local variable instead
of an iterator referring to it.
During review of this patch, it was discovered that all known
implementations of std::unique_copy and ranges::unique_copy (except
cmcstl2) disagree with the specification. The standard (and the SGI STL
documentation) say that it uses pred(*i, *(i-1)) but everybody uses
pred(*(i-1), *i) instead, and apparently always has done. This patch
adjusts ranges::unique_copy to be consistent.
In the first __unique_copy overload, the local copy of the iterator is
changed to be the previous position not the next one, so that we use
++first as the "next" iterator, consistent with the logic used in the
other overloads. This makes it easier to compare them, because we aren't
using pred(*first, *next) in one and pred(something, *first) in the
others. Instead it's always pred(something, *first).
libstdc++-v3/ChangeLog:
PR libstdc++/120386
* include/bits/ranges_algo.h (__unique_copy_fn): Reorder
arguments for third case to match the first two cases.
* include/bits/stl_algo.h (__unique_copy): Replace three
overloads with two, depending only on the iterator category of
the input range. Dispatch to __unique_copy_1 for the
non-forward case.
(__unique_copy_1): New overloads for the case where the input
range uses non-forward iterators.
(unique_copy): Only pass the input range category to
__unique_copy.
* testsuite/2
