51. Requirement to not invalidate iterators missing

Section: 26.2 [container.requirements] Status: TC1 Submitter: David Vandevoorde Opened: 1998-06-23 Last modified: 2016-02-10

Priority: Not Prioritized

View all other issues in [container.requirements].

View all issues with TC1 status.

Discussion:

The std::sort algorithm can in general only sort a given sequence by moving around values. The list<>::sort() member on the other hand could move around values or just update internal pointers. Either method can leave iterators into the list<> dereferencable, but they would point to different things.

Does the FDIS mandate anywhere which method should be used for list<>::sort()?

Matt Austern comments:

I think you've found an omission in the standard.

The library working group discussed this point, and there was supposed to be a general requirement saying that list, set, map, multiset, and multimap may not invalidate iterators, or change the values that iterators point to, except when an operation does it explicitly. So, for example, insert() doesn't invalidate any iterators and erase() and remove() only invalidate iterators pointing to the elements that are being erased.

I looked for that general requirement in the FDIS, and, while I found a limited form of it for the sorted associative containers, I didn't find it for list. It looks like it just got omitted.

The intention, though, is that list<>::sort does not invalidate any iterators and does not change the values that any iterator points to. There would be no reason to have the member function otherwise.

Proposed resolution:

Add a new paragraph at the end of 23.1:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

Rationale:

This was US issue CD2-23-011; it was accepted in London but the change was not made due to an editing oversight. The wording in the proposed resolution below is somewhat updated from CD2-23-011, particularly the addition of the phrase "or change the values of"