Boost logo

Boost :

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-01-15 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?

>
> 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?

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 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"?

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