16

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?

101010
  • 41,839
  • 11
  • 94
  • 168
  • 6
    Realize that "past-the-end" is a logical concept, not a physical one. It literally means the iterator you get when you advance past the last valid entry, but the internal contents of that iterator could be anything. – Mark Ransom Nov 11 '15 at 16:30
  • 1
    There is a natural notion of next() and end() from terminating tree traversals like breadth-first and depth-first, thus there is nothing conceptually special about respective iterators. – decltype_auto Nov 11 '15 at 16:48
  • @MarkRansom Fair enough, it's a logical concept. But how you implement such a logical concept? I mean in code. – 101010 Nov 11 '15 at 21:24
  • I guess my point was that it's completely arbitrary. Depending on the exact implementation of the tree there may be a natural and obvious way of doing it, but I suspect you'll find as many different ways of doing it as there are implementations of the standard library. – Mark Ransom Nov 11 '15 at 21:39

2 Answers2

9

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.

AlexStepanov
  • 451
  • 3
  • 13
3

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.

Billy ONeal
  • 104,103
  • 58
  • 317
  • 552
  • I'm unable to find a place in the standard that implies that `std::map::end()` or `std::set::end()` must return a decrementable iterator. What you are saying is true for `basic_string`, `array`, `deque`, `list` and `vector`, but the OP asked about `set` and `map`. – Андрей Беньковский Nov 11 '15 at 16:54
  • @АндрейБеньковский: N4527 23.2.1 [container.requirements.general]/12: Unless otherwise specified [...]invoking a container member function [...] shall not invalidate iterators to, or change the values of, objects within that container. -- and map::insert does not explicitly state otherwise. 23.2.4 [associative.reqmts]/9: The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements. – Billy ONeal Nov 11 '15 at 17:01
  • @АндрейБеньковский: In particular, it is *NOT* true for `basic_string`, `deque`, or `vector` -- in those cases if a reallocation is triggered by the insert iterators and references are invalidated. And you can't insert into an `array` so that's not really relevant here. – Billy ONeal Nov 11 '15 at 17:02