So when we need to traverse a container from start to end we write something like
for (i = v->begin(); i != v->end(); i++)
assuming i is an iterator for container v.
My question is "what guarantees that end will always point to one past the last element in container?" How does STL ensures this behavior and is there any chance that this case is not true?
STL ensures this behavior by always storing stuff like this:
In the end (pun), it doesn't matter what end() is, as long as it's always end() (and, obviously, can't be confused with any other node).
C++03 Section 23.1/7 says
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();
The stl specification guarantees that end will be one past the end See here. That will always be the case. Exactly how it does this can depend on the implementation (sometimes the values is just set to null for example), but rest assured your loop will be OK as long as v is a valid pointer.
"end will always point to one past the last element in container" means that if you increment iterator that points to the last element it will be equal to the result of end(). Implementation can be different. In Visual C++ std::vector::end() returns implementation specific iterator that holds zero pointer.
std::vector<T>::iterator is a random-access iterator. If std::vector<T>::end() returned (T*)0, end()-begin() would be illegal, yet it needs to return std::vector::size()
end returns implementation specific iterator that holds zero pointer.
vector<>::end() is defined as vector<>::begin()+vector<>::size(), and is actually stored in the vector<> object (GCC vector is implemented by means of three pointers: begin, end and end_of_capacity, where begin==end if the vector is empty, begin+size()==end at all times and end==end_of_capacity if size()==capacity(). There are no zero pointer anywhere to be seen.You're asking about all STL containers... not a word of mention of vector specifically where end() might be implemented as you obviously intuitively expect. What's one past the end in a std::map<>? The "end is one past the last used node" thing is just a logical concept, expressing that you can safely increment from that last-used node, differentiate/equate it from/to the abstract concept of "end", and do some node arithmetic where end is considered to be one further along than the last-used node. Don't take it too literally.
As some of the previous posters have stated end() is one past the end element. If you need to access the last element via iterators use iter = container.end() - 1; Otherwise, in the case of vectors, variable = someVector.back(); Assuming that variable is of the data type someVector contains.
In regard to what guarantees that it points to the end, the container itself handles that internally. You just have to treat it like a blackbox like any other object and trust it does it correctly.
Whenever the container is resized, it will track where the end is and will be up to date before you access end() again. Depending on the container however, if you have an iterator and alter it in some ways, it can invalidate the iterator and break your iteration process.
v->end()at each turn of the loop certainly is less efficient...for (auto it = v.begin(), end = v.end(); it != end; ++it)is the canonical form, though in C++0x one might as well usefor (auto val : v)orstd::foreachand a lambda function.