In C++, a concept is a named set of requirements on a type. You can think of a concept as the C++ way of
specifying the interface of an abstract data type (ADT). The sequence concept enforces that a type satisfies the requirements of the sequence ADT we covered in class. To be a sequence, a type must satisfy the requirements:
i-th element of the sequence S with the syntax S[i]S with the syntax S.size()T
To force the value type of the sequence to be T, we can optionally write the concept as sequence<T>. The value type can also be left unspecified, so the concept sequence (without the type parameter T) matches a sequence of any type.
For example, the types par::array_sequence<int>, a std::array<int, N>, a std::vector<int>, a std::span<int>, etc., are all valid implementations of integer sequences, so they satisfy the sequence<int> concept.
sequence concept below, but you are not required to understand it. This requires rather advanced C++ knowledge to implement.
template<typename Range, typename T = void>
concept sequence = std::ranges::sized_range<Range> && std::ranges::random_access_range<Range> &&
(std::same_as<T, void> || std::same_as<std::range_value_t<Range>, T>) &&
requires(Range&& r, std::size_t i) {
{ r[i] } -> std::same_as<std::range_reference_t<Range>>;
{ r.size() } -> std::same_as<std::range_size_t<Range>>;
};
Functions in C++ (both ordinary and lambda functions) can be generic, meaning they can take inputs of different types. There are many ways to specify generic functions, the simplest of which is to use the auto keyword as the type of a parameter. Using auto as the type tells the compiler to deduce the type based on the type of the argument passed when calling the function.
Using auto as the type of a parameter makes the type unconstrained; the function will
accept any type for which the code compiles. We can restrict the type so that it is required to match
a particular concept by writing the concept name before the auto keyword.
In this class, we will frequently write generic algorithms on sequences using the pattern sequence auto, which means a generic (deduced) type that is required to match the sequence concept. For example, we can write a generic function that takes any integer sequence type (by constant reference) as
auto my_function(const sequence<int> auto& seq)
That's it! This function can now be called using an argument of any type that satisfies sequence<int>. Similarly, to write an even more generic function that can take a sequence of any value type, we can write
auto my_function(const sequence auto& seq)const sequence<int> auto&) or forwarding references (sequence<int> auto&&) to avoid accidental copies. Since C++ uses value semantics, writing sequence<int> auto as a parameter type will typically make an expensive deep copy of the argument!