C++ 20 接受随机访问容器但拒绝的概念 std::list

Question

已知

std::vector满足一个RandomAccessContainer的要求，所以使用[]运算符是常量时间。然而，std::list 只满足 Container 和 ReversibleContainer 的较弱要求，因此检索元素是 O(N)，而且 [] 运算符不存在。

我想约束一个模板，以便在 [] 运算符不存在或不是 O(1) 时得到一个很好的编译时错误。我怎样才能做到这一点？

目前，在 g++ 11.2.0 上，当使用 std::list:

实例化以下模板时，我无法收到清晰的错误消息

template<typename RandomAccessContainer>
void foo(RandomAccessContainer const & x);

template<typename ContiguousContainer>
void foo(ContiguousContainer const & x);

template<typename T>
requires ContiguousContainer<T>
void foo(T const & x);

Answer 1

您可以从类型特征开始检查类型是否支持下标：

template<class T>
struct has_subscript {
    static std::false_type test(...);

    template<class U>
    static auto test(const U& t) -> decltype(t[0], std::true_type{});

    static constexpr bool value = decltype(test(std::declval<T>()))::value;
};

template <class T>
inline constexpr bool has_subscript_v = has_subscript<T>::value;

然后补充概念：

template <class T>
concept subscriptable = has_subscript_v<T>;

template <class T>
concept subscript_and_cont_iterator =
    std::contiguous_iterator<decltype(std::begin(std::declval<T>()))> &&
    subscriptable<T>;

Demo

如果不需要类型特征，只需使用 requires 子句使 subscriptable：

template <class T>
concept subscriptable = requires(const T& c) { c[0]; };

Demo

Answer 2

Ranges 库附带了一堆 range-related 概念。在这种情况下，您需要：

template <std::ranges::random_access_range R>
void foo(R&& x);

这个概念不检查范围本身是否有 []（无论如何这对你来说是不够的，map 提供但不是随机访问），但它确实检查iterator是随机访问迭代器，要求随机访问迭代器本身支持索引。

所以你必须写 ranges::begin(x)[2].

而不是 x[2]

C++ 20 接受随机访问容器但拒绝的概念 std::list

C++ 20 concept to accept a random access container but reject std::list

c++

c++-concepts

c++20