765. More on iterator validity

Section: 24.3.4 [iterator.concepts] Status: C++11 Submitter: Martin Sebor Opened: 2007-12-14 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [iterator.concepts].

View all issues with C++11 status.

Discussion:

Issue 278 defines the meaning of the term "invalid iterator" as one that may be singular.

Consider the following code: 

   std::deque<int> x, y;
   std::deque<int>::iterator i = x.end(), j = y.end();
   x.swap(y);

Given that swap() is required not to invalidate iterators and using the definition above, what should be the expected result of comparing i and j to x.end() and y.end(), respectively, after the swap()?

I.e., is the expression below required to evaluate to true? 

   i == y.end() && j == x.end()

(There are at least two implementations where the expression returns false.)

More generally, is the definition introduced in issue 278 meant to make any guarantees about whether iterators actually point to the same elements or be associated with the same containers after a non-invalidating operation as they did before?

Here's a motivating example intended to demonstrate the importance of the question: 

   Container x, y ({ 1, 2});   // pseudocode to initialize y with { 1, 2 }
   Container::iterator i = y.begin() + 1;
   Container::iterator j = y.end();
   std::swap(x, y);
   std::find(i, j, 3);

swap() guarantees that i and j continue to be valid. Unless the spec says that even though they are valid they may no longer denote a valid range the code above must be well-defined. Expert opinions on this differ as does the behavior of popular implementations for some standard Containers.

[ San Francisco: ]

Pablo: add a note to the last bullet of paragraph 11 of 23.1.1 clarifying that the end() iterator doesn't refer to an element and that it can therefore be invalidated.

Proposed wording:

[Note: The end() iterator does not refer to any element and can therefore be invalidated. -- end note]

Howard will add this proposed wording to the issue and then move it to Review.

[ Post Summit: ]

Lawrence: suggestion: "Note: The end() iterator does not refer to any element"

Walter: "Note: The end() iterator can nevertheless be invalidated, because it does not refer to any element."

Nick: "The end() iterator does not refer to any element. It is therefore subject to being invalidated."

Consensus: go with Nick

With that update, Recommend Tentatively Ready.

Proposed resolution:

Add to 23.2.2 [container.requirements.general], p11:

Unless otherwise specified (see 23.1.4.1, 23.1.5.1, 23.2.2.3, and 23.2.6.4) all container types defined in this Clause meet the following additional requirements: