9

According to the C++ standard, calling push_back() on a vector invalidates the iterator if the new size of the vector grows above its capacity, but on a list it never invalidates iterators. Now consider the following code snippets:

1.

vector<int> v{1,2,3};
v.reserve(100);
for (int i: v) {
    v.push_back(i);
}

2.

list<int> l{1,2,3};
for (int i: l) {
    l.push_back(i);
}

I tried it with gcc 4.8 and found that code 1 finishes with v being {1,2,3,1,2,3}, but code 2 runs into an infinite loop. The explanation seems pretty simple to me: the end() iterator of vector points to a memory location, and since it is only evaluated once during a range based for loop, it stops when it reaches past the 3rd element of the vector. On the other hand, list probably has some kind of null token as an end iterator, which is always placed after the last element, thus the loop will never reach it.

While the results seem straightforward, my question is what does the standard say about this? Is it supposed to be so in every standard library implementations, or is this behavior not defined? What should I expect when writing a loop that may call push_back() to such a container (which I usually like to avoid anyway)?

5
  • I guess the Standard does not have much to say about this. It is allowed, it is legal, it is just an infinite loop Commented Jul 5, 2013 at 16:57
  • @AndyProwl I think the standard does have something to say: it is required to be an endless loop. (If it isn't an endless loop with vector, it is because there is undefined behavior, so anything the implementation does is legal.) Commented Jul 5, 2013 at 17:06
  • @JamesKanze: Well, that's the same I meant to say. The OP wrote a legal infinite loop, there's nothing the standard has to say about that particular situation (talking about the list example of course). Commented Jul 5, 2013 at 17:07
  • 3
    For reference, §23.3.6.5/1: "Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid." Commented Jul 5, 2013 at 17:32
  • @Xeo thanks, that's the answer I was looking for. Commented Jul 5, 2013 at 17:38

1 Answer 1

5

I don't think that the standard is very explicit, but in general, end means end, and if you insert elements beyond the current position in a loop, you'll never get there.

Of course, your first loop, with vector, has undefined behavior, since insert (and erase) invalidates all iterators at or beyond the position of the insertion, even if there is no reallocation. And the end iterator will always be beyond the point of insertion.

Sign up to request clarification or add additional context in comments.

8 Comments

According to cppreference.com, iterators in vector are only invalidated if the size grouws through capacity. en.cppreference.com/w/cpp/container/vector/push_back Does this reflect the standard correctly, or does it say that they can be invalidated at any call to push_back?
@petersohn: Cppreference literally says "...Otherwise no iterators and references are invalidated." This is patently wrong. From the purely "physical" point of view one can understand their logic, but the language spec takes a more high-level approach. All iterators and references that refer to "shifted" elements are considered invalidated, even though they might still refer to valid memory locations.
@petersohn According the the standard (§23.3.6.5): "[...] If no reallocation happens, all the iterators and references before the insertion point remain valid." (If they aren't guaranteed to remain valid, they are invalid. This is a blatant error at the site you quote.
@AndreyT All iterators which no longer point to the element they previously pointed to are considered invalid. (It's highly likely that in std::vector, an iterator after the insertion will point to the element in front of the one it previously pointed to if no allocation occurs, but the standard doesn't try to standardize such "accidental" behavior.)
@AndreyT and @James Kanze: the cppreference docs for std::vector::push_back should be better now.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.