如何在 C++17 中编写 constexpr 快速排序？

Question

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

/Users/user1/tests/test22.cpp:318:19: error: constexpr variable 'leftSize' must be initialized by a constant expression
constexpr size_t leftSize = GetLeftSize(array);
^ ~~~~~~~~~~~~~~~~~~
/Users/user1/tests/test22.cpp:327:27: note: in instantiation of function template specialization 'QuickSort' requested here
constexpr auto array13 = QuickSort(array12);
^
/Users/user1/tests/test22.cpp:318:42: note: read of non-constexpr variable 'array' is not allowed in a constant expression
constexpr size_t leftSize = GetLeftSize(array);
^
/Users/user1/tests/test22.cpp:318:42: note: in call to 'array(array)'
/Users/user1/tests/test22.cpp:319:26: error: non-type template argument is not a constant expression
constexpr std::array left = QuickSort(SliceLeft(array));
^~~~~~~~
/Users/user1/tests/test22.cpp:319:26: note: initializer of 'leftSize' is not a constant expression
/Users/user1/tests/test22.cpp:318:19: note: declared here
constexpr size_t leftSize = GetLeftSize(array);
^
/Users/user1/tests/test22.cpp:327:17: error: constexpr variable 'array13' must be initialized by a constant expression
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

函数QuickSort中的参数array不是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。

如何在 C++17 中编写 constexpr 快速排序？

How to write a constexpr quick sort in c++17?

c++

sorting

constexpr

c++17