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.