Как можно статически утверждать член класса std :: array для сортировки в c ++ 11?

Question

Как можно во время компиляции утверждать, что член класса std::array<uint8_t, 3> отсортирован? Это позволило бы сделать его const, использовать static_assert() и не вызывать std::sort() в конструкторе.

В c ++ 20 std::is_sorted() стало constexpr, но не является доступно для предыдущих версий.

Answer 1

Вот подтверждение реализации концепции, которая может быть вызвана непосредственно на std::array; сделать это более общим (для других типов контейнеров constexpr) оставлено читателю в качестве упражнения:

template <typename T, std::size_t N>
constexpr bool is_sorted(std::array<T, N> const& arr, std::size_t from) {
    return N - from == 0 or (arr[from - 1] <= arr[from] and is_sorted(arr, from + 1));
}

template <typename T, std::size_t N>
constexpr bool is_sorted(std::array<T, N> const& arr) {
    return N == 0 or is_sorted(arr, 1);
}

Answer 2

Отказ от ответственности: Для этого требуется C ++ 14, поскольку, как я уже упоминал в комментариях, вы, вероятно, не сможете реализовать constexpr версию is_sorted для std::array до C ++ 14 из-за того, что некоторые операции над std::array не являются constexpr ¹ в C ++ 11 (operator[] / std::get<>).

В реализации C ++ 14, вы можете использовать стандартный for -l oop в вашей функции constexpr и использовать эту очень простую реализацию:

template<typename T, std::size_t N>
constexpr bool is_sorted(std::array<T, N> const &arr) {
    for (std::size_t i = 0; i < arr.size() - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}

Обратите внимание, что реализация is_sorted для других контейнеров основана на итераторах (array, span, string_view), вероятно, требуется C ++ 20, поскольку таких вещей, как ConstexprIterator до C ++ 20.

_{¹ Похоже, g cc и clang предоставляют этих членов как constexpr даже с -std=c++11, так что если это нормально для вас, вы можете использовать один из двух других ответов.}

Answer 3

Не так хорошо, как другое решение, но я хотел показать, что это возможно (даже если досадно) в C ++ 11 (опираясь на решение @ KonradRudolph)

Редактировать: Это также просто C ++ 14, поскольку с тех пор std::get составляет всего constexpr. Страница на нем в cppref сбивает с толку, но с тех пор исправлена.

#include <array>
#include <type_traits>

template<typename T, std::size_t N, std::size_t from>
constexpr typename std::enable_if<from == N, bool>::type
    is_sorted_impl(std::array<T, N> const &arr)
{
    return true;
}

template<typename T, std::size_t N, std::size_t from,
         class = typename std::enable_if<from<N>::type> 
constexpr bool is_sorted_impl(std::array<T, N> const &arr)
{
    return N - from == 0 or (std::get<from - 1>(arr) <= std::get<from>(arr) and
                             is_sorted_impl<T, N, from + 1>(arr));
}

template<typename T, std::size_t N>
constexpr bool is_sorted(std::array<T, N> const &arr)
{
    return N == 0 or is_sorted_impl<T, N, 1>(arr);
}

int main()
{
    constexpr std::array<int, 5> arr{1, 2, 3, 4, 5};
    static_assert(is_sorted(arr), "test");
}

Мы используем std::get, что было constexpr с момента ее появления в C ++ 14 , Чтобы обойти создание экземпляра std::get<N> (который, очевидно, дает ошибку времени компиляции), мы специализируем шаблон функции для случая from == N (что нам нужно сделать с enable_if, поскольку частичные специализации шаблона функции не допускаются). Не очень хорошо, но возможно.

С другой стороны: решение @ KonradRudolph компилируется в g cc и также включается -std=c++11 -pedantic, хотя это не должно быть из-за того, что operator[] не является constexpr, это ошибка?