Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk