Re: "Hi. I'm A Set, Implemented As {BST | AVL | Splay | Red-Black}."
On 2008-08-31 10:55, Le Chaud Lapin wrote:
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.
I have not studies the subject in great detail so the following might
not be entirely correct, and there might be ways to solve some of the
issues I see with more advanced template programming or using C++0x
features.
I can see advantages of all three options, #1 has the advantage of being
simple and easy to use for less knowledgeable users. On the other hand
the same effect be be achieved by using default arguments in #2 and #3.
#2 would be a small extension of the approach taken by STL, where the
tree-implementation is an additional template-parameter. The drawback of
this would be that Set<int, AVLTree> and Set<int, RBTree> would be
different types and you would either have to parameterise functions that
can expect to handle both types. Or you could use a common interface
which they all inherit from, but then you will have problems using the
container with anything except references/pointers.
#3 is nice because you can create a Tree-interface which your RB, AVL,
BST, etc. implements and then use something similar to PIMPL. I'm not
sure that there's a way to make creating such a container look nice
unless you want the default implementation since it will probably
involve passing a pointer to the tree-object, but there might be a way
to work around that.
--
Erik Wikstr??m
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]