Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[forwardlist.ops] bogus specification of forward_list::unique LWG2997 #4221

Closed
zygoloid opened this issue Sep 22, 2020 · 6 comments · Fixed by #4695
Closed

[forwardlist.ops] bogus specification of forward_list::unique LWG2997 #4221

zygoloid opened this issue Sep 22, 2020 · 6 comments · Fixed by #4695
Assignees
@jwakely
Labels
lwg Issue must be reviewed by LWG. not-editorial Issue is not deemed editorial; the editorial issue is kept open for tracking.

Comments

@zygoloid
Copy link
Member

zygoloid commented Sep 22, 2020 •
edited

The specification for forward_list::unique says:

Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version with no arguments) or pred(*i, *(i - 1)) (for the version with a predicate argument) holds.

Err, what?

Given {1, 1, 1, 1, 1, 2, 2, 2, 2, 2}, we:

  1. consider the range [first + 1, last): {1, 1, 1, 1, 2, 2, 2, 2, 2}.
  2. identify the elements for which *i == *(i-1), dropping the first 2.
  3. identify the consecutive groups of equal elements from step (2): {1, 1, 1, 1} and {2, 2, 2, 2}.
  4. erase all but the first element from each such group.

The result is {1, 1, 2, 2}. That doesn't seem right.

The problem here is that we express basically every part of the rules twice or three times in the same sentence, and usually at least all but one of those repetitions is wrong. (Eg, compare "equal" to the more careful description later, compare "all but the first" with the use of [first + 1, last) and *i == *(i-1).)

Perhaps we meant:

Erases all but the first element from every consecutive group of equal elements. That is, for a nonempty list, erases all elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version with no arguments) or pred(*i, *(i - 1)) (for the version with a predicate argument) holds.

Oh, and while we're here: what are first and last supposed to be here? I think it means begin() and end()...
@zygoloid
Copy link
Member Author

zygoloid commented Sep 22, 2020 •
edited

Similar jumbled words appear in other places:

[alg.unique]p1:

Effects: For a nonempty range, eliminates all but the first element from every consecutive group of equivalent elements. That is, for a nonempty range, erases all elements referred to by the iterator i in the range [first + 1, last) for which E is true.

[list.ops]p20:

Effects: Erases all but the first element from every consecutive group of equal elements. That is, for a nonempty list, erases all elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version of unique with no arguments) or pred(*i, *(i - 1)) (for the version of unique with a predicate argument) holds.

The std::list version also uses nonexistent first and last values.

@zygoloid
Copy link
Member Author

@jwakely I think we can handle this editorially, but let me know if you'd prefer LWG to take this.

@jwakely
Copy link
Member

jwakely commented Sep 22, 2020

I'm happy for it to be treated editorially. There's no disagreement about what the expected semantics are, and no implementation divergence, so it's just a case of using words that aren't bad.

@tkoeppe tkoeppe changed the title [forwardlist.ops] bogus specification fo forward_list::unique [forwardlist.ops] bogus specification of forward_list::unique Sep 26, 2020
@jensmaurer jensmaurer mentioned this issue Jan 14, 2021
Closed
@jensmaurer
Copy link
Member

jensmaurer commented Jan 14, 2021 •
edited

@zygoloid : The proposed change to [alg.unique] seems incorrect. The term "erases" is certainly undefined in the context of an algorithm; we don't have a reference to the enclosing container where we could "erase".

@timsong-cpp
Copy link
Contributor

This overlaps https://cplusplus.github.io/LWG/issue2997 but that issue's PR doesn't fix the issue @zygoloid pointed out. That PR has a normative component though (the requirement that the predicate is an equivalence relation). I'll redraft.

@jensmaurer jensmaurer changed the title [forwardlist.ops] bogus specification of forward_list::unique [forwardlist.ops] bogus specification of forward_list::unique LWG 2997 Feb 23, 2021
@jensmaurer jensmaurer added lwg Issue must be reviewed by LWG. not-editorial Issue is not deemed editorial; the editorial issue is kept open for tracking. labels Feb 23, 2021
@jwakely
Copy link
Member

jwakely commented Mar 15, 2021

Is "consecutive group of equal elements" wrong as well? It is the equal elements which are consecutive, not the groups.

Arguably, given {1,1,2,3,3} there are two groups of equal elements, {1,1} and {3,3}, but they are not consecutive. So a hostile reading of "every consecutive group of equal elements" would be that nothing is removed here.

Would "from each group of consecutive equal elements" be better?

@jensmaurer jensmaurer changed the title [forwardlist.ops] bogus specification of forward_list::unique LWG 2997 [forwardlist.ops] bogus specification of forward_list::unique LWG2997 Jun 15, 2021
@jensmaurer jensmaurer mentioned this issue Jun 15, 2021
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@jwakely jwakely

Labels
lwg Issue must be reviewed by LWG. not-editorial Issue is not deemed editorial; the editorial issue is kept open for tracking.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

P2385R0 C++ Standard Library Issues to be moved in Virtual Plenary, June 2021 cplusplus/draft
4 participants
@zygoloid @jwakely @timsong-cpp @jensmaurer