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);
CodePudding user response:
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>;
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]; };
CodePudding user response:
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]
.