26

The most popular post on C++ Iterator invalidation rules claims that it's not clear if the past-the-end iterators (i.e., those returned by end(), cend(), rend(), and crend()) are invalidated according to the same rules as normal iterators, which point to elements in the container. These claims, made for both 2003 and 2011 C++, defer to a post discussing End iterator invalidation rules, where the accepted answer suggests that the 2003 standard is ambiguous on the matter. This conclusion is based on a comment in 23.1/10 (in the context of swap()) that seems to imply that when the spec does not explicitly mention invalidation of past-the-end iterators, they may be invalidated.

A comment on that post's question (by mike-seymour) suggests that C++11 is unambiguous on this matter, in the case of deques. My question is about all containers:

  • In C++11, are there any container operations that may invalidate a past-the-end iterator, and where this behavior is ambiguous in the language specification?

Said differently,

  • Can I trust the validity of a past-the-end iterator after performing a container operation that does not say it may invalidate the past-the-end iterators?
Community
  • 1
  • 1
nknight
  • 1,034
  • 8
  • 17
  • 8
    You can trust the validity of past-the-end iterator after performing an operation that does not invalidate any iterator. For all other cases, I would not know, I don't really care: reobtain the iterator (which is a constant time operation) and there is no need to worry about whether that particular iterator is invalidated or not... – David Rodríguez - dribeas Jul 05 '12 at 18:40
  • 8
    There are certainly operations that may invalidate an end iterator. `vector::erase`, for example, "invalidates iterators and references at or after the point of erasure." The end iterator is necessarily "after the point of erasure." – James McNellis Jul 05 '12 at 18:41
  • @dribeas: Thanks for your workaround; I'm sure it's optimal in almost every situation, especially given compiler inlining, etc. There is anecdotal evidence (http://stackoverflow.com/q/3084109/985943) that you might get performance benefits from caching the past-the-end pointers; indeed this motivated my question. – nknight Jul 05 '12 at 19:49
  • 1
    @JamesMcNellis: Agreed. The standard is unambiguous here because the end iterator is [defined somewhere to be] after the point of erasure. How about `vector::reserve()`, 23.3.6.3/5 (I have rev. n3337), "Reallocation invalidates all the...iterators referring to the elements in the sequence," and this list does not include the past-the-end iterators, which by definition do not point to elements in the sequence. Yet, the SGI implementation invalidates _all_ iterators, presumably the past-the-end ones too [http://www.sgi.com/tech/stl/Vector.html#5]. More: http://stackoverflow.com/a/1624961/985943 – nknight Jul 05 '12 at 20:12
  • That is assuredly a defect in the C++11 specification. – James McNellis Jul 05 '12 at 20:22

4 Answers4

12

My question is about all containers:

  • In C++11, are there any container operations that may invalidate a past-the-end iterator, and where this behavior is ambiguous in the language specification?

I am not sure what you mean with "where this behavior is ambiguous in the language specification", but there certainly are operations that invalidate past-the-end operators (like insert into a std::vector or std::string).

Said differently,

  • Can I trust the validity of a past-the-end iterator after performing a container operation that does not say it may invalidate the past-the-end iterators?

You can trust the past-the-end iterator like any other iterator: Any operation that does not (potentially) invalidate iterators won't invalidate them. Except for the possibility of the standard sporting a bug, that is all operations where it doesn't say that they (potentially) invalidate operators.

sbi
  • 219,715
  • 46
  • 258
  • 445
  • 1
    What about the quote for `reserve` in the comment-to-the-question: `"Reallocation invalidates all the...iterators referring to the elements in the sequence,"`? Would you say that's definitely a defect in the standard? – Mark B May 10 '13 at 13:25
  • 1
    @Mark: It probably is. Common sense would dictate that for many containers, invalidating iterators into the sequence will necessarily also invalidate the end iterator. (However, I am about as far away from a language lawyer as high-rep C++ tag user come, so take this with a grain of salt.) – sbi May 10 '13 at 22:07
  • Actually cppreference.com does talk about end() iterator's invalidation. See https://stackoverflow.com/a/72624474/199150 (below) – Shriram V Jun 14 '22 at 23:45
  • "past-the-end operators" - mistake? – Кое Кто May 30 '23 at 13:19
2

You should be able to trust it if the standard says the operation will not invalidate iterators. Anything else should be treated as a bug in the standard library implementation.

bstamour
  • 7,746
  • 1
  • 26
  • 39
  • 1
    Personally I agree that a negative answer to my (second) question should mean a bug in the standard. And I agree with your response, but I really was hoping you could show that the inverse to what you said was false. That is, 'You should be able to trust that no iterator, including past-the-end iterators, are invalidated by a container operation if the standard doesn't say they are.' – nknight Jul 05 '12 at 19:45
1

Regarding end iterator's invalidation rules, there is a mention in cppreference.com#Iterator_invalidation.

The relevant lines are:

The past-the-end iterator deserves particular mention. In general this iterator is invalidated as though it were a normal iterator to a non-erased element. So std::set::end is never invalidated, std::unordered_set::end is invalidated only on rehash, std::vector::end is always invalidated (since it is always after the modified elements), and so on.

There is one exception: an erasure which deletes the last element of a std::deque does invalidate the past-the-end iterator, even though it is not an erased element of the container (or an element at all). Combined with the general rules for std::deque iterators, the net result is that the only modifying operation which does not invalidate std::deque::end is an erasure which deletes the first element, but not the last.

Also see a test with std::set's end() - https://godbolt.org/z/5ecdqYod3.

Shriram V
  • 1,500
  • 2
  • 11
  • 20
0

At least in GCC end iterator gets invalidated for std::map:

#include <set>
#include <stdlib.h>
#include <assert.h>
int main() {
  std::set<int> a;
  a.insert(1);
  std::set<int>::reverse_iterator rit(a.rbegin());
  ++rit;
  assert(rit==a.rend());
  a.erase(a.begin());
  assert(a.rend()==rit); // FAIL
}
Jan Kratochvil
  • 387
  • 3
  • 11
  • 2
    Interesting, but flawed. `.rend()` returns an iterator-adaptor. Specifically, the one that adapts `a.begin()`, NOT `a.end()`, so there is no contradiction. `rend()` by definition adapts `begin()` and that iterator was invalidated, explicitly by the `erase`. – sehe Mar 03 '20 at 08:39
  • Counter example to demonstrate the point: http://coliru.stacked-crooked.com/a/8a195ac32db336f2. Same goes for regular iterators http://coliru.stacked-crooked.com/a/6e80855c3b88422a and even in the case of removing the single element: http://coliru.stacked-crooked.com/a/e06c5188e46d52b6 like your original example – sehe Mar 03 '20 at 08:44