2997. LWG 491 and the specification of {forward_,}list::unique

Section: 26.3.10.5 [list.ops], 26.3.9.6 [forwardlist.ops] Status: New Submitter: Tim Song Opened: 2017-07-07 Last modified: 2017-07-12

Priority: 3

View all other issues in [list.ops].

View all issues with New status.

Discussion:

There are various problems with the specification of list::unique and its forward_list counterpart, some of which are obvious even on cursory inspection:

LWG 491, which pointed out many of those problems with the specification of list::unique, was closed as NAD with the rationale that

"All implementations known to the author of this Defect Report comply with these assumption", and "no impact on current code is expected", i.e. there is no evidence of real-world confusion or harm.
That implementations somehow managed to do the right thing in spite of obviously defective standardese doesn't seem like a good reason to not fix the defects.

[2017-07 Toronto Tuesday PM issue prioritization]

Priority 3; by the way, there's general wording in 28.3 [algorithms.requirements] p10 that lets us specify iterator arithmetic as if we were using random access iterators.

[2017-07-11 Tim comments]

I drafted the P/R fully aware of the general wording in 28.3 [algorithms.requirements] p10. However, that general wording is limited to Clause 28, so to make use of the shorthand permitted by that wording, we would need additional wording importing it to these subclauses.

Moreover, that general wording only defines a+n and b-a; it notably doesn't define a-n, which is needed here. And one cannot merely define a-n as a+(-n) since that has undefined behavior for forward iterators.

Proposed resolution:

This wording is relative to N4659.

  1. Edit 26.3.10.5 [list.ops] as indicated:

    void unique();
    template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
    

    -?- Requires: The comparison function shall be an equivalence relation.

    -19- Effects: If empty(), has no effects. Otherwise, eErases all but the first element from every consecutive group of equalequivalent elements referred to by the iterator i in the range [first + 1, last)[next(begin()), end()) for which *i == *(i-1)*j == *i (for the version of unique with no arguments) or pred(*i, *(i - 1))pred(*j, *i) (for the version of unique with a predicate argument) holds, where j is an iterator in [begin(), end()) such that next(j) == i. Invalidates only the iterators and references to the erased elements.

    -20- Throws: Nothing unless an exception is thrown by *i == *(i-1) or pred(*i, *(i - 1)) the equality comparison or the predicate.

    -21- Complexity: If the range [first, last) is not empty!empty(), exactly (last - first) - 1size() - 1 applications of the corresponding predicate, otherwise no applications of the predicate.

  2. Edit 26.3.9.6 [forwardlist.ops] as indicated:

    void unique();
    template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
    

    -?- Requires: The comparison function shall be an equivalence relation.

    -16- Effects: If empty(), has no effects. Otherwise, eErases all but the first element from every consecutive group of equalequivalent elements referred to by the iterator i in the range [first + 1, last)[next(begin()), end()) for which *i == *(i-1)*j == *i (for the version with no arguments) or pred(*i, *(i - 1))pred(*j, *i) (for the version with a predicate argument) holds, where j is an iterator in [begin(), end()) such that next(j) == i. Invalidates only the iterators and references to the erased elements.

    -17- Throws: Nothing unless an exception is thrown by the equality comparison or the predicate.

    -18- Complexity: If the range [first, last) is not empty!empty(), exactly (last - first) - 1distance(begin(), end()) - 1 applications of the corresponding predicate, otherwise no applications of the predicate.