Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-01-14 12:51:10

Steven Ross wrote:
> algorithm_sorting.tar.gz is now in the boost vault, and is formatted for
> submission.
> I'd appreciate it if people could test it on their compiler and give me some
> feedback.

Seems to be here:
http://www.boostpro.com/vault/index.php?action=downloadfile&filename=algorithm_sorting.tar.gz&directory=&

Some first impressions follow.  I will try to find time to look at it 
more carefully at some point but I can't promise.

You seem to have quite a lot of code that's duplicated for the functor 
and non-function versions.  Can't this be eliminated by using e.g. 
std::less as a default for the compare template parameter?  (Isn't this 
what std::sort does?)

I suggest that you get rid of the tab characters in the source.  I 
personally find your lines rather long, but that's a matter of taste.

It would be good if it were possible to automatically detect whether a 
floating point type is one for which the cast-to-integer trick works.  
It would be great if C++ defined some macro or similar that defined 
whether float and double were IEEE 754 or not.  (Hmm, is there some 
sort of type_traits thing to do this?).  Maybe it's possible to get a 
"good guess" answer by checking whether the bit pattern is as expected 
for some known constant; would someone like to suggest a good way to 
check this at compile time?  You could then fall back to std::sort if 
it fails.

I think you can use things like typename RandomAccessIter::value_type 
instead of passing *first in order to determine data_type.

I'm not sure how useful your functor-versions are since they still seem 
to depend on the "integer-ness" or "float-ness" of the sorted type.  
Apart from sorting backwards, what use cases are there?  Using functors 
would be more useful if it let you sort types that are neither integers 
nor floats; for example, fixed-point types or pointers-to-integers or 
structs containing a key field to be sorted on.  I think that the key 
here is that you make assumptions about the return type of operator>> 
or the right_shift functor which are not true in those cases.  It may 
be that you just need to rename that functor and document what it needs 
to do.  I think it's really "get N bits from key".  I would have 
thought that the floating-point algorithm would just be an instance of 
the generic algorithm with custom functors, with a bit of 
specialisation to cope with the reverse-order-for-negatives thing.

One of the things that your string sort does is to not compare 
known-equal initial substrings.  Does anyone know if there is a variant 
of a conventional sort (e.g. quicksort) that does this?

Some more documentation of the performance benefit would be useful.  
How about some graphs?

Cheers,  Phil.