What exactly is iterator returned by .end()?

Hi,

does the standard define what the iterator returned by container.end() points to?

Or the question represented in code:

Code:

---

vector<int> v;
vector<int>::iterator iter = v.end();
v.push_back(1);

assert( iter == v.end() ); //?

---

I see two possibilities:
1. iterator returned by container.end() is implemented as a special marker element which is always the same. in this case the assert should not fail
2. iterator returned by container.end() is dynamically derived from the last element of the container. in this case the assert should maybe fail

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

Thank you in advance!

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.

Quote:

---

Originally Posted by Elysia

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.

---

Actually, I'm pretty sure a valid end iterator is always returned. begin() returns an iterator to the first element, while end() an iterator to the item past the last element. If a vector is empty, then begin() == end().
It is true that adding something to a vector invalidates iterators. Not for all types though. For a set, if I am not mistaken, the iterators won't be invalidated. (I know this wasn't part of the question, but an in my opinion significant addition anyway).

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.

It returns an iterator situated one element beyond the last.
If there is no last element that is an undefined position, therefore it cannot return an iterator and returns 0.

If the vector is empty, begin() should return 0 as well, simply because there is no first element to refer to.
Begin would be end only in result, still not in principle as the first element can never be one element past the last element even if both elements are undefined.

Quote:

---

Originally Posted by pheres

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

---

EVOEx is correct. Concerning all standard containers:

Quote:

---

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

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?

Quote:

---

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.

Quote:

---

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

Quote:

---

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.

Quote:

---

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:

---

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;

---

Well try the above. If you get 1 then the iterator doesn't change (which should be the case). If you get 12 then that means that the iterator always points the end of the vector (which shouldn't be true)

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.

I see. So the iterator returned by .end() is no special case regarding invalidation rules.
Thank you all!

Quote:

---

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.