Issue 1207: Underspecified std::list operations?

1207. Underspecified `std::list` operations?

Section: 23.3.9.5 [list.ops] Status: C++11 Submitter: Loïc Joly Opened: 2009-09-13 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [list.ops].

View all issues with C++11 status.

Discussion:

It looks to me like some operations of std::list (sort, reverse, remove, unique & merge) do not specify the validity of iterators, pointers & references to elements of the list after those operations. Is it implied by some other text in the standard?

I believe sort & reverse do not invalidating anything, remove & unique only invalidates what refers to erased elements, merge does not invalidate anything (with the same precision as splice for elements who changed of container). Are those assumptions correct ?

[ 2009-12-08 Jonathan Wakely adds: ]

23.2.2 [container.requirements.general] paragraph 11 says iterators aren't invalidated unless specified, so I don't think it needs to be repeated on every function that doesn't invalidate iterators. list::unique says it "eliminates" elements, that should probably be "erases" because IMHO that term is used elsewhere and so makes it clearer that iterators to the erased elements are invalidated.

list::merge coud use the same wording as list::splice w.r.t iterators and references to moved elements.

Suggested resolution:

In 23.3.9.5 [list.ops] change paragraph 19
                                 void unique();
template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
Effects: ~~Eliminates~~ Erases all but the first element from every consecutive group ...
Add to the end of paragraph 23
void                          merge(list<T,Allocator>&& x);
template <class Compare> void merge(list<T,Allocator>&& x, Compare comp);
...

Effects: ... that is, for every iterator i, in the range other than the first, the condition comp(*i, *(i - 1) will be false. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.

[ 2009-12-12 Loïc adds wording. ]

[ 2010-02-10 Moved to Tentatively Ready after 5 positive votes on c++std-lib. ]

[ 2010-02-10 Alisdair opens: ]

I object to the current resolution of #1207. I believe it is overly strict with regard to list end iterators, being the only mutating operations to require such stability.

More importantly, the same edits need to be applied to forward_list, which uses slightly different words to describe some of these operations so may require subtly different edits (not checked.)

I am prepared to pick up the end() iterator as a separate (new) issue, as part of the FCD ballot review (BSI might tell me 'no' first ;~) but I do want to see forward_list adjusted at the same time.

[ 2010-03-28 Daniel adds the first 5 bullets in an attempt to address Alisdair's concerns. ]

[ 2010 Rapperswil: ]

The wording looks good. Move to Tentatively Ready.

[ Adopted at 2010-11 Batavia ]

Proposed resolution:

Change [forwardlist.ops]/12 as indicated:
```
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
```
12 Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_if()). This operation shall be stable: the relative order of the elements that are not removed is the same as their relative order in the original list. Invalidates only the iterators and references to the erased elements.
Change [forwardlist.ops]/15 as indicated:
```
template <class BinaryPredicate> void unique(BinaryPredicate pred);
```
15 Effects:: ~~Eliminates~~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. Invalidates only the iterators and references to the erased elements.
Change [forwardlist.ops]/19 as indicated:
```
void merge(forward_list<T,Allocator>&& x);
template <class Compare> void merge(forward_list<T,Allocator>&& x, Compare comp)
```
[..]

19 Effects:: Merges x into *this. This operation shall be stable: for equivalent elements in the two lists, the elements from *this shall always precede the elements from x. x is empty after the merge. If an exception is thrown other than by a comparison there are no effects. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
Change [forwardlist.ops]/22 as indicated:
```
void sort();
template <class Compare> void sort(Compare comp);
```
[..]

22 Effects:: Sorts the list according to the operator< or the comp function object. This operation shall be stable: the relative order of the equivalent elements is preserved. If an exception is thrown the order of the elements in *this is unspecified. Does not affect the validity of iterators and references.
Change [forwardlist.ops]/24 as indicated:
```
void reverse();
```
24 Effects:: Reverses the order of the elements in the list. Does not affect the validity of iterators and references.
Change 23.3.9.5 [list.ops], p15:
```
                           void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
```
Effects: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased elements.
Change 23.3.9.5 [list.ops], p19:
```
                                 void unique();
template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
```
Effects: ~~Eliminates~~ 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 of unique with no arguments) or pred(*i, *(i - 1)) (for the version of unique with a predicate argument) holds. Invalidates only the iterators and references to the erased elements.
Change 23.3.9.5 [list.ops], p23:
```
void                          merge(list<T,Allocator>&& x);
template <class Compare> void merge(list<T,Allocator>&& x, Compare comp);
```
Effects: If (&x == this) does nothing; otherwise, merges the two sorted ranges [begin(), end()) and [x.begin(), x.end()). The result is a range in which the elements will be sorted in non-decreasing order according to the ordering defined by comp; that is, for every iterator i, in the range other than the first, the condition comp(*i, *(i - 1) will be false. Pointers and references to the moved elements of x now refer to those same elements but as members of *this. Iterators referring to the moved elements will continue to refer to their elements, but they now behave as iterators into *this, not into x.
Change 23.3.9.5 [list.ops], p26:
```
void reverse();
```
Effects: Reverses the order of the elements in the list. Does not affect the validity of iterators and references.
Change 23.3.9.5 [list.ops], p30:
```
                         void sort();
template <class Compare> void sort(Compare comp);
```
Effects: Sorts the list according to the operator< or a Compare function object. Does not affect the validity of iterators and references.

1207. Underspecified std::list operations?

1207. Underspecified `std::list` operations?