On 3/22/07, Corrado Zoccolo <czoccolo@gmail.com> wrote:
A trie data structure (http://en.wikipedia.org/wiki/Trie 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@gmail.com> wrote:
On 3/21/07, Corrado Zoccolo <czoccolo@gmail.com> 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 --
I think that the problem you are getting at is the type of tree created by msd radix sort, which creates a bin for each possible byte value and then puts corresponding bytes in the correct bin. However, that is not implemented because for arrays of independent items, msd radix sort is much less effecient than LSD radix sort. For arrays of arrays, multikey and radix quicksort are faster than MSD sort because they avoid the problem of empty bins.