This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of C++11 status.

### 1207. Underspecified `std::list` operations?

Section: 22.3.10.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: ]

> 22.2.1 [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 22.3.10.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:

1. Change 99 [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.

2. Change 99 [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.

3. Change 99 [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`.

4. Change 99 [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.

5. Change 99 [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.

6. Change 22.3.10.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.

7. Change 22.3.10.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.

8. Change 22.3.10.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`.

9. Change 22.3.10.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.

10. Change 22.3.10.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.