CODEWITHSUNDEEP
c++c++11stlstdmapstdset
Dimitrios Bouzas
Dimitrios Bouzas

Reputation: 42929

How STL ordered containers know their end?

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?

Upvotes: 16

Views: 341

Answers (2)

AlexStepanov
AlexStepanov

Reputation: 481

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.

Upvotes: 9

Billy ONeal
Billy ONeal

Reputation: 106609

All of the "list-like" containers like this need to have some kind of sentinel node for the end, because the user can get end(), insert something into the container, decrement the iterator, and the decremented end() must point to that inserted element. My understanding is that some implementations will dynamically allocate for this, and some will put the dynamic sentinel node inside the container itself.

Upvotes: 3

Related Questions