98 void operator()(It first, It last, Getter getter = Getter{})
const {
100 constexpr auto passes = N / Bit;
102 using value_type =
typename std::iterator_traits<It>::value_type;
103 using difference_type =
typename std::iterator_traits<It>::difference_type;
104 std::vector<value_type> aux(
static_cast<std::size_t
>(std::distance(first, last)));
106 auto part = [getter = std::move(getter)](
auto from,
auto to,
auto out,
auto start) {
107 constexpr auto mask = (1 << Bit) - 1;
108 constexpr auto buckets = 1 << Bit;
111 std::size_t count[buckets]{};
113 for(
auto it = from; it != to; ++it) {
114 ++count[(getter(*it) >> start) & mask];
118 std::size_t index[buckets]{};
120 for(std::size_t pos{}, end = buckets - 1u; pos < end; ++pos) {
121 index[pos + 1u] = index[pos] + count[pos];
124 for(
auto it = from; it != to; ++it) {
125 const auto pos = index[(getter(*it) >> start) & mask]++;
126 out[
static_cast<difference_type
>(pos)] = std::move(*it);
130 for(std::size_t pass = 0; pass < (passes & ~1u); pass += 2) {
131 part(first, last, aux.begin(), pass * Bit);
132 part(aux.begin(), aux.end(), first, (pass + 1) * Bit);
135 if constexpr(passes & 1) {
136 part(first, last, aux.begin(), (passes - 1) * Bit);
137 std::move(aux.begin(), aux.end(), first);