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.