Title
More on iterator validity
Status
c++11
Section
[iterator.concepts]
Submitter
Martin Sebor

Created on 2007-12-14.00:00:00 last changed 153 months ago

Messages

Date: 2010-10-21.18:28:33

Proposed resolution:

Add to [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:

  • ...
  • no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [Note: The end() iterator does not refer to any element. It is therefore subject to being invalidated. — end note]
Date: 2010-10-21.18:28:33

[ 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.

Date: 2010-10-21.18:28:33

[ 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.

Date: 2007-12-14.00:00:00

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.

History
Date User Action Args
2011-08-23 20:07:26adminsetstatus: wp -> c++11
2010-10-21 18:28:33adminsetmessages: + msg3700
2010-10-21 18:28:33adminsetmessages: + msg3699
2010-10-21 18:28:33adminsetmessages: + msg3698
2007-12-14 00:00:00admincreate