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.

@Pheres: What are you actually trying to achieve? Check that something got added? If so, why not take the size() of the vector, and compare it later on?

--
Mats

Quote:

---

Originally Posted by Elysia

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.

---

Just out of curiosity, why are the iterators incompatible?

Quote:

---

Originally Posted by C_ntua

Just out of curiosity, why are the iterators incompatible?

---

Since reallocation presumably occurred, the underlying pointers do not point to somewhere in the same dynamically allocated array (or one past the end), hence they cannot be validly compared.

EDIT:
No, I recall wrongly: pointers that point to elements from different arrays cannot be validly subtracted, but there is no restriction on comparison. On the other hand, since we are talking about iterators, the fact that the underlying array is different could be sufficient for us to call the iterators incompatible by definition.

Quote:

---

Originally Posted by matsp

@Pheres: What are you actually trying to achieve? Check that something got added? If so, why not take the size() of the vector, and compare it later on?

--
Mats

---

I've some list (not vector in my case) of objects and 2 free iterators which mark begin and end of a range of objects which shall asynchronously (to the computation of the two iterators) be processed in the next slice of time.
Also asynchronously objects can be added as well as removed, so the iterators have to be recomputed in this case to keep the system stable.
Thats why I wanted to know if I have to check if an iterator coincidentaly pointing to end() has to be recomputed after adding objects (to the end if the list) or not.

Quote:

---

Originally Posted by pheres

Thats why I wanted to know if I have to check if an iterator coincidentaly pointing to end() has to be recomputed after adding objects (to the end if the list) or not.

---

Adding elements to a std::list does not invalidate existing iterators. Erasing elements from a std::list only invalidates iterators to the erased elements. Unfortunately, I am not sure what exactly is the definition of a "valid iterator". Clearly, an iterator that refers to an existing element is valid, but I am not sure if a past-the-end iterator is considered valid.

Am I right in thinking that there is two (or more) threads potentially accessing the same container at the same? That seems like a VERY BAD IDEA(tm).

There is nothing in the standard that guarantees that the STL containers are in the least way thread-safe. You may be operating on elements in a vector, and all of a sudden the vector is being re-arranged and the elements are now in a completely different place. Linked lists are equally dodgy - you may be going to the next element, which is currently being deleted by the other thread (or an element inserted in front of).

Your are playing with matches and petrol - it's going to burn you sooner or later.

--
Mats

the list access is synchronized while receiving references to it's elements or computation of the iterators or adding/removing elements and only unlocked while processing the received elements. this is just the normal thread pool pattern with nothing very special about it. i tested it on multicore machine under heavy load. the synch should be ok.
I only thought about saving the check for the iterator returned by .end() as a special case