c++ - Constexpr 排序的唯一容器集作为数组包装器

Question

我想创建一个像 std::array 这样的 constexpr 容器，它也是经过排序的并且所有元素都是唯一的。我想要实现的是在编译时检查构造函数中给定的数据是否已排序且唯一。我相信 std::set 接口(interface)更接近我想要实现的目标，但它不是 constexpr (还？)。我计划创建一个包装器并在内部使用 std::array，同时在外部公开 std::set 接口(interface)。

当前的实现如下所示

struct ConstexprSet
{
    constexpr ConstexprSet(const std::array<DataType, Size>& data) : mData(data)
    {
        if constexpr (!std::is_sorted(std::cbegin(mData), std::cend(mData)))
            throw std::runtime_error("Data not sorted");
        if constexpr (std::adjacent_find(std::cbegin(mData), std::cend(mData)) != std::cend(mData))
            throw std::runtime_error("Data not unique");
    }
    [[nodiscard]] constexpr auto GetData() const noexcept { return mData; }
private:
    std::array<DataType, Size> mData;
};

我得到的错误是“this”不是常量表达式。如果我使用 data 参数更改 mData，我会发现 data 不是常量表达式。那么到底什么是常量表达式呢？ 如果我将整个数组作为 NTTP 传递，这会起作用吗？

所需的用例是这样的

constexpr ConstexprSet features{"A"sv, "B"sv, "C"sv, "D"sv, "E"sv, "F"sv}; 

其中模板参数将从输入参数中推导出来，就像在 std::array 中一样。

以下两个示例不应成功编译，它们应提供全面的消息

constexpr ConstexprSet features{"A"sv, "D"sv, "C"sv, "B"sv, "E"sv, "F"sv}; // Data not sorted
constexpr ConstexprSet features{"A"sv, "B"sv, "B"sv, "D"sv, "E"sv, "F"sv}; // Data not unique

另一个失败的实验是创建一个带有初始化列表的构造函数并将其直接传递到内部数组，但这也不起作用......

任何有关如何克服此问题的想法或我可以遵循的任何其他方法来实现此容器的所需行为将非常受欢迎

我用于实验的当前草稿可以在这里找到 https://godbolt.org/z/1468cEjhW

Answer 1

struct ConstexprSet {
    std::array<DataType, Size> mData;

你不能这样做 - 在类级别，DataType 和 Size 甚至没有声明标识符。

让我们声明它们(T 代表 DataType，n 代表 Size):

template<typename T, auto n> class Set {
    std::array<T, n> mData;
// TODO

What I want to achieve is to check at compile time if the given data in the constructor are sorted and unique

那么你需要一个构造函数 consteval (必须在编译时运行)，而不是constexpr(运行时/编译时“多态”):

public:
    consteval Set(auto... ts): mData{std::move(ts)...} {
        if (n == 0) return; // can't think of a ready STL algorithm
        for (auto prev = mData.begin(), cur = prev + 1; cur != mData.end(); ++prev, ++cur)
            if (*prev >= *cur)
                throw std::logic_error{"not sorted / not unique"};
    }
};

方便的推演指南:

Set(auto t, auto... ts) -> Set<decltype(t), sizeof...(ts) + 1>;

测试:

int main() {
    constexpr Set set1{"A"sv, "B"sv, "D"sv}; // ok
    constexpr Set set2{"A"sv, "D"sv, "B"sv}; // error
    constexpr Set set3{"A"sv, "D"sv, "D"sv}; // error
}

should give comprehensive messages

source>:24:16: error: constexpr variable 'set2' must be initialized by a constant expression
        constexpr Set set2{"A"sv, "D"sv, "B"sv}; // error
                      ^~~~~~~~~~~~~~~~~~~~~~~~~
<source>:17:5: note: subexpression not valid in a constant expression
                                throw std::logic_error{"not sorted / not unique"};

source>:25:16: error: constexpr variable 'set3' must be initialized by a constant expression
        constexpr Set set3{"A"sv, "D"sv, "D"sv}; // error
                      ^~~~~~~~~~~~~~~~~~~~~~~~~
<source>:17:5: note: subexpression not valid in a constant expression
                                throw std::logic_error{"not sorted / not unique"};