Issue 2439: unique_copy() sometimes can't fall back to reading its output

2439. `unique_copy()` sometimes can't fall back to reading its output

Section: 26.7.9 [alg.unique] Status: C++17 Submitter: Stephan T. Lavavej Opened: 2014-10-01 Last modified: 2017-07-30

Priority: 3

View all other issues in [alg.unique].

View all issues with C++17 status.

Discussion:

unique_copy()'s wording says that if it's given input-only and output-only iterators, it needs the input's value type to be copyable. This is correct, because in this case the algorithm must have a local element copy in order to detect duplicates.

The wording also says that if it's given an InputIterator that's forward or stronger, the input's value type doesn't have to be copyable. This is also correct, because in this case the algorithm can reread the input in order to detect duplicates.

Finally, the wording says that if it's given an input-only iterator with an OutputIterator that's forward or stronger, the input's value type doesn't have to be copyable. This is telling the algorithm to compare its input to its output in order to detect duplicates, but that isn't always possible! If the input and output have the same value type, then they can be compared (as long as *result = *first behaves sanely; see below). If they have different value types, then we can't compare them.

This could be resolved by requiring heterogeneous value types to be comparable in this situation, but that would be extremely tricky to wordsmith (as it would challenge the concept of "group of equal elements" used by the Effects). It will be vastly simpler and more effective to extend the "local element copy" requirement to this scenario.

Note that the input-only, output forward-or-stronger, identical value types scenario needs a bit of work too. We always require *result = *first to be "valid", but in this case we need to additionally require that the assignment actually transfers the value. (Otherwise, we'd be allowing an op=() that ignores *first and always sets *result to zero, or other unacceptable behavior.) This is just CopyAssignable.

(What happens when unique_copy() is given a move_iterator is a separate issue.)

To summarize:

input forward+: no additional requirements
input-only, output forward+, same value types: needs CopyAssignable
input-only, output forward+, different value types: needs CopyConstructible and CopyAssignable
input-only, output-only: needs CopyConstructible and CopyAssignable

[Urbana 2014-11-07: Move to Ready]

Proposed resolution:

This wording is relative to N3936.

Change 26.7.9 [alg.unique] p5, as depicted:
```
template<class InputIterator, class OutputIterator>
OutputIterator
unique_copy(InputIterator first, InputIterator last,
            OutputIterator result);
template<class InputIterator, class OutputIterator,
         class BinaryPredicate>
OutputIterator
unique_copy(InputIterator first, InputIterator last,
            OutputIterator result, BinaryPredicate pred);
```
-5- Requires: The comparison function shall be an equivalence relation. The ranges [first,last) and [result,result+(last-first)) shall not overlap. The expression *result = *first shall be valid. If neither InputIterator nor OutputIterator meets the requirements of forward iterator then the value type of InputIterator shall be CopyConstructible (Table 21) and CopyAssignable (Table 23). Otherwise CopyConstructible is not required.Let T be the value type of InputIterator. If InputIterator meets the forward iterator requirements, then there are no additional requirements for T. Otherwise, if OutputIterator meets the forward iterator requirements and its value type is the same as T, then T shall be CopyAssignable (Table 23). Otherwise, T shall be both CopyConstructible (Table 21) and CopyAssignable.

2439. unique_copy() sometimes can't fall back to reading its output

2439. `unique_copy()` sometimes can't fall back to reading its output