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 17:48:29

Steven Ross wrote:
>> 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?)
>
> In the version of STL I downloaded to look at, there is the functor version
> of std::sort, and the non-functor version.  The code is entirely duplicated
> at all levels where comparison are used, because the functor adds overhead
> (it takes up space on the stack, if nothing else).  This overhead is small
> (around 2-5%), but measurable.

OK.

I would hope that a class with no state in it would take no space, but 
I suppose compilers may be dumb about that sometimes.

> My philosophy is that I (as the
> library developer) go to the effort to make things as fast and flexible as
> possible, so that those who include the library don't have to worry about
> any of that.

That's a good attitude, but there's also the "library reviewer" to 
factor in :-)

>> I think you can use things like typename RandomAccessIter::value_type
>> instead of passing *first in order to determine data_type.
>
> I tried that, but it didn't compile on my system (MacOSX PPC gcc4.0.1).

That's surprising.  Maybe you could distil it down to a minimal example 
and we can all scratch our heads over it.

>> 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.
>
> Did you look at my KeyPlusData sample or the index.html?

Ah sorry, I didn't find index.html; I found README and assumed that was 
the limit of the documentation...

> That's what the functor versions are there for: sorting classes or
> structures based upon a key.  All you have to do is define the correct
> functor.

I still believe that "rightshift" is the wrong name for this functor in 
these cases.

> Fixed-point types can sort as an integer of the same size in bytes.  The
> only real requirement is that they must return a data type that when
> subtracted from an item of the same type returns something convertible to a
> size_t, that if (b - a) < (c - a) then b < c, and that bitshifting works as
> division by a power of two would, reducing the difference by a power of two
> per shift.

Can you clarify that a bit?  Say I have this:

class fixed {
   ....
   some_integer_type impl;
   ....
   bool operator<(const fixed& other) const;
   fixed operator>>(unsigned int shift_mt) const;
};

What do I need to do?

>> 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.
>
> Positive floats can be sorted just like integers, with the right functor.
> Negative floats have to be sorted backwards.  I didn't see any efficient way
> to write a functor to handle negative floats.

Can't you just pass a "greater" functor instead of "less"?

> I'll look at std::numeric_limits<>::is_iec559 and see if that does what I
> want.

It looks promising to me!

Phil.