Radix-Sort ein Array von Zeichenfolgen?

Sehr ähnlich iavr, aber die Sortierung in-place (Benchmarks gegen iavr Lösung mit g++ -O3 und dauert etwa 2020ms im Vergleich zu iavr ist 1780ms), genießen ein regelmäßige Oberfläche und wiederverwendbar-code. Das problem mit Iavr Umsetzung ist, dass seine Logik funktioniert nur mit Container von strings, und ist nicht leicht erweiterbar, um andere Arten. Offensichtlich seine spezielle version die effizientere ist, aber es könnte sich lohnen, es zu opfern Leistung für die Regelmäßigkeit.
Finden Sie den rest des Codes an radix-sort-Implementierung

Allgemeinen Radix-Sortierung:

template <typename T> 
using Iter_value = std::iterator_traits<T>::value_type;

//intermediate struct to get partial template specialization
template<typename Iter, typename T, size_t range = 256>
struct rdx_impl {
    static void rdx_sort(Iter begin, Iter end, int bits) { 
        //bits is # bits to consider up to if a max val is known ahead of time
        //most efficent (theoretically) when digits are base n, having lg(n) bits
        constexpr size_t digit_bits {8};        //# bits in digit, 8 works well for 32 and 64 bit vals

            size_t d {0};                   //current digit #
            for (long long mask = (1 << digit_bits) - 1;
                d * digit_bits < bits;) {//ex. 0x000000ff for setting lower 8 bits on 32 bit num
                cnt_sort(begin, end, range, Digit_cmp<T>(mask, digit_bits*d));
                ++d;
            }
        }
    };

//specialization of rdx_sort for strings
struct Shorter {
    template <typename Seq>
    bool operator()(const Seq& a, const Seq& b) { return a.size() < b.size(); }
};
template <typename Iter>    
struct rdx_impl<Iter, std::string> {    //enough to hold ASCII char range
    static void rdx_sort(Iter begin, Iter end, int) {
        //ignore additional int argument
        int len_max = std::max_element(begin, end, Shorter())->size();
        for (int d = len_max - 1; d >= 0; --d)
            cnt_sort(begin, end, 128, Digit_cmp<std::string>(d));
    }
};

//generic call interface for all iterators 
template <typename Iter>   //use intermediate struct for partial specialization
void rdx_sort(Iter begin, Iter end, int bits) {
    rdx_impl<Iter, Iter_value<Iter>>::rdx_sort(begin, end, bits);
}

Zählen, Sortieren, Sortieren auf jeder Stelle (in place):

template <typename Iter, typename Op>
void cnt_sort(Iter begin, Iter end, size_t range, Op op) {
    using T = typename Iter::value_type;
    std::vector<int> counts(range);   //init to 0
    for (auto i = begin; i != end; ++i) //count # elems == i
        ++counts[op(*i)]; 
    for (size_t i = 1; i < range; ++i)
        counts[i] += counts[i-1];   //turn into # elems <= i
    std::vector<T> res(end - begin);
    for (auto j = end;;) {
        --j;
        res[--counts[op(*j)]] = *j;
        if (j == begin) break;
    }
    //~18% of time is spent on copying
    std::copy(res.begin(), res.end(), begin);
}

Extrahieren Wert der Stelle:

template <typename T>   //overload digit_cmp for non-integral types top provide radix sort with digits
class Digit_cmp {   //functor for comparing a "digit" (particular bits)
    const long long mask; //0..63 bitfield to test against
    const size_t to_shift;
public:
    Digit_cmp(long long m, size_t ts) : mask{m}, to_shift{ts} {}
    //by default assumes integral, just shifts
    size_t operator()(T n) const {    //char assuming r = 8
        return (n >> to_shift) & mask; //shift then mask for unit digit
    }
};
//specialization for strings
template <>
class Digit_cmp<std::string> {
    const size_t digit;
public:
    Digit_cmp(size_t d) : digit{d} {}
    size_t operator()(const std::string& str) {
        //0 indicates past the end of the string
        return str.size() > digit ? str[digit] : 0;
    }
};