C++Talk.NET

rasmus · Guest

Hi,

I'd like comments and advice on interface of my ternary_tree class.
It's at http://abc.se/~re/code/tst/ - download from Links page.
Current status is that it somewhat mimics Sorted Associative container
(some significant differences though), it passes some tests,
and is about as fast as STLPort hash_map.
There is some documentation, but not full blown (no tutorials;
for usage examples see test_tst.cpp in the zip file).
It is ready for use (or I need more test cases), but I'm a little
unsure which way to go with the interface.

Ternary search trees were described by Bentley and Sedgewick
in DDJ 1994/04, see also http://www.cs.princeton.edu/~rs/strings/
for a more theoretical article and C code sketch.

If you don't know about TST's, it's worth checking out,
as it is useful as a dictionary container.
A TST offers lookup speed similar to hash maps, is sorted,
and allows advanced searches, eg prefix match, neighbour search
(eg for mispelt words), or wildcard search: "b?nd" finds "band",
"bend", "bind", "bond", etc.

There are several issues with my interface wrt standard concepts.
In consequence of the requirement that key type is a Forward Container,
the comparator is applied to key elements, not to the key itself.
(I call it a Structured Container, but that may be an overstatement.)
So this makes the Sorted Associative Container template parameters unsuitable.

The allocator definition and use is probably not quite right.
And the clod of support classes is a little messy.

If someone finds it useful, I'm happy.
Please mail me about bugs, (real address in code and readme file);
please post comments or questions in comp.lang.c++.moderated.
I can bring up more specific questions later if there's any interest in this.

Thanks for any advice,

re

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