This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++17 status.

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

Section: 27.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.

1. Change 27.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`.