BST implementations in STL

Question

C++ STL "set" and "map" support logarthmic worst case time for insert, erase, and find operations. Consequently underlying implementation is Binary search tree. An important issue in implementing set and map is providing support for iterator class. Ofcourse, internally the iterator maintains a pointer to the "current" node in the iterator . The hard point is efficiently advancing to next node.

My question are

1. if "set" and "map" implements binary search tree how we advance to next node using iterator class i.e., what we return ++ or -- i.e., is it left subtree or right subtree?

2. In general how most of the STL implementaions BST and how ++ or -- of iterator is implemented?

Thanks!

Answer 1

1. There is nothing in the C++ specification that requires the use of a binary tree. Because of this, ++ and -- are defined in terms of the sequence of elements. map and set store an ordered sequence of elements. Therefore, ++ will go to the next element, and -- will go to the previous element. The next and previous elements are defined by the order of the elements.

   Note that while the C++ specification doesn't require the use of a binary tree, the particular performance requirements pretty much force some use of a binary tree.

2. Generally, they use some from of Red/Black self-balancing binary tree.

Answer 2

It mostly depends on the particular implementation. One way (my description only: not necessarily the one you have) can be the following:

a node has 3 pointers: a left, a right and an up one. what ++ does is:

• if there is "right", go right than go deepest left as possible.
• Otherwise go up until we came from the right, and up once again.

what -- does its exactly the inverse.