Thread: What exactly is iterator returned by .end()?

If vector is empty, then an invalid iterator is returned.
If vector is not empty, then it points to end + 1.
(This was observed in Microsoft's implementation.)
But regardless of how end() is implemented, adding something to the vector invalidates the iterators.

Well, invalid or not can be speculated, but I know that it returned NULL when it was empty, and so likely would begin, from what I observed. So I suppose it can be said that it is a valid iterator, but begin == end.

Originally Posted by pheres

What does the standard say? Does the answer depend on the container typ?

EVOEx is correct. Concerning all standard containers:

Originally Posted by C++ Standard, 2003 Edition, Section 23.1, Paragraph 7

begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value for the container. If the container is empty, then begin() == end();

As such, returning a null pointer when the container is empty would satisfy the requirements for begin() and end(), but the standard does not mandate that a null pointer be returned when the container is empty. (Oh yes, and I forgot that in the first place, iterators are a generalisation of pointers, so the standard could not mandate that null pointers be returned anyway.)

EDIT:
To address the point on whether the assert would fail: it is obvious that the assert should fail since the previous end of the vector cannot be equal to the current end of the vector when the vector's size changes.

Concerning invalidation of iterators: EVOEx is again correct to say that whether adding an element to a container invalidates iterators depends on the container. In the case of a vector, it also depends on whether reallocation occurs, so it is not absolutely true to say that "adding something to the vector invalidates the iterators".

Originally Posted by pheres

So looking at my peace of code that means that the push_back() will not invalidate iter, iter is still required to point to end() and the assert will pass?

may pass - it depends on how the storage is implemented. in a vector, for example, it may return the address of element(size+1).

--
Mats

Obviously the end of the vector is not the same after the push_back, so that assertion should never pass.

Originally Posted by anon

Obviously the end of the vector is not the same after the push_back, so that assertion should never pass.

However, in a linked list, the end() may be NULL (or some other sentinel value), which is always the same value - so there's no guarantee that it actually changes the value of end.

For a vector, I agree, it's unlikely to fail - but replace it with the "right" container class, and it may do.

--
Mats

Originally Posted by matsp

may pass - it depends on how the storage is implemented. in a vector, for example, it may return the address of element(size+1).

No, as I pointed out, and which anon has confirmed, it is clear that the assertion must fail, otherwise there is a bug in the standard library implementation.

Originally Posted by matsp

However, in a linked list, the end() may be NULL (or some other sentinel value), which is always the same value - so there's no guarantee that it actually changes the value of end.

That is true, but pheres' example is for vector.

Code:

#include <vector>
#include <iostream>

using namespace std;

int main()
{
	vector<int> v;
	v.push_back(1);
	vector<int>::iterator end = v.end();
	v.push_back(2);
	vector<int>::iterator it;
	for (it = v.begin(); it != end ; it++)
		cout << *it;
}

Output:
Well, nothing.
Visual Studio pops up a nasty dialog says "vector iterators incompatible."
So don't count on doing something like this. When you add or delete from a vector, assume that the iterators are invalidated.

Originally Posted by Elysia

When you add or delete from a vector, assume that the iterators are invalidated.

Unless you specifically reserve to prevent reallocation, e.g.,

Code:

#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> v;
    v.reserve(2);
    v.push_back(1);
    vector<int>::iterator end = v.end();
    v.push_back(2);
    vector<int>::iterator it;

    for (it = v.begin(); it != end ; it++)
        cout << *it;
}

Actually, thinking about matsp's claim that the assertion may pass for vector... If the capacity is enough, the iterator returned by end() for the empty container could point to the same position as the iterator returned by end() for the container with one element. It would still satisfy the requirements as long as begin() pointed to the same place... however, the flaw could be that begin() might not be allowed to point to the same place since it would be invalidated despite the fact that reallocation does not occur.