主页 / 问题 / 1407454
Accepted
Denver Toha
Asked:2022-07-07 19:15:15 +0000 UTC2022-07-07 19:15:15 +0000 UTC

如何编写compile_time排序？

  • 772

最近我需要编写一个编译时排序。由于我们项目使用c++17，std::sort不是constexpr，20标准还没有完全支持。

我决定分享我的算法，如果他们改进它或告诉我错误，我会很高兴

c++ шаблоны-с++

2 个回答

  1. Best Answer

    只需像往常一样编写排序，并将其附加到constexpr.

    #include <array>
#include <iostream>
#include <utility>

template <typename T>
constexpr void sort(T *begin, T *end)
{
    for (T *mid = end; mid > begin;)
    {
        mid--;
        for (T *cur = begin; cur < mid; cur++)
        {
            if (cur[0] > cur[1])
            {
                T tmp(std::move(cur[0]));
                cur[0] = std::move(cur[1]);
                cur[1] = std::move(tmp);
            }
        }
    }
}

constexpr std::array<int, 4> foo()
{
    std::array<int, 4> ret = {2,4,3,1};
    sort(ret.data(), ret.data() + ret.size());
    return ret;
}

int main()
{
    constexpr auto arr = foo();
    for (int x : arr)
        std::cout << x << '\n';
}
    • 1

  2. 由于没有必要在编译时对大数组进行排序（也没有必要），所以我实现了最简单的插入排序。

    // енум нужен для примера, так как для моей задачи необходимо сортировать пары enum - строка
enum class MinLimValue : uint16_t
{
    NONE                 = 0,  // значение не задано
    // 0 - 3 бит - PPE
    MIN_BANNER_PPE       = 1 << 0,
    // 4 - 7 бит - cpm
    REQUEST_MIN_CPM      = 1 << 4,
    PAD_MIN_CPM          = 1 << 5,
    MIN_CPM_BY_ALIVE_CPM = 1 << 6,
};

namespace compile_time {

    // swapt для простых объектов и объектов с constexpr оператором присваивания
    template<typename T>
    constexpr void swap(T & aLeft, T & aRight) {
          T sTmp = aLeft;
          aLeft = aRight;
          aRight = sTmp;
    }
   
    // следующие 3 перегрузки нужны для свапа картежей
    template<size_t I, typename... T>
    constexpr void swap(std::tuple<T...> & aLeft, std::tuple<T...>& aRight)
    {
        auto& sLeft = std::get<I>(aLeft);
        auto& sRight = std::get<I>(aRight);
        auto sTmp = sLeft;
        sLeft = sRight;
        sRight = sTmp;
    }

    template<size_t... I, typename... T>
    constexpr void swap(std::tuple<T...> & aLeft, std::tuple<T...>& aRight,  std::index_sequence<I...>)
    {
        ([&]{ swap<I>(aLeft, aRight);}(), ...);
    }

    template<typename... T>
    constexpr void swap(std::tuple<T...> & aLeft, std::tuple<T...>& aRight)
    {
        constexpr auto sSize = std::tuple_size<std::tuple<T...>>{};
        swap(aLeft, aRight, std::make_index_sequence<sSize>{});
    }

    template<size_t I, typename T>
    constexpr void innerLoop(T& arr) {
        if constexpr(I == 0) {
            return;
        }
        for (size_t i = I; i > 0 && arr[i - 1] > arr[i]; i--) {
            compile_time::swap(arr[i - 1], arr[i]);
        }
    }

    template<typename T, std::size_t ...I>
    constexpr void outerLoop(T & arr, std::index_sequence<I...>)
    {
        ([&] {
            innerLoop<I>(arr);
        }(), ...);
    }

    template<size_t Size, typename T>
    constexpr void sort(T& arr)
    {
        outerLoop(arr, std::make_index_sequence<Size>());
    }


    // для примера, чтоб проверить работает ли наша сортировка в comp
    constexpr auto makeArr()
    {
        std::array<std::tuple<MinLimValue, int>, 5> sTest{std::make_tuple(MinLimValue::NONE, 5),
                                                                 std::make_tuple(MinLimValue::PAD_MIN_CPM,3),
                                                                 std::make_tuple(MinLimValue::MIN_CPM_BY_ALIVE_CPM,5),
                                                                 std::make_tuple(MinLimValue::MIN_BANNER_PPE,10),
                                                                 std::make_tuple(MinLimValue::REQUEST_MIN_CPM,89)};
        sort<5>(sTest);
        return sTest;
    }
}

int main() {

    constexpr auto sArr = compile_time::makeArr();

    return 0;
}

    不幸的是，我无法创建一个嵌套循环，以便嵌套计数器使用 compile_time 获取一个变量值，编译器被诅咒了，所以在排序的 2 个循环中，我实现了函数。

    • 0

相关问题