
Boost : 
Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 20090115 08:40:14
On Wed, Jan 14, 2009 at 2:48 PM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:
>
>
> 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.
It's an arithmetic right shift, or alternatively division by a power of 2.
What do you want to call it?
>
> Fixedpoint 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?
You < operator is fine, and usable without modification.
If your  operator returns something castable to a size_t, then you don't
need any functors, that will do (return impl  right.impl;)
If your  operator doesn't return something castable to a size_t, then you
need to define a rightshift functor that does. How about:
struct rightshift {
some_integer_type operator()(const fixed &x, unsigned offset) { return
x.impl >> offset; }
};
>
> I would
>>> have thought that the floatingpoint algorithm would just be an instance
>>> of
>>> the generic algorithm with custom functors, with a bit of specialisation
>>> to
>>> cope with the reverseorderfornegatives 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"?
Yes, but that would hurt efficiency.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk