implement std::ranges::unique and std::ranges::unique_copy
- implement std::ranges::unique that delegates to std::unique
- fix classic std::unique_copy does not work with output iterator that satisfies both InputIterator and OutputIterator requirements.
background: The classic implementation does tag dispatch on the iteartor_category of the output iterator and uses output_iterator_tag as a fallback. However, if the user passes an output iterator that satisfy both
InputIterator and OutputIterator requirement, the iteartor_category is likely to be input_iteartor_tag and input_iteartor_tag does not derive from output_iterator_tag. So the fallback case would not work.
See this example where msvc stl correctly implemented and libc++ errors out
The fix to the classic algorithm is strictly following the wording
If InputIterator meets the Cpp17ForwardIterator requirements, then there are no additional requirements for T.
Having an overload that takes __reread_from_input_tag, which does auto prev = in; comp(*prev, *in)
Otherwise, if OutputIterator meets the Cpp17ForwardIterator requirements and its value type is the same as T, then T meets the Cpp17CopyAssignable (Table 33) requirements.
Having an overload that takes __reread_from_output_tag, which does comp(*out, *in)
Otherwise, T meets both the Cpp17CopyConstructible (Table 31) and Cpp17CopyAssignable requirements.
Having an overload that takes __read_from_tmp_value_tag, which does value_type tmp = *in; ++in; comp(tmp, *in)
- implement std::ranges::unique_copy, which reuses the implementation above, but slightly different dispatching condition as ranges version has slightly different requires constraints.
Also I believe the std::ranges::unique_copy is incorrectly constrained. More specifically, the intent of the constraint (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) was to allow implementations to write comp(*in ,*out) (ignore std::invoke and projection for now). However, I and O having the same value_type is not enough to allow comp(*in ,*out), because that expression only uses the iter_reference_t of the I and O, instead of the iter_value_t. See discussion here
But anyway, I decided that in this patch, implement what exactly in the spec and bring up the issue in LWG later.