1#ifndef ENTT_CORE_ALGORITHM_HPP
2#define ENTT_CORE_ALGORITHM_HPP
35 template<
typename It,
typename Compare = std::less<>,
typename... Args>
36 void operator()(It first, It last, Compare compare = Compare{}, Args &&...args)
const {
37 std::sort(std::forward<Args>(args)..., std::move(first), std::move(last), std::move(compare));
54 template<
typename It,
typename Compare = std::less<>>
55 void operator()(It first, It last, Compare compare = Compare{})
const {
57 for(
auto it = first + 1; it < last; ++it) {
58 auto value = std::move(*it);
61 for(; pre > first && compare(value, *(pre - 1)); --pre) {
62 *pre = std::move(*(pre - 1));
65 *pre = std::move(value);
76template<std::
size_t Bit, std::
size_t N>
78 static_assert((N % Bit) == 0,
"The maximum number of bits to sort must be a multiple of the number of bits processed per pass");
95 template<
typename It,
typename Getter =
identity>
96 void operator()(It first, It last, Getter getter = Getter{})
const {
98 constexpr auto passes = N / Bit;
100 using value_type =
typename std::iterator_traits<It>::value_type;
101 std::vector<value_type> aux(std::distance(first, last));
103 auto part = [getter = std::move(getter)](
auto from,
auto to,
auto out,
auto start) {
104 constexpr auto mask = (1 << Bit) - 1;
105 constexpr auto buckets = 1 << Bit;
107 std::size_t index[buckets]{};
108 std::size_t count[buckets]{};
110 for(
auto it = from; it != to; ++it) {
111 ++count[(getter(*it) >> start) & mask];
114 for(std::size_t pos{}, end = buckets - 1u; pos < end; ++pos) {
115 index[pos + 1u] = index[pos] + count[pos];
118 for(
auto it = from; it != to; ++it) {
119 out[index[(getter(*it) >> start) & mask]++] = std::move(*it);
123 for(std::size_t pass = 0; pass < (passes & ~1); pass += 2) {
124 part(first, last, aux.begin(), pass * Bit);
125 part(aux.begin(), aux.end(), first, (pass + 1) * Bit);
128 if constexpr(passes & 1) {
129 part(first, last, aux.begin(), (passes - 1) * Bit);
130 std::move(aux.begin(), aux.end(), first);
Function object for performing insertion sort.
void operator()(It first, It last, Compare compare=Compare{}) const
Sorts the elements in a range.
Function object for performing LSD radix sort.
void operator()(It first, It last, Getter getter=Getter{}) const
Sorts the elements in a range.
Function object to wrap std::sort in a class type.
void operator()(It first, It last, Compare compare=Compare{}, Args &&...args) const
Sorts the elements in a range.