如何在c ++ 17中编写constexpr快速排序？ [关闭]

Question

关闭。这个问题是off-topic。它当前不接受答案。

---

是否要改善此问题？ Update the question，因此堆栈溢出为on-topic。

[<15天前关闭。

如何在c ++ 17中编写constexpr快速排序？为什么我的代码不起作用？g ++输出：

/ Users / user1 / tests / test22.cpp：318：19：错误：constexpr变量'leftSize'必须通过常量表达式初始化constexpr size_t leftSize = GetLeftSize（array）;^ ~~~~~~~~~~~~~~~~~~/Users/user1/tests/test22.cpp:327:27：注意：在此处实例化功能模板特化“ QuickSort”时需要constexpr auto array13 = QuickSort（array12）;^/Users/user1/tests/test22.cpp:318:42：注意：在常量表达式中不允许读取非constexpr变量“数组”constexpr size_t leftSize = GetLeftSize（array）;^/Users/user1/tests/test22.cpp:318:42：注意：在调用“ array（array）”时/Users/user1/tests/test22.cpp:319:26：错误：非类型模板参数不是常量表达式constexpr std :: array left = QuickSort（SliceLeft（array））;^ ~~~~~~~~/Users/user1/tests/test22.cpp:319:26：注意：“ leftSize”的初始化程序不是常量表达式/Users/user1/tests/test22.cpp:318:19：注意：在此声明constexpr size_t leftSize = GetLeftSize（array）;^/Users/user1/tests/test22.cpp:327:17：错误：constexpr变量'array13'必须通过常量表达式初始化constexpr auto array13 = QuickSort（array12）;^ ~~~~~~~~~~~~~~~~~~

这是我的代码：

#include <array>

template<typename T, size_t N>
constexpr size_t GetLeftSize(const std::array<T, N> array)
{
    T f = array[0];
    size_t n = 1;
    for (size_t i = 1; i < N; i ++)
        if (array[i] <= f)
            n ++;

    return n;
}

// Get Left Slice
template<typename T, size_t N, size_t L>
constexpr std::array<T, L> SliceLeft(const std::array<T, N> array)
{
    std::array<T, L> result{};
    for (size_t i = 0; i < L; i ++)
        result[i] = array[i];
    return result;
}

// Get Right Slice
template<typename T, size_t N, size_t R>
constexpr std::array<T, R> SliceRight(const std::array<T, N> array)
{
    std::array<T, R> result{};
    for (size_t i = 0; i < R; i ++)
        result[i] = array[N - i];
    return result;
}

// Link Sclice
template<typename T, size_t L, size_t R>
constexpr std::array<T, L + R> LinkSlice(const std::array<T, L> left, const std::array<T, R> right)
{
    std::array<T, L + R> result{};

    for (size_t i = 0; i < L; i ++)
        result[i] = left[i];

    for (size_t i = 0; i < L; i ++)
        result[L + i] = right[i];

    return result;

}

// Quick sort function
template<typename T, size_t N>
constexpr const std::array<T, N> QuickSort(const std::array<T, N> array)
{
    if (N <= 1)
        return array;
    constexpr size_t leftSize = GetLeftSize(array);
    constexpr std::array<T, leftSize> left = QuickSort(SliceLeft<T, N, leftSize>(array));
    constexpr std::array<T, N - leftSize> right = QuickSort(SliceRight<T, N, N - leftSize>(array));
    return LinkSlice(left, right);
}

int main()
{   
    constexpr std::array<int, 6> array12{7, 9, 3, 6, 1, 19};
    constexpr auto array13 = QuickSort(array12);
    return 0;
}

Answer 1

array函数中的参数QuickSort不是constexpr变量，尽管它将使用constexpr参数array12进行初始化，因此您不能使用它来初始化constexpr变量leftSize。

实际上，constexpr函数可以修改其参数，因此您可以像执行普通函数一样实现QuickSort：

#include <array>

template<typename T, std::size_t N>
constexpr void QuickSort(std::array<T, N> &array, std::size_t low, std::size_t high)
{
    if (high <= low) return;
    auto i = low, j = high + 1;
    auto key = array[low];
    for (;;) {
        while (array[++i] < key) if (i == high) break;
        while (array[--j] > key) if (j == low) break;
        if (i >= j) break;

        auto tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;

    }

    auto tmp = array[low];
    array[low] = array[j];
    array[j] = tmp;

    QuickSort(array, low, j - 1);
    QuickSort(array, j + 1, high);
}

template<typename T, std::size_t N>
constexpr std::array<T, N> QuickSort(std::array<T, N> array)
{
    QuickSort(array, 0, N - 1);
    return array;
}

int main()
{   
    constexpr std::array<int, 6> array12{7, 9, 3, 6, 1, 19};
    constexpr auto array13 = QuickSort(array12);
    return 0;
} 

还要注意，由于C ++ 20，std::sort已经是constexpr。