
Boost : 
Subject: Re: [boost] Proposed templated integer_sort
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 20090114 17:48:29
Steven Ross wrote:
>> You seem to have quite a lot of code that's duplicated for the functor and
>> nonfunction 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 nonfunctor 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 25%), 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 functorversions are since they still seem to
>> depend on the "integerness" or "floatness" 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, fixedpoint types or pointerstointegers 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.
> 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?
>> 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"?
> I'll look at std::numeric_limits<>::is_iec559 and see if that does what I
> want.
It looks promising to me!
Phil.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk