- Title
- LWG 491 and the specification of {forward_,}list::unique
- Status
- new
- Section
- [list.ops][forwardlist.ops]
- Submitter
- Tim Song

Created on **2017-07-07.00:00:00**
last changed **2 months ago**

Date: 2021-02-23.17:51:38

**Proposed resolution:**

This wording is relative to N4878.

Edit [list.ops] as indicated:

-1- Since lists allow fast insertion and erasing from the middle of a list, certain operations are provided specifically for them.

^{222}In this subclause, arguments for a template parameter named`Predicate`or`BinaryPredicate`shall meet the corresponding requirements in [algorithms.requirements]. The semantics of`i + n`and`i - n`, where`i`is an iterator into the list and`n`is an integer, are the same as those of`next(i, n)`and`prev(i, n)`, respectively. For`merge`and`sort`, the definitions and requirements in [alg.sorting] apply.[…]

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

-?- Let

`binary_pred`be`equal_to<>{}`for the first overload.-?-

*Preconditions:*`binary_pred`is an equivalence relation.-20-

*Effects:*Erases all but the first element from every consecutive group of~~equal~~equivalent elements. That is, for a nonempty list, erases all elements referred to by the iterator`i`in the rangefor which~~[first + 1, last)~~[begin() + 1, end())`*i == *(i-1)`(for the version of`unique`with no arguments) or`binary_pred(*i, *(i - 1))`is`true`~~(for the version of~~. Invalidates only the iterators and references to the erased elements.`unique`with a predicate argument) holds-21-

*Returns*: The number of elements erased.-22-

*Throws:*Nothing unless an exception is thrown bythe predicate.`*i == *(i-1)`or`pred(*i, *(i - 1))`-23-

*Complexity:*If~~the range~~`[first, last)`is not empty`empty()`is`false`, exactlyapplications of the corresponding predicate, otherwise no applications of the predicate.~~(last - first) - 1~~size() - 1Edit [forwardlist.ops] as indicated:

-1- In this subclause, arguments for a template parameter named

`Predicate`or`BinaryPredicate`shall meet the corresponding requirements in [algorithms.requirements]. The semantics of`i + n`, where`i`is an iterator into the list and`n`is an integer, are the same as those of`next(i, n)`. The expression`i - n`, where`i`is an iterator into the list and`n`is an integer, means an iterator`j`such that`j + n == i`is`true`. For`merge`and`sort`, the definitions and requirements in [alg.sorting] apply.[…]

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

-?- Let

`binary_pred`be`equal_to<>{}`for the first overload.-?-

*Preconditions:*`binary_pred`is an equivalence relation.-18-

*Effects:*Erases all but the first element from every consecutive group of~~equal~~equivalent elements. That is, for a nonempty list, erases all elements referred to by the iterator`i`in the rangefor which~~[first + 1, last)~~[begin() + 1, end())`*i == *(i-1)`(for the version with no arguments) or`binary_pred(*i, *(i - 1))`is`true`~~(for the version with a predicate argument) holds~~. Invalidates only the iterators and references to the erased elements.-19-

*Returns*: The number of elements erased.-20-

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

*Complexity:*If~~the range~~`[first, last)`is not empty`empty()`is`false`, exactlyapplications of the corresponding predicate, otherwise no applications of the predicate.~~(last - first) - 1~~distance(begin(), end()) - 1

Date: 2021-02-21.00:00:00

*[ 2021-02-21 Tim redrafts ]*

The wording below incorporates editorial pull request 4465.

Date: 2017-07-11.00:00:00

*[ 2017-07-11 Tim comments ]*

I drafted the P/R fully aware of the general wording in [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.

**Previous resolution [SUPERSEDED]:**

This wording is relative to N4659.

Edit [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:Ifempty(), has no effects. Otherwise, e~~E~~rases all but the first element from every consecutive group of~~equal~~equivalent elements referred to by the iteratoriin the rangefor which~~[first + 1, last)~~[next(begin()), end())(for the version of~~*i == *(i-1)~~*j == *iuniquewith no arguments) or(for the version of~~pred(*i, *(i - 1))~~pred(*j, *i)uniquewith a predicate argument) holds, wherejis an iterator in[begin(), end())such thatnext(j) == i. Invalidates only the iterators and references to the erased elements.-20-

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

Complexity:If~~the range~~[first, last)is not empty!empty(), exactlyapplications of the corresponding predicate, otherwise no applications of the predicate.~~(last - first) - 1~~size() - 1Edit [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:Ifempty(), has no effects. Otherwise, e~~E~~rases all but the first element from every consecutive group of~~equal~~equivalent elements referred to by the iteratoriin the rangefor which~~[first + 1, last)~~[next(begin()), end())(for the version with no arguments) or~~*i == *(i-1)~~*j == *i(for the version with a predicate argument) holds, where~~pred(*i, *(i - 1))~~pred(*j, *i)jis an iterator in[begin(), end())such thatnext(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(), exactlyapplications of the corresponding predicate, otherwise no applications of the predicate.~~(last - first) - 1~~distance(begin(), end()) - 1

Date: 2017-07-12.01:58:24

*[ 2017-07 Toronto Tuesday PM issue prioritization ]*

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

Date: 2017-07-07.00:00:00

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

- It refers to the identifiers
`first`and`last`, which aren't even defined. - It uses
`i - 1`on non-random-access iterators - in the case of`forward_list`, on forward-only iterators. - The resolution of LWG 202, changing the specification of
`std::unique`to require an equivalence relation and adjusting the order of comparison, weren't applied to these member functions.

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.

History | |||
---|---|---|---|

Date | User | Action | Args |

2021-02-22 04:26:47 | admin | set | messages: + msg11693 |

2017-07-12 03:44:21 | admin | set | messages: + msg9362 |

2017-07-12 01:58:24 | admin | set | messages: + msg9360 |

2017-07-08 14:02:23 | admin | set | messages: + msg9326 |

2017-07-07 00:00:00 | admin | create |