"Hi. I'm A Set, Implemented As {BST | AVL | Splay | Red-Black}."

Hi All,

It is common knowledge that set-like containers in STL are implemented
using red-black trees. However, Ben Pfaff showed of Stanford showed
in his paper:

http://www.stanford.edu/~blp/papers/libavl.pdf

....that, not suprisingly, red-black implementations, while good
overall, are not optimal for all situations. Sometimes an AVL
implementation will perform better [input comes in sorted, later
random access], and sometimes regular BST is best [input comes in
randomly].

Faced with implementing your own set-like container, would you:

1. Do what STL did: Pick one, ignore the rest, and get on with it.
2. Create compile-time framework to choose among implementations
according to anticipated use.
3. Create run-time framework to choose among implementations,
according to anticipated use.

I recall somewhere on the WWW an author following #3, but cannot find
the code.

The mechanism I use now to get at various possible implementations is
embarrassing: I prefix Set<> with a namespace for the implementation:
AVL::Set<>. I do have abstract base for all of them, which I use when
only an interface is needed. Yes, I know this is yuck. I would rather
just write Set<>, but then I would have to commit to a specific
implementation unless I use schemes #2 or #3.

What would you do?

-Le Chaud Lapin-

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]