1241. unique_copy needs to require EquivalenceRelation

Section: 26.7.9 [alg.unique] Status: C++11 Submitter: Daniel Krügler Opened: 2009-10-17 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [alg.unique].

View all issues with C++11 status.

Discussion:

A lot of fixes were silently applied during concept-time and we should not lose them again. The Requires clause of 26.7.9 [alg.unique]/5 doesn't mention that == and the predicate need to satisfy an EquivalenceRelation, as it is correctly said for unique. This was intentionally fixed during conceptification, were we had:

template<InputIterator InIter, class OutIter>
  requires OutputIterator<OutIter, RvalueOf<InIter::value_type>::type>
        && EqualityComparable<InIter::value_type>
        && HasAssign<InIter::value_type, InIter::reference>
        && Constructible<InIter::value_type, InIter::reference>
  OutIter unique_copy(InIter first, InIter last, OutIter result);

template<InputIterator InIter, class OutIter,
         EquivalenceRelation<auto, InIter::value_type> Pred>
  requires OutputIterator<OutIter, RvalueOf<InIter::value_type>::type>
        && HasAssign<InIter::value_type, InIter::reference>
        && Constructible<InIter::value_type, InIter::reference>
        && CopyConstructible<Pred>
  OutIter unique_copy(InIter first, InIter last, OutIter result, Pred pred);

Note that EqualityComparable implied an equivalence relation.

[ N.B. adjacent_find was also specified to require EquivalenceRelation, but that was considered as a defect in concepts, see 1000 ]

[ 2009-10-31 Howard adds: ]

Moved to Tentatively Ready after 5 positive votes on c++std-lib.

Proposed resolution:

Change 26.7.9 [alg.unique]/5 as indicated:

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);

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 (34) and CopyAssignable (table 36). Otherwise CopyConstructible is not required.