CODEWITHSUNDEEP
c++stl
venkysmarty
venkysmarty

Reputation: 11431

BST implementations in STL

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!

Upvotes: 3

Views: 2606

Answers (3)

Eugen Constantin Dinca
Eugen Constantin Dinca

Reputation: 9150

Besides the worst case operational complexities both map & set (and all Orderer/Sorted Associative Containers in the C++ Standard Library) have a very important property: their elements are always sorted in order by key (according to a comparator).
A self-balancing binary search tree satisfies the operational complexities and the only traversal that will give you the elements in sorted order is, you've guessed it, the in-order one.
Nicol Bolas' answer gives you more details about the usual implementation. If you're curios to actually see such an implementation, you can take a gander at the RDE STL implementation. It's a lot easier to read than what you'll find in your average C++ Standard Library implementation. As a side note, both set & map implementations in RDESTL have only forward iterator (not bidirectional as the standard says) but it should be pretty easy to figure out the -- part.

Upvotes: 0

Emilio Garavaglia
Emilio Garavaglia

Reputation: 20739

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.

Upvotes: 1

Nicol Bolas
Nicol Bolas

Reputation: 473856

  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.

Upvotes: 6

Related Questions