Boost logo

Boost :

Subject: Re: [boost] [review] Formal review period for Sort library continuing through November 19
From: Steven Ross (spreadsort_at_[hidden])
Date: 2014-11-17 08:01:35


On Mon, Nov 17, 2014 at 7:21 AM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:
> Steven Ross wrote:
>> If std::sort can sort it, so can string_sort if you use the
>> available functors properly.
> How about:
> bool compare_distance_from_origin(point& a, point& b)
> {
> return sqr(a.x)+sqr(a.y) < sqr(b.x)+sqr(b.y);
> }
> std::sort(points.begin(),points.end(),&compare_distance_from_origin);

Your radix key is: sqr(x) + sqr(y). If you make all your functors work
relative to that generated key, it'll work fine.

> To me, it's clear that there are many kinds of sort where a radix
> sort can't be used. An interesting borderline case would be
> case-insensitive sorting; have you tried doing that?

Your Get_char functor just needs to convert one case to the other before
struct bracket {
  inline unsigned char operator()(const DATA_TYPE &x, size_t offset) const {
    return tolower(x.a[offset]);
for an example of using string_sort with functors. I'll convert that
example to do case-insensitive comparison, as that is an interesting case.

If you can represent your sort as a sequence of comparisons of sequences of
bytes, you can convert each of those comparisons into a sequence of bytes
that make up a synthetic radix. I am willing to concede that this might be
complicated, and in some cases less efficient when sorting reasonable
quantities of data, but it is doable.

I think many people are confused about the limitations of radix sorts,
because LSD radix sorting over more complex variable-length keys is
inefficient, but MSD radix sort does well with variable-length keys.

Boost list run by bdawes at, gregod at, cpdaniel at, john at