How is end() implemented in STL containers?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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();

Answer 4

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

Answer 5

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.