C++ augmenting an STL data structure

Question

My requirement is to be able to quickly retrieve a minimum and maximum value in a tree. (Note, not the minimum/maximum key, but min/max of the satellite data).

The tree would be based on strings as keys and each node would store an integer with it. This integer bound to change and be constantly updated. Keys remain fixed

I was considering using an approach described here of augmenting a red black tree, so that every node stores the maximum ( max of left's max and right's max and itself) similar for minimum.

So when I update a node, I would simply update the min/max of every node which was traversed to reach my current node.

What would be the best approach to avoid rewriting the STL implementation of red/black tree.

Answer 1

You can't use an STL container (e.g. set, which doesn't technically even need to me a BST as far as I know), as it doesn't provide you with access to the underlying structure.

Your options are:

• As you already mentioned, writing your own BST.

• Simply using a secondary BST (or heap) which is ordered by your integer value.

• Using Boost's multi_index_container.