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

user_904050 0
Viewed 201

std::vector is known to meet the requirement of a RandomAccessContainer, so using the [] operator is constant time. However, std::list only meets the weaker requirements of a Container and ReversibleContainer, and hence retrieving an element is O(N), moreover the [] operator doesn't exist.

I would like to constrain a template so that I can get a nice compile-time error whenever the [] operator doesn't exist or is not O(1). How can I achieve this?

Currently, on g++ 11.2.0, I cannot get a clean error message when instantiating the following templates with a 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);
c++-concepts c++20 c++
2 Answers

The Ranges library comes with a bunch of range-related concepts. In this case, you want:

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

This concept doesn't check if the range itself has [] (and that's insufficient for you anyway, map provides that but isn't random access), but it does check that the iterator is a random access iterator, and random access iterators are required to themselves support indexing.

So rather than x[2] you have to write ranges::begin(x)[2].

user_20690640

You could start with a type trait to check if the type supports subscripting:

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;

Then add concepts:

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

If you don't need the type trait, just make subscriptable using a requires clause:

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

Demo

user_75822470
Related