Boost logo

Boost :

From: Corrado Zoccolo (czoccolo_at_[hidden])
Date: 2007-03-22 16:09:04

A trie data structure ( where the
similarity with radix_sort is also drawn) is an associative data
structure where the key is a (possibly of arbitrary lenght) sequence
of fixed size objects (e.g. chars or ints). It is typically used to
store strings, but as you extended the radixsort to operate on almost
generic classes, the same can be achieved for trie.

What I'm sayng is that if a class satisfies the requirement to be
processed by radix_sort (let's say it defines an operator[] returning
unsigned char), then that class can also be used as a key for a trie,
so it is sound (and useful) for a library to provide both sorting and
trie based implementations of set and map, for the classes that model
the concept.

On 3/22/07, Sam Schetterer <samthecppman_at_[hidden]> wrote:
> On 3/21/07, Corrado Zoccolo <czoccolo_at_[hidden]> wrote:
> >
> > Hi Sam,
> > I see sorting problems and sorted data structures as two faces of the
> > same medal.
> > In STL, for example, we have std::sort and std::set that both work
> > with a two way comparison functor (std::less).
> > I see a great potential in your work on operator[] with trie data
> > structures.
> > I think that an organic proposal of radix_sort with trie data
> > structures (mimicking std::set and std::map), that both use the same
> > operator[] approach would be very interesting.
> >
> > Corrado
> > --
> What do you mean when you say that? Do you mean that data would first be
> sorted by element value, and then all equal elements would be sorted by key?
> I am not sure that I understand what you are getting at, but the basic idea
> sounds pretty good.
> _______________________________________________
> Unsubscribe & other changes:

dott. Corrado Zoccolo                          mailto:zoccolo_at_[hidden]
PhD - Department of Computer Science - University of Pisa, Italy
The self-confidence of a warrior is not the self-confidence of the average
man. The average man seeks certainty in the eyes of the onlooker and calls
that self-confidence. The warrior seeks impeccability in his own eyes and
calls that humbleness.
                               Tales of Power - C. Castaneda

Boost list run by bdawes at, gregod at, cpdaniel at, john at