3

We can see from several sources that std::map is implemented using a red-black tree. It is my understanding that these types of data structures do not hold their elements in any particular order and just maintain the BST property and the height balancing requirements.

So, how is it that map::begin is constant time, and we are able to iterate over an ordered sequence?

Steve M
  • 9,296
  • 11
  • 49
  • 98
  • http://stackoverflow.com/a/7648812/3651800 – Matt Coubrough Dec 03 '14 at 03:58
  • @Matt Courbrough That says that std::map is guaranteed to be sorted, not how it is achieved using a red-black tree. – Steve M Dec 03 '14 at 04:01
  • Might have misunderstood your question, but those answers state the comparison function used for ordering. – Matt Coubrough Dec 03 '14 at 04:03
  • DietrichEpp's answer covers the sorting aspects. Regarding "So, how is it that `map::begin` is constant time" - rather than descend through the tree when `begin` is called (with would be O(log2N)), the implementation tracks (its choice of pointer or iterator internally - probably the same thing in the end anyway - but `begin` itself will obviously return an iterator) the lowest-value node currently in the tree, updating that if necessary after an `erase`, `insert` etc. - so it can be provided in constant time. The last node will be tracked similarly (for `rbegin()`). – Tony Delroy Dec 03 '14 at 04:09
  • @Tony D That makes sense for the begin iterator. I'm guessing it must be doing something like doing the traversal and sorting it at some point to get the rest of the sequence? – Steve M Dec 03 '14 at 04:15

3 Answers3

4

Starting from the premise that std::map is maintaining a BST internally (which is not strictly required by the standard, but most libraries probably do that, like a red-black tree).

In a BST, to find the smallest element, you would just follow the left branches until you reach a leaf, which is O(log(N)). However, if you want to deliver the "begin()" iterator in constant time, it is quite simple to just keep track, internally, of the smallest element. Every time an insertion causes the smallest element to change, you update it, that's all. It's memory overhead, of course, but that's a trade-off.

There are possibly other ways to single out the smallest element (like keeping the root node unbalanced on purpose). Either way, it's not hard to do.

To iterate through the "ordered" sequence, you simply have to do an in-order traversal of the tree. Starting from the left-most leaf node, you go (up), (right), (up, up), (right), ... so on.. it's a simple set of rules and it's easy to implement, just see a quick implementation of a simple BST inorder iterator that I wrote a while back. As you do the in-order traversal, you will visit every node from the smallest to the biggest, in the correct order. In other words, it just gives you the illusion that "array" is sorted, but in reality, it's the traversal that makes it look like it's sorted.

Mikael Persson
  • 18,174
  • 6
  • 36
  • 52
  • 1
    Thank you, I was missing the piece of the inorder traversal yielding the sorted order. – Steve M Dec 03 '14 at 04:24
  • @SteveM On a side note, containers like `std::map` are not really good at iterating. The logic of the tree-traversal, plus the fact that you jump around in memory all the time, make the performance quite poor in practice. So, consider them for "mainly look-ups, occasional ordered traversals" or for things like looking up ranges of values. For fast traversals, you're typically better off maintaining a sorted `std::vector`. [My diagram](http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container/22671607#22671607) mentions that. – Mikael Persson Dec 03 '14 at 04:33
2

The balancing properties of a red-black tree allow you to insert a node, anywhere in the tree, at O(log N) cost. For typical std::map implementations, the container will keep the tree sorted, and whenever you insert a new node, insert it into the correct location to keep the tree sorted, and then rebalance the tree to maintain the red-black property.

So no, red-black trees are not inherently sorted.

Dietrich Epp
  • 205,541
  • 37
  • 345
  • 415
0

RB trees are binary search trees. Binary search trees don't necessarily store their elements in any particular order, but you can always get an inorder traversal. I'm not sure how map::begin guarantees constant time, I'd assume this involves always remembering the path to the smallest element (normally it'd be O(log(n))).

Cubic
  • 14,902
  • 5
  • 47
  • 92