C++ Standard Library Concepts

Some Simple Examples

You can define a concept in terms of a trait:

template <class T>
concept integral = std::is_integral_v<T>;

Or combine several traits with logic operators ||, && or !:

#include <concepts>

template <typename T>
concept IsMySupportedInt = std::same_as<T, int>
                        || std::same_as<T, long int>;

Alternatively, you can use a requires expression:

template <typename T>
concept ILabel = requires(T v)
{
  v.clear();
  {v.buildHtml()} -> std::convertible_to<std::string>;
};

(The foregoing code in curly brackets tests for member function clear() to work and for member function buildHtml to work and to return something convertible to std::string.)

Now, how are these concepts used?

An example:

template <std::integral IDX>
value_type& get(IDX idx);

NOTE: You could use just any other concept that has been defined inside or outside the STL.

Modeling Semantic Categories

The intent of concepts is to model semantic categories (Number, Range, RegularFunction) rather than syntactic restrictions (HasPlus, Array). According to ISO C++ core guideline T.20, The ability to specify a meaningful semantics is a defining characteristic of a true concept, as opposed to a syntactic constraint.

Note that in generic programming (implemented as templates in C++), we take the notion of an ADT a step further. Instead of writing down the specification for a single type, we describe a family of types that all have a common interface and semantic behavior. The set of requirements that describe the interface and semantic behavior is referred to as a concept. Algorithms constructed in the generic style are then applicable to any type that satisfies the requirements of the algorithm. This ability to use many different types with the same variable (or parameter of a function) is referred to as polymorphism.

A concept is thus a description of the requirements placed by a generic component on one or more of its arguments. A type or group of types that satisfies a concept's requirements is said to model the concept or to be a model of the concept. A concept is said to refine another concept when its requirements are a superset of those of the other concept.

Concept Requirements

Concept requirements usually come from the following categories:

Valid expressions

C++ expressions that must compile successfully for the objects involved in the expression to be considered models of the concept. For example, an Iterator x is expected to support the expressions ++x and *x.

Associated types

Types that participate in one or more of the valid expressions and that can be computed from the type(s) modeling the concept. Typically, associated types can be accessed either through typedefs nested within a class definition for the modeling type or through a traits class. For example, an iterator's value type is associated with the iterator through std::iterator_traits.

Invariants

Runtime characteristics of a model's instances that must always be true; that is, all operations on an instance must preserve these characteristics. The invariants often take the form of pre-conditions and post-conditions. For instance, after a Forward Iterator is copied, the copy and the original must compare equal.

Complexity guarantees

Maximum limits on how long the execution of one of the valid expressions will take, or how much of various resources its computation will use. Incrementing an Iterator, for example, is required to have constant complexity.

Implementation in the C++20

Class templates, function templates, and non-template functions (typically members of class templates) may be associated with a constraint, which specifies the requirements on template arguments, which can be used to select the most appropriate function overloads and template specializations.

Named sets of such requirements are called concepts. Each concept is a predicate, evaluated at compile time, and becomes a part of the interface of a template where it is used as a constraint:

#include <string>
#include <cstddef>
using namespace std::literals;

// Declaration of the concept "Hashable", which is satisfied by
// any type T such that for values a of type T,
// the expression std::hash<T>{}(a) compiles and its result is convertible to std::size_t
template<typename T>
concept bool Hashable () {
  return requires(T a) {
    { std::hash<T>{}(a) } -> std::size_t;
  };
};
<!--
template<typename T>
concept Hashable = requires(T a) {
    { std::hash<T>{}(a) } -> std::size_t;
};
-->

struct meow {};

template<Hashable T>
void f(T); // constrained C++20 function template

// Alternative ways to apply the same constraint:
// template<typename T>
//    requires Hashable<T>
// void f(T);
//
// template<typename T>
// void f(T) requires Hashable<T>;

int main() {
  f("abc"s); // OK, std::string satisfies Hashable
  f(meow{}); // Error: meow does not satisfy Hashable
}

Violations of constraints are detected at compile time, early in the template instantiation process, which leads to easy to follow error messages.

std::list<int> l = {3,-1,10};
std::sort(l.begin(), l.end());
//Typical compiler diagnostic without concepts:
//  invalid operands to binary expression ('std::_List_iterator<int>' and
//  'std::_List_iterator<int>')
//                           std::__lg(__last - __first) * 2);
//                                     ~~~~~~ ^ ~~~~~~~
// ... 50 lines of output ...
//
//Typical compiler diagnostic with concepts:
//  error: cannot call std::sort with std::_List_iterator<int>
//  note:  concept RandomAccessIterator<std::_List_iterator<int>> was not satisfied

Syntax for Concepts

as in

Concepts cannot recursively refer to themselves and cannot be constrained:

Explicit instantiations, explicit specializations, or partial specializations of concepts are not allowed (the meaning of the original definition of a constraint cannot be changed).

template<Incrementable T>
void f(T) requires Decrementable<T>;

template<Incrementable T>
void f(T) requires Decrementable<T>; // OK, redeclaration

template<typename T>
    requires Incrementable<T> && Decrementable<T>
void f(T); // Ill-formed, no diagnostic required

// the following two declarations have different constraints:
// the first declaration has Incrementable<T> && Decrementable<T>
// the second declaration has Decrementable<T> && Incrementable<T>
// Even though they are logically equivalent.

template<Incrementable T>
void g(T) requires Decrementable<T>;

template<Decrementable T>
void g(T) requires Incrementable<T>; // ill-formed, no diagnostic required

template<class T> constexpr bool is_meowable = true;
template<class T> constexpr bool is_cat = true;

template<class T>
concept Meowable = is_meowable<T>;

template<class T>
concept BadMeowableCat = is_meowable<T> && is_cat<T>;

template<class T>
concept GoodMeowableCat = Meowable<T> && is_cat<T>;

template<Meowable T>
void f1(T); // #1

template<BadMeowableCat T>
void f1(T); // #2

template<Meowable T>
void f2(T); // #3

template<GoodMeowableCat T>
void f2(T); // #4

void g(){
    f1(0); // error, ambiguous:
           // the is_meowable<T> in Meowable and BadMeowableCat forms distinct
           // atomic constraints that are not identical (and so do not subsume each other)

    f2(0); // OK, calls #4, more constrained than #3
           // GoodMeowableCat got its is_meowable<T> from Meowable
}

Sets of Requirements

The requirements for a concept consist of a set of valid expressions, associated types, invariants, and complexity guarantees. A type that meets the set of requirements is said to model the concept. A concept can extend the requirements of another concept, which is called refinement.

Valid Expressions are C++ expressions that must compile successfully for the types involved in the expression to be considered models of the concept.
Associated Types are auxiliary types that have some relation to the type T modeling the concept. The requirements in a concept typically make statements about associated types. For example, iterator requirements typically include an associated type called the value_type and the requirement that objects returned by the iterator's dereference operator must be of the value_type. In C++ it is common to use a traits class to map from the type T to the associated types of the concept.
Invariants are run-time characteristics of types that must always be true. The invariants often take the form of preconditions and postconditions. When a precondition is not fulfilled, the behavior of the operation is, in general, undefined and can lead to a segmentation fault. This is the case for the Boost Graph Library. Some libraries provide debugging versions that use assertions or throw exceptions when a precondition is violated.
Complexity Guarantees are maximum limits on how long the execution of one of the valid expressions will take, or how much of the various resources its computation will use.

Example: InputIterator

In this section, we take a closer look at InputIterator as an example of a concept. First, the InputIterator concept is a refinement of TrivialIterator which, in turn, is a refinement of Assignable and EqualityComparable . Thus, the InputIterator meets all the requirements of a TrivialIterator (which meets all of the requirements of Assignable and EqualityComparable) The result is that a type that models InputIterator will have a dereference operator, it can be copied and assigned, and it can be compared with other iterator objects using == and != .

The InputIterator concept adds the requirement for pre-increment and post-increment operators. These requirements are denoted by the following valid expressions. Objects i and j are instances of a type T that models InputIterator.

The std::iterator_traits class provides access to the associated types of an iterator type. The type of an object that is pointed to by an iterator type (call it X) can be determined via the value_type of the traits class. The other associated types are reference, pointer, difference_type, and iterator_category.

In the following function template we show the use of the iterator_traits class to obtain the value_type of the iterator and dereference the iterator.

As for complexity guarantees, all of the InputIterator operations are required to be constant time. Some types that model InputIterator are std::list<int>::iterator, double*, and std::istream iterator<char>.

The purpose of defining concepts becomes clear when considering the implementation of generic algorithms. The implementation of the std::for_each() function follows. Inside the function precisely four operations are applied to the iterator objects first or last : comparison using operator!=(), increment with operator++(), dereference with operator*(), and copy construction. For this function to compile and operate properly the iterator arguments must support at least these four operations. The concept InputIterator includes these operations (and not many more), so it is a reasonable choice for succinctly describing the requirements of for_each().

template <typename InputIterator, typename Function>
Function for_each(InputIterator first, InputIterator last, Function f ) {
  for ( ; first != last; ++first)
  f(*first);
  return f ;
}

Standard Concepts

The concepts library provides definitions of fundamental library concepts that can be used to perform compile-time validation of template arguments and perform function dispatch based on properties of types.

Most concepts in the standard library impose both syntactic and semantic requirements. It is said that a standard concept is satisfied if its syntactic requirements are met, and is modeled if it is satisfied and its semantic requirements (if any) are also met.

All the concepts below demand inclusion of <concepts> (C++20).

Additional concepts can be found in the iterators library, the algorithms library, and ranges library.