https://gcc.gnu.org/bugzilla/show_bug.cgi?id=120386
--- Comment #3 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The master branch has been updated by Jonathan Wakely <r...@gcc.gnu.org>: https://gcc.gnu.org/g:ff2e49f444e851b005ba8abcf610a85bc1d7ae3a commit r16-1056-gff2e49f444e851b005ba8abcf610a85bc1d7ae3a Author: Jonathan Wakely <jwak...@redhat.com> 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/25_algorithms/unique_copy/lwg2439.cc: New test. Reviewed-by: Tomasz KamiÅski <tkami...@redhat.com>
