Section: 23.3.9.5 [list.ops] Status: NAD Submitter: Thomas Mang Opened: 2004-12-12 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [list.ops].
View all issues with NAD status.
Discussion:
In Section 23.3.9.5 [list.ops], paragraphs 19 to 21 describe the behavior of the std::list<T, Allocator>::unique operation. However, the current wording is defective for various reasons.
1) Analysis of current wording:
23.3.9.5 [list.ops], paragraph 19:
Current wording says: "Effects: Eliminates 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 of unique with no argument) or pred(*i, *(i -1)) (for the version of unique with a predicate argument) holds."
This sentences makes use of the undefined term "Eliminates". Although it is, to a certain degree, reasonable to consider the term "eliminate" synonymous with "erase", using "Erase" in the first place, as the wording of 23.3.9.5 [list.ops], paragraph 15 does, would be clearer.
The range of the elements referred to by iterator i is "[first + 1, last)". However, neither "first" nor "last" is defined.
The sentence makes three times use of iterator arithmetic expressions ( "first + 1", "*i == *(i - 1)", "pred(*i, *(i -1))" ) which is not defined for bidirectional iterator [see DR submitted by Thomas Mang regarding invalid iterator arithmetic expressions].
The same problems as pointed out in DR 202 (equivalence relation / order of arguments for pred()) apply to this paragraph.
23.3.9.5 [list.ops], paragraph 20:
Current wording says: "Throws: Nothing unless an exception in thrown by *i == *(i-1) or pred(*i, *(i - 1))"
The sentence makes two times use of invalid iterator arithmetic expressions ( "*i == *(i - 1)", "pred(*i, *(i -1))" ).
[Note: Minor typos: "in" / missing dot at end of sentence.]
23.3.9.5 [list.ops], paragraph 21:
Current wording says: "Complexity: If the range (last - first) is not empty, exactly (last - first) - 1 applications of the corresponding predicate, otherwise no application of the predicate.
See DR 315 regarding "(last - first)" not yielding a range.
Invalid iterator arithmetic expression "(last - first) - 1" left .
2) Description of intended behavior:
For the rest of this Defect Report, it is assumed that "eliminate" is supposed to be synonymous to "erase", that "first" is equivalent to an iterator obtained by a call to begin(), "last" is equivalent to an iterator obtained by a call to end(), and that all invalid iterator arithmetic expressions are resolved as described in DR submitted by Thomas Mang regarding invalid iterator arithmetic expressions.
Furthermore, the resolutions of DR 202 are considered regarding equivalence relation and order of arguments for a call to pred.
All implementations known to the author of this Defect Report comply with these assumptions, apart from the impact of the alternative resolution of DR 202. Except for the changes implied by the resolutions of DR 202, no impact on current code is expected.
3) Proposed fixes:
Change 23.3.9.5 [list.ops], paragraph 19 to:
"Effect: Erases all but the first element from every consecutive group of elements, referred to by the iterator i in the range [begin(), end()), for which the following conditions hold: *(i-1) == *i (for the version of unique with no argument) or pred(*(i-1), *i) != false (for the version of unique with a predicate argument)."
Comments to the new wording:
a) The new wording was influenced by DR 202 and the resolutions presented there. If DR 202 is resolved in another way, the proposed wording need also additional review. b) "Erases" refers in the author's opinion unambiguously to the member function "erase". In case there is doubt this might not be unamgibuous, a direct reference to the member function "erase" is suggested [Note: This would also imply a change of 23.3.9.5 [list.ops], paragraph 15.]. c) The expression "(i - 1)" was left, but is expected that DR submitted by Thomas Mang regarding invalid iterator arithmetic expressions will take this into account. d) The wording "(for the version of unique with no argument)" and "(for the version of unique with a predicate argument)" was kept consciously for clarity. e) "begin()" substitutes "first", and "end()" substitutes "last". The range need adjustment from "[first + 1, last)" to "[begin(), end())" to ensure a valid range in case of an empty list. f) If it is considered that the wording is unclear whether it declares the element of a group which consists of only a single element implicitly to be the first element of this group [Note: Such an interpretation could eventually arise especially in case size() == 1] , the following additional sentence is proposed: "If such a group of elements consists of only a single element, this element is also considered the first element."
Change 23.3.9.5 [list.ops], paragraph 20 to:
"Throws: Nothing unless an exception is thrown by *(i-1) == *i or pred(*(i-1), *i)."
Comments to the new wording:
a) The wording regarding the conditions is identical to proposed 23.3.9.5 [list.ops], paragraph 19. If 23.3.9.5 [list.ops], paragraph 19 is resolved in another way, the proposed wording need also additional review. b) The expression "(i - 1)" was left, but is expected that DR submitted by Thomas Mang regarding invalid iterator arithmetic expressions will take this into account. c) Typos fixed.
Change 23.3.9.5 [list.ops], paragraph 21 to:
"Complexity: If empty() == false, exactly size() - 1 applications of the corresponding predicate, otherwise no applications of the corresponding predicate."
Comments to the new wording:
a) The new wording is supposed to also replace the proposed resolution of DR 315, which suffers from the problem of undefined "first" / "last".
5) References to other DRs:
See DR 202. See DR 239. See DR 315. See DR submitted by Thomas Mang regarding invalid iterator arithmetic expressions.
Proposed resolution:
Rationale:
"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.