Generic radix sort

Question

This started out with my answer to Radix Sort on an Array of Strings?. Since I intend to write a generic radix sort for my own purposes anyway, I continued a little bit, and here is a version tested on:

1. a fixed std::array of unsigned numbers, each treated as a fixed sequence of bytes from least-significant (right) to most-significant (left), to be sorted by natural order; and

2. an std::vector of std::strings, each treated as a variable-length sequence of characters from left to right, to be sorted by lexicographical order.

I will eventually make this more and more generic, but I am posting it here before it becomes extremely abstract. For now, it is not even parametrized with respect to ascending/descending order, but most interesting generalizations will be towards

• all scalar types: signed integers, floating-point, enums, pointers, etc.;
• sequences (built-in arrays or standard containers) of previous types to be sorted lexicographically;
• tuples or structures of previous types to be sorted lexicographically;
• recursive application of the above.

Here it is (live example):

#include <type_traits>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <iostream>

template<bool B>
using expr = std::integral_constant<bool, B>;

//-----------------------------------------------------------------------------

template <typename View, bool Var, bool Flip, size_t Radix>
class radix_sort
{
    template <typename I, typename S>
    void sort(I& idx, const S& slice) const
    {
        using A = std::array<size_t, (Var ? Radix + 1 : Radix)>;

        A count = {};
        I prev = idx;

        for (auto i : prev)
            ++count[slice(i)];

        A offset = {{0}};
        std::partial_sum(count.begin(), count.end() - 1, offset.begin() + 1);

        for (auto i : prev)
            idx[offset[slice(i)]++] = i;
    }

public:
    template <typename D>
    std::vector<size_t> operator()(const D& data) const
    {
        std::vector<size_t> idx(data.size());
        std::iota(idx.begin(), idx.end(), 0);

        if (data.size() < 2)
            return idx;

        View view;
        using R = decltype(data[0]);

        size_t width = Var ?
            view.size(*std::max_element(data.begin(), data.end(),
                [view](R a, R b) { return view.size(a) < view.size(b); }
            )) :
            view.size(data[0]);

        for (size_t d = 0; d < width; ++d)
        {
            size_t digit = Flip ? width - d - 1 : d;
            sort(idx, [&view, &data, digit] (size_t i) {
                return size_t(view.at(expr<Var>(), data[i], digit));
            });
        }

        return idx;
    }
};

//-----------------------------------------------------------------------------

struct int_view
{
    template<typename A>
    size_t size(const A& a) const { return sizeof(a); }

    template <bool B, typename E>
    unsigned char at(expr<B>, const E& elem, size_t pos) const
    {
        return (elem >> pos) & 0xFF;
    }
};

//-----------------------------------------------------------------------------

struct array_view
{
    template<typename A>
    size_t size(const A& a) const { return a.size(); }

    template <typename E>
    typename E::value_type
    at(std::false_type, const E& elem, size_t pos) const
    {
        return elem[pos];
    }

    template <typename E>
    typename E::value_type
    at(std::true_type, const E& elem, size_t pos) const
    {
        using T = typename E::value_type;
        return pos < elem.size() ? elem[pos] + T(1) : T(0);
    }
};

//-----------------------------------------------------------------------------

std::array<unsigned, 100>
numbers()
{
    return {{
        162, 794, 311, 528, 165, 601, 262, 654, 689, 748,
        450,  83, 228, 913, 152, 825, 538, 996,  78, 442,
        106, 961,   4, 774, 817, 868,  84, 399, 259, 800,
        431, 910, 181, 263, 145, 136, 869, 579, 549, 144,
        853, 622, 350, 513, 401,  75, 239, 123, 183, 239,
        417,  49, 902, 944, 490, 489, 337, 900, 369, 111,
        780, 389, 241, 403,  96, 131, 942, 956, 575,  59,
        234, 353, 821,  15,  43, 168, 649, 731, 647, 450,
        547, 296, 744, 188, 686, 183, 368, 625, 780,  81,
        929, 775, 486, 435, 446, 306, 508, 510, 817, 794
    }};
}

std::vector<std::string>
strings()
{
    return {
        "subdivides",
        "main street",
        "pants",
        "impaled decolonizing",
        "argillaceous",
        "axial satisfactoriness",
        "temperamental",
        "hypersensitiveness",
        "bears",
        "hairbreadths",
        "creams surges",
        "unlaboured",
        "hoosier",
        "buggiest",
        "mauritanians",
        "emanators",
        "acclaiming",
        "zouaves dishpan",
        "traipse",
        "solarisms",
        "remunerativeness",
        "solubilizing",
        "chiseled",
        "jugular",
        "ooziness",
        "toastier",
        "baud",
        "suffixed",
        "powerless tiding",
        "disassimilated",
        "gasps",
        "flirtier",
        "uh"
    };
}

//-----------------------------------------------------------------------------

template<typename G, typename S>
void test(G generate, S sort)
{
    auto data = generate();
    auto idx = sort(data);

    std::cout << "sorted data:" << std::endl;
    for (auto i : idx)
        std::cout << data[i] << std::endl;
    std::cout << std::endl;
}

int main()
{
    test(numbers, radix_sort<int_view,   false, false, 256>());
    test(strings, radix_sort<array_view, true,  true,  128>());
}

I would appreciate the following:

1. General comments on both algorithm and style.
2. Any more specific comments on correctness and efficiency.
3. Is the code self-evident, so that no comments are practically needed? For instance, is it evident what "views" and "slices" are?
4. I think I'll find my way with signed integral and remaining types, but is there a clean, standard, portable way of obtaining integral representations of mantissa + exponent of floating-point numbers, or should one resort to type casts and bitwise operations according to IEEE standard representations?

---

EDIT Please note I made a slight simplification in radix_sort::sort() compared to my original post.

Answer 1

Style

You should reorder your headers in alphabetic order. It will help when you will have to check whether a header is already included or not:

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <type_traits>
#include <vector>

You have many type names that are a single capital letter, which quite hinder readability. For example, you could change A into Arr. For many of them, I can't guess which "concept" should satisfy template parameter types. Apart from T and U for any type or N for any integral value, it is pretty uncommon to use a single capital letter.

You should also be consistent when naming your types: do you want them to be capitalized or not? If you want to be consistent, you could for example rename expr into Expr.

Generally speaking, the style is quite good: the indentation is clear, the lines are not too long and you don't seem to have any magic number besides 0xFF. I wish I could always read code that clean.

Idiomacity

In radix_sort::sort, you use member functions begin and end. It is now considered good style to write std::begin and std::end wherever possible so that you won't get into trouble if the code is changed. Moreover, in C++14, you will have std::cbegin and std::cend that rely on member begin and end. That means that pre-C++11 containers that do not provide member cbegin and cend can also be used.