How STL ordered containers know their end?

Question

I know that the standard doesn't dictate the way that STL containers must be implemented, but rather it mandates a set of requirements for each one of them.

However, it is widely known that STL ordered containers are usually implemented as red–black trees.

You can iterate through the elements of a std::set or a std::map using their respective iterators, or since C++11 using ranged loops.

What puzzles me however, is how an ordered container in STL "knows" its "end". Or put it another way, since they're implemented as trees, how the end of the container is implemented or could it be implemented?

I know that the standard dictates §23.2.1/c General container requirements (Emphasis Mine):

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

OK, for contiguous containers this is easy, but how this "past-the-end" could be materialized for trees?

Answer 1

I have just inspected the implementation of map container in Visual Studio 2013 STL, and here is how end is implemented. When map is constructed, a head element of the RB tree is allocated and this element is declared to be the end of the container.

When you traverse the container via a valid iterator, operator++ and operator-- simply skip the head element. And when you reach the last element of the tree and increment an iterator, it climbs upwards (looking for a right subtree) and eventually reaches the head of the tree, which is end.