This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofCD1 status.
Section: 26.7.9[alg.unique]Status:CD1Submitter: Andrew KoenigOpened: 2000-01-13Last modified: 2016-01-28
Priority:Not Prioritized
View all otherissues in [alg.unique].
View all issues withCD1 status.
Discussion:
What should unique() do if you give it a predicate that is not anequivalence relation? There are at least two plausible answers:
1. You can't, because 25.2.8 says that it it "eliminates all but the first element from every consecutive group of equal elements..." and it wouldn't make sense to interpret "equal" as meaning anything but an equivalence relation. [It also doesn't make sense to interpret "equal" as meaning ==, because then there would never be any sense in giving a predicate as an argument at all.]
2. The word "equal" should be interpreted to mean whatever the predicate says, even if it is not an equivalence relation (and in particular, even if it is not transitive).
The example that raised this question is from Usenet:
int f[] = { 1, 3, 7, 1, 2 };int* z = unique(f, f+5, greater<int>());If one blindly applies the definition using the predicategreater<int>, and ignore the word "equal", you get:
Eliminates all but the first element from every consecutive group of elements referred to by the iterator i in the range [first, last) for which *i > *(i - 1).
The first surprise is the order of the comparison. If we wanted toallow for the predicate not being an equivalence relation, then weshould surely compare elements the other way: pred(*(i - 1), *i). Ifwe do that, then the description would seem to say: "Break thesequence into subsequences whose elements are in strictly increasingorder, and keep only the first element of each subsequence". So theresult would be 1, 1, 2. If we take the description at its word, itwould seem to call for strictly DEcreasing order, in which case theresult should be 1, 3, 7, 2.
In fact, the SGI implementation of unique() does neither: It yields 1,3, 7.
Proposed resolution:
Change 26.7.9[alg.unique] paragraph 1 to:
For a nonempty range, eliminates all but the first element from everyconsecutive group of equivalent elements referred to by the iterator
iin the range [first+1, last) for which the followingconditions hold:*(i-1) == *iorpred(*(i-1), *i) !=false.
Also insert a new paragraph, paragraph 2a, that reads: "Requires: Thecomparison function must be an equivalence relation."
[Redmond: discussed arguments for and against requiring thecomparison function to be an equivalence relation. Straw poll:14-2-5. First number is to require that it be an equivalencerelation, second number is to explicitly not require that it be anequivalence relation, third number is people who believe they needmore time to consider the issue. A separate issue: Andy Sawyerpointed out that "i-1" is incorrect, since "i" can refer to the firstiterator in the range. Matt provided wording to address thisproblem.]
[Curaçao: The LWG changed "... the range (first,last)..." to "... the range [first+1, last)..." forclarity. They considered this change close enough to editorial to notrequire another round of review.]
Rationale:
The LWG also considered an alternative resolution: change 26.7.9[alg.unique] paragraph 1 to:
For a nonempty range, eliminates all but the first element from everyconsecutive group of elements referred to by the iterator
iin the range (first, last) for which the followingconditions hold:*(i-1) == *iorpred(*(i-1), *i) !=false.
Also insert a new paragraph, paragraph 1a, that reads: "Notes: Thecomparison function need not be an equivalence relation."
Informally: the proposed resolution imposes an explicit requirementthat the comparison function be an equivalence relation. Thealternative resolution does not, and it gives enough information sothat the behavior of unique() for a non-equivalence relation isspecified. Both resolutions are consistent with the behavior ofexisting implementations.