Struct radix_sort
Synopsis
#include <src/entt/core/algorithm.hpp>
template<std::size_t Bit, std::size_t N>
struct radix_sort
Description
Function object for performing LSD radix sort.
- Template Parameters
Bit- Number of bits processed per pass.N- Maximum number of bits to sort.
Methods
| operator() | Sorts the elements in a range. |
Source
Lines 76-133 in src/entt/core/algorithm.hpp.
template<std::size_t Bit, std::size_t N>
struct radix_sort {
static_assert((N % Bit) == 0, "The maximum number of bits to sort must be a multiple of the number of bits processed per pass");
/**
* @brief Sorts the elements in a range.
*
* Sorts the elements in a range using the given _getter_ to access the
* actual data to be sorted.
*
* This implementation is inspired by the online book
* [Physically Based Rendering](http://www.pbr-book.org/3ed-2018/Primitives_and_Intersection_Acceleration/Bounding_Volume_Hierarchies.html#RadixSort).
*
* @tparam It Type of random access iterator.
* @tparam Getter Type of _getter_ function object.
* @param first An iterator to the first element of the range to sort.
* @param last An iterator past the last element of the range to sort.
* @param getter A valid _getter_ function object.
*/
template<typename It, typename Getter = identity>
void operator()(It first, It last, Getter getter = Getter{}) const {
if(first < last) {
static constexpr auto mask = (1 << Bit) - 1;
static constexpr auto buckets = 1 << Bit;
static constexpr auto passes = N / Bit;
using value_type = typename std::iterator_traits<It>::value_type;
std::vector<value_type> aux(std::distance(first, last));
auto part = [getter = std::move(getter)](auto from, auto to, auto out, auto start) {
std::size_t index[buckets]{};
std::size_t count[buckets]{};
for(auto it = from; it != to; ++it) {
++count[(getter(*it) >> start) & mask];
}
for(std::size_t pos{}, end = buckets - 1u; pos < end; ++pos) {
index[pos + 1u] = index[pos] + count[pos];
}
for(auto it = from; it != to; ++it) {
out[index[(getter(*it) >> start) & mask]++] = std::move(*it);
}
};
for(std::size_t pass = 0; pass < (passes & ~1); pass += 2) {
part(first, last, aux.begin(), pass * Bit);
part(aux.begin(), aux.end(), first, (pass + 1) * Bit);
}
if constexpr(passes & 1) {
part(first, last, aux.begin(), (passes - 1) * Bit);
std::move(aux.begin(), aux.end(), first);
}
}
}
};