concepts.tex

%!TEX root = std.tex

\rSec0[concepts.lib]{Concepts library}

\rSec1[concepts.lib.general]{General}

\pnum
This Clause describes library components that \Cpp programs may use to perform
compile-time validation of template parameters and perform function dispatch
based on properties of types. The purpose of these concepts is to establish
a foundation for equational reasoning in programs.

\pnum
The following subclauses describe core language concepts,
comparison concepts, object concepts, and function concepts
as summarized in Table~\ref{tab:concepts.lib.summary}.

\begin{libsumtab}{Fundamental concepts library summary}{tab:concepts.lib.summary}
\ref{concepts.lib.corelang}   & Core language concepts         &   \tcode{<experimental/ranges/concepts>}      \\
\ref{concepts.lib.compare}    & Comparison concepts            &                      \\
\ref{concepts.lib.object}     & Object concepts                &                      \\
\ref{concepts.lib.callable}   & Callable concepts              &                      \\
\end{libsumtab}

\rSec2[concepts.lib.general.equality]{Equality Preservation}

\pnum
An expression is \techterm{equality preserving} if, given equal inputs, the expression results in
equal outputs. The inputs to an expression are the set of the expression's operands. The
output of an expression is the expression's result and all operands modified by the expression.

\pnum
Not all input values must be valid for a given expression; e.g., for integers \tcode{a}
and \tcode{b}, the expression \tcode{a / b} is not well-defined when \tcode{b} is \tcode{0}. This
does not preclude the expression \tcode{a / b} being equality preserving. The
\techterm{domain} of an expression is the set of input values for which the
expression is required to be well-defined.

\pnum
Expressions required by this specification to be equality preserving are
further required to be stable: two evaluations of such an expression with the same
input objects must have equal outputs absent any
explicit intervening modification of those input objects.
\enternote This requirement allows generic code to reason
about the current values of objects based on knowledge of the prior values as
observed via equality preserving expressions. It effectively forbids spontaneous
changes to an object, changes to an object from another thread of execution, changes
to an object as side effects of non-modifying expressions, and changes to an object as
side effects of modifying a distinct object if those changes could be observable
to a library function via an equality preserving expression that is required to be
valid for that object. \exitnote

\pnum
Expressions declared in a \grammarterm{requires-expression} in this document are
required to be equality preserving, except for those annotated with the comment
``not required to be equality preserving.'' An expression so annotated
may be equality preserving, but is not required to be so.

\pnum
An expression that may alter the value of one or more of its inputs in a manner
observable to equality preserving expressions is said to modify those inputs.
This document uses a notational convention to specify which expressions declared
in a \grammarterm{requires-expression} modify which inputs: except where otherwise
specified, an expression operand that is a non-constant lvalue or rvalue may be
modified. Operands that are constant lvalues or rvalues must not be modified.

\pnum
Where a \grammarterm{requires-expression} declares an expression that is non-modifying
for some constant lvalue operand, additional variations of that expression that accept
a non-constant lvalue or (possibly constant) rvalue for the given operand are also
required except where such an expression variation is explicitly required with
differing semantics. These \techterm{implicit expression variations} must meet the semantic
requirements of the declared expression. The extent to which an implementation
validates the syntax of the variations is unspecified.

\enterexample
\begin{codeblock}
template <class T>
concept bool C =
  requires(T a, T b, const T c, const T d) {
    c == d;           // \#1
    a = std::move(b); // \#2
    a = c;            // \#3
  };
\end{codeblock}

Expression \#1 does not modify either of its operands, \#2 modifies both of its
operands, and \#3 modifies only its first operand \tcode{a}.

Expression \#1 implicitly requires additional expression variations that meet the
requirements for \tcode{c == d} (including non-modification), as if the expressions
\begin{codeblock}
a == d;       a == b;             a == move(b);       a == d;
c == a;       c == move(a);       c == move(d);
move(a) == d; move(a) == b;       move(a) == move(b); move(a) == move(d);
move(c) == b; move(c) == move(b); move(c) == d;       move(c) == move(d);
\end{codeblock}
had been declared as well.

Expression \#3 implicitly requires additional expression variations that meet the
requirements for \tcode{a = c} (including non-modification of the second operand),
as if the expressions \tcode{a = b} and \tcode{a = move(c)} had been declared.
Expression \#3 does not implicitly require an expression variation with a
non-constant rvalue second operand, since expression \#2 already specifies exactly
such an expression explicitly.
\exitexample

\enterexample
The following type \tcode{T} meets the explicitly stated syntactic requirements
of concept \tcode{C} above but does not meet the additional implicit requirements:

\begin{codeblock}
struct T {
  bool operator==(const T&) const { return true; }
  bool operator==(T&) = delete;
};
\end{codeblock}

\tcode{T} fails to meet the implicit
requirements of \tcode{C}, so \tcode{C<T>} is not satisfied. Since
implementations are not required to validate the syntax of implicit requirements, it
is unspecified whether or not an implementation diagnoses as ill-formed a program
which requires \tcode{C<T>}.
\exitexample

\rSec1[concepts.lib.synopsis]{Header \tcode{<experimental/ranges/concepts>} synopsis}

\indexlibrary{\idxhdr{experimental/ranges/concepts}}%
\begin{codeblock}
namespace std { namespace experimental { namespace ranges { inline namespace v1 {
  // \ref{concepts.lib.corelang}, core language concepts:
  // \ref{concepts.lib.corelang.same}, Same:
  template <class T, class U>
  concept bool Same = @\seebelow@;

  // \ref{concepts.lib.corelang.derived}, DerivedFrom:
  template <class T, class U>
  concept bool DerivedFrom = @\seebelow@;

  // \ref{concepts.lib.corelang.convertibleto}, ConvertibleTo:
  template <class T, class U>
  concept bool ConvertibleTo = @\seebelow@;

  // \ref{concepts.lib.corelang.commonref}, CommonReference:
  template <class T, class U>
  concept bool CommonReference = @\seebelow@;

  // \ref{concepts.lib.corelang.common}, Common:
  template <class T, class U>
  concept bool Common = @\seebelow@;

  // \ref{concepts.lib.corelang.integral}, Integral:
  template <class T>
  concept bool Integral = @\seebelow@;

  // \ref{concepts.lib.corelang.signedintegral}, SignedIntegral:
  template <class T>
  concept bool SignedIntegral = @\seebelow@;

  // \ref{concepts.lib.corelang.unsignedintegral}, UnsignedIntegral:
  template <class T>
  concept bool UnsignedIntegral = @\seebelow@;

  // \ref{concepts.lib.corelang.assignable}, Assignable:
  template <class T, class U>
  concept bool Assignable = @\seebelow@;

  // \ref{concepts.lib.corelang.swappable}, Swappable:
  template <class T>
  concept bool Swappable = @\seebelow@;

  template <class T, class U>
  concept bool SwappableWith = @\seebelow@;

  // \ref{concepts.lib.corelang.destructible}, Destructible:
  template <class T>
  concept bool Destructible = @\seebelow@;

  // \ref{concepts.lib.corelang.constructible}, Constructible:
  template <class T, class... Args>
  concept bool Constructible = @\seebelow@;

  // \ref{concepts.lib.corelang.defaultconstructible}, DefaultConstructible:
  template <class T>
  concept bool DefaultConstructible = @\seebelow@;

  // \ref{concepts.lib.corelang.moveconstructible}, MoveConstructible:
  template <class T>
  concept bool MoveConstructible = @\seebelow@;

  // \ref{concepts.lib.corelang.copyconstructible}, CopyConstructible:
  template <class T>
  concept bool CopyConstructible = @\seebelow@;

  // \ref{concepts.lib.compare}, comparison concepts:
  // \ref{concepts.lib.compare.boolean}, Boolean:
  template <class B>
  concept bool Boolean = @\seebelow@;

  // \ref{concepts.lib.compare.equalitycomparable}, EqualityComparable:
  template <class T, class U>
  concept bool WeaklyEqualityComparableWith = @\seebelow@;

  template <class T>
  concept bool EqualityComparable = @\seebelow@;

  template <class T, class U>
  concept bool EqualityComparableWith = @\seebelow@;

  // \ref{concepts.lib.compare.stricttotallyordered}, StrictTotallyOrdered:
  template <class T>
  concept bool StrictTotallyOrdered = @\seebelow@;

  template <class T, class U>
  concept bool StrictTotallyOrderedWith = @\seebelow@;

  // \ref{concepts.lib.object}, object concepts:
  // \ref{concepts.lib.object.movable}, Movable:
  template <class T>
  concept bool Movable = @\seebelow@;

  // \ref{concepts.lib.object.copyable}, Copyable:
  template <class T>
  concept bool Copyable = @\seebelow@;

  // \ref{concepts.lib.object.semiregular}, Semiregular:
  template <class T>
  concept bool Semiregular = @\seebelow@;

  // \ref{concepts.lib.object.regular}, Regular:
  template <class T>
  concept bool Regular = @\seebelow@;

  // \ref{concepts.lib.callable}, callable concepts:
  // \ref{concepts.lib.callable.invocable}, Invocable:
  template <class F, class... Args>
  concept bool Invocable = @\seebelow@;

  // \ref{concepts.lib.callable.regularinvocable}, RegularInvocable:
  template <class F, class... Args>
  concept bool RegularInvocable = @\seebelow@;

  // \ref{concepts.lib.callable.predicate}, Predicate:
  template <class F, class... Args>
  concept bool Predicate = @\seebelow@;

  // \ref{concepts.lib.callable.relation}, Relation:
  template <class R, class T, class U>
  concept bool Relation = @\seebelow@;

  // \ref{concepts.lib.callable.strictweakorder}, StrictWeakOrder:
  template <class R, class T, class U>
  concept bool StrictWeakOrder = @\seebelow@;
}}}}
\end{codeblock}

\rSec1[concepts.lib.corelang]{Core language concepts}

\rSec2[concepts.lib.corelang.general]{General}

\pnum
This section contains the definition of concepts corresponding to language features.
These concepts express relationships between types, type classifications, and
fundamental type properties.

\rSec2[concepts.lib.corelang.same]{Concept \tcode{Same}}

\indexlibrary{\idxcode{Same}}%
\begin{itemdecl}
template <class T, class U>
concept bool Same = is_same<T, U>::value; // \seebelow
\end{itemdecl}

\begin{itemdescr}
\pnum
There need not be any subsumption relationship between \tcode{Same<T, U>} and
\tcode{is_same<T, U>::value}.

\pnum
\remarks For the purposes of constraint checking, \tcode{Same<T, U>} implies
\tcode{Same<U, T>}.
\end{itemdescr}

\rSec2[concepts.lib.corelang.derived]{Concept \tcode{DerivedFrom}}

\indexlibrary{\idxcode{DerivedFrom}}%
\begin{itemdecl}
template <class T, class U>
concept bool DerivedFrom =
  is_base_of<U, T>::value &&
  is_convertible<remove_cv_t<T>*, remove_cv_t<U>*>::value; // \seebelow
\end{itemdecl}

\begin{itemdescr}
\pnum
There need not be any subsumption relationship between \tcode{DerivedFrom<T, U>}
and either \tcode{is_base_of<U, T>::value} or
\tcode{is_convertible<remove_cv_t<T>*, remove_cv_t<U>*>::value}.

\pnum
\enternote \tcode{DerivedFrom<T, U>} is satisfied if and only if \tcode{T} is
publicly and unambiguously derived from \tcode{U}, or \tcode{T} and \tcode{U}
are the same class type ignoring \cv-qualifiers. \exitnote
\end{itemdescr}

\rSec2[concepts.lib.corelang.convertibleto]{Concept \tcode{ConvertibleTo}}

\indexlibrary{\idxcode{ConvertibleTo}}%
\begin{itemdecl}
template <class T, class U>
concept bool ConvertibleTo =
  is_convertible<From, To>::value && // \seebelow
  requires(From (&f)()) {
    static_cast<To>(f());
  };
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{test} be the invented function:
\begin{codeblock}
To test(From (&f)()) {
  return f();
}
\end{codeblock}
and let \tcode{f} be a function with no arguments and return type \tcode{From}
such that \tcode{f()} is equality preserving.
\tcode{ConvertibleTo<From, To>} is satisfied only if:

\begin{itemize}
\item
\tcode{To} is not an object or reference-to-object type, or
\tcode{static_cast<To>(f())} is equal to \tcode{test(f)}.

\item
\tcode{From} is not a reference-to-object type, or

\begin{itemize}
\item
If \tcode{From} is an rvalue reference to a non const-qualified type, the resulting state of the object referenced by \tcode{f()} after either above expression is valid but unspecified~(\cxxref{lib.types.movedfrom}).

\item
Otherwise, the object referred to by \tcode{f()} is not modified by either above expression.
\end{itemize}

\end{itemize}

\pnum
There need not be any subsumption relationship between \tcode{ConvertibleTo<From, To>}
and \tcode{is_\-convert\-ible\brk{}<From,\brk{} To>::value}.
\end{itemdescr}


\rSec2[concepts.lib.corelang.commonref]{Concept \tcode{CommonReference}}

\pnum
For two types \tcode{T} and \tcode{U}, if \tcode{common_reference_t<T, U>}
is well-formed and denotes a type \tcode{C} such that both
\tcode{ConvertibleTo<T, C>} and \tcode{ConvertibleTo<U, C>} are
satisfied, then \tcode{T} and \tcode{U} share a \techterm{common reference
type}, \tcode{C}. \enternote \tcode{C} could be the same as \tcode{T}, or
\tcode{U}, or it could be a different type. \tcode{C} may be a reference
type. \tcode{C} need not be unique.\exitnote

\indexlibrary{\idxcode{CommonReference}}%
\begin{itemdecl}
template <class T, class U>
concept bool CommonReference =
  Same<common_reference_t<T, U>, common_reference_t<U, T>> &&
  ConvertibleTo<T, common_reference_t<T, U>> &&
  ConvertibleTo<U, common_reference_t<T, U>>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{C} be \tcode{common_reference_t<T, U>}. Let \tcode{t} be a
function whose return type is \tcode{T}, and let \tcode{u} be a function
whose return type is \tcode{U}. \tcode{CommonReference<T, U>} is satisfied
only if:
\begin{itemize}
\item \tcode{C(t())} equals \tcode{C(t())} if and only if \tcode{t()} is an
  equality preserving expression~(\ref{concepts.lib.general.equality}).
\item \tcode{C(u())} equals \tcode{C(u())} if and only if \tcode{u()} is an
  equality preserving expression.
\end{itemize}

\pnum
\enternote Users can customize the behavior of \tcode{CommonReference} by specializing the
\tcode{basic_common_reference} class template~(\ref{meta.trans.other}).\exitnote
\end{itemdescr}

\rSec2[concepts.lib.corelang.common]{Concept \tcode{Common}}

\pnum
If \tcode{T} and \tcode{U} can both be explicitly converted to some third type,
\tcode{C}, then \tcode{T} and \tcode{U} share a \techterm{common type},
\tcode{C}. \enternote \tcode{C} could be the same as \tcode{T}, or \tcode{U}, or
it could be a different type. \tcode{C} may not be unique.\exitnote

\indexlibrary{\idxcode{Common}}%
\begin{itemdecl}
template <class T, class U>
concept bool Common =
  Same<common_type_t<T, U>, common_type_t<U, T>> &&
  ConvertibleTo<T, common_type_t<T, U>> &&
  ConvertibleTo<U, common_type_t<T, U>> &&
  CommonReference<
    add_lvalue_reference_t<const T>,
    add_lvalue_reference_t<const U>> &&
  CommonReference<
    add_lvalue_reference_t<common_type_t<T, U>>,
    common_reference_t<
      add_lvalue_reference_t<const T>,
      add_lvalue_reference_t<const U>>>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{C} be \tcode{common_type_t<T, U>}. Let
\tcode{t} be a function whose return type is \tcode{T}, and let \tcode{u} be a function
whose return type is \tcode{U}. \tcode{Common<T, U>} is satisfied only if:
\begin{itemize}
\item \tcode{C(t())} equals \tcode{C(t())} if and only if
  \tcode{t()} is an equality preserving
  expression~(\ref{concepts.lib.general.equality}).
\item \tcode{C(u())} equals \tcode{C(u())} if and only if
  \tcode{u()} is an equality preserving
  expression~(\ref{concepts.lib.general.equality}).
\end{itemize}

\pnum
\enternote Users can customize the behavior of \tcode{Common} by specializing the \tcode{common_type}
class template~(\ref{meta.unary.prop}).\exitnote

\end{itemdescr}

\rSec2[concepts.lib.corelang.integral]{Concept \tcode{Integral}}

\indexlibrary{\idxcode{Integral}}%
\begin{itemdecl}
template <class T>
concept bool Integral = is_integral<T>::value; // \seebelow
\end{itemdecl}

\begin{itemdescr}
\pnum
There need not be any subsumption relationship between \tcode{Integral<T>} and
\tcode{is_integral<T>\colcol{}value}.
\end{itemdescr}

\rSec2[concepts.lib.corelang.signedintegral]{Concept \tcode{SignedIntegral}}

\indexlibrary{\idxcode{SignedIntegral}}%
\begin{itemdecl}
template <class T>
concept bool SignedIntegral = Integral<T> && is_signed<T>::value; // \seebelow
\end{itemdecl}

\begin{itemdescr}
\pnum
There need not be any subsumption relationship between \tcode{SignedIntegral<T>} and
\tcode{is_signed<T>::\brk{}value}.

\pnum
\enternote \tcode{SignedIntegral<T>} may be satisfied even for
types that are not signed integral types~(\cxxref{basic.fundamental});
for example, \tcode{char}.
\exitnote
\end{itemdescr}

\rSec2[concepts.lib.corelang.unsignedintegral]{Concept \tcode{UnsignedIntegral}}

\indexlibrary{\idxcode{UnsignedIntegral}}%
\begin{itemdecl}
template <class T>
concept bool UnsignedIntegral = Integral<T> && !SignedIntegral<T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\enternote \tcode{UnsignedIntegral<T>} may be satisfied even for
types that are not unsigned integral types~(\cxxref{basic.fundamental});
for example, \tcode{char}.
\exitnote
\end{itemdescr}

\rSec2[concepts.lib.corelang.assignable]{Concept \tcode{Assignable}}

\indexlibrary{\idxcode{Assignable}}%
\begin{itemdecl}
template <class T, class U>
concept bool Assignable =
  is_lvalue_reference<T>::value && // \seebelow
  CommonReference<
    const remove_reference_t<T>&,
    const remove_reference_t<U>&> &&
  requires(T t, U&& u) {
    { t = std::forward<U>(u) } -> Same<T>&&;
  };
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{t} be an lvalue that refers to an object \tcode{o} such that
\tcode{decltype((t))} is \tcode{T}, and \tcode{u} an expression such that
\tcode{decltype((u))} is \tcode{U}. Let \tcode{u2} be a distinct object that is
equal to \tcode{u}. \tcode{Assignable<T, U>} is satisfied only if

\begin{itemize}
\item \tcode{addressof(t = u) == addressof(o)}.

\item After evaluating \tcode{t = u}:

\begin{itemize}
\item \tcode{t} is equal to \tcode{u2}, unless \tcode{u} is a non-const xvalue that refers to \tcode{o}.

\item If \tcode{u} is a non-\tcode{const} xvalue, the resulting state of the
object to which it refers is valid but unspecified~(\cxxref{lib.types.movedfrom}).

\item Otherwise, if \tcode{u} is a glvalue, the object to which it refers is not
modified.
\end{itemize}
\end{itemize}

\pnum
There need not be any subsumption relationship between \tcode{Assignable<T, U>}
and \tcode{is_\-lval\-ue_\-ref\-er\-ence<T>::\brk{}value}.

\pnum
\enternote Assignment need not be a total function~(\ref{structure.requirements});
in particular, if assignment to an object \tcode{x} can result in a modification
of some other object \tcode{y}, then \tcode{x = y} is likely not in the domain
of \tcode{=}. \exitnote
\end{itemdescr}

\rSec2[concepts.lib.corelang.swappable]{Concept \tcode{Swappable}}

\indexlibrary{\idxcode{Swappable}}%
\begin{itemdecl}
template <class T>
concept bool Swappable =
  requires(T& a, T& b) {
    ranges::swap(a, b);
  };

template <class T, class U>
concept bool SwappableWith =
  CommonReference<
    const remove_reference_t<T>&,
    const remove_reference_t<U>&> &&
  requires(T&& t, U&& u) {
    ranges::swap(std::forward<T>(t), std::forward<T>(t));
    ranges::swap(std::forward<U>(u), std::forward<U>(u));
    ranges::swap(std::forward<T>(t), std::forward<U>(u));
    ranges::swap(std::forward<U>(u), std::forward<T>(t));
  };
\end{itemdecl}

\begin{itemdescr}
\pnum
This subclause provides definitions for swappable types and expressions. In these
definitions, let \tcode{t} denote an expression of type \tcode{T}, and let \tcode{u}
denote an expression of type \tcode{U}.

\pnum
An object \tcode{t} is \defn{swappable with} an object \tcode{u} if and only if
\tcode{SwappableWith<T, U>} is satisfied. \tcode{Swappable\-With<T, U>} is satisfied
only if given distinct objects \tcode{t2} equal to \tcode{t}
and \tcode{u2} equal to \tcode{u}, after evaluating either
\tcode{ranges::swap(t, u)} or \tcode{ranges::swap(u, t)}, \tcode{t2} is equal to
\tcode{u} and \tcode{u2} is equal to \tcode{t}.

\pnum
An rvalue or lvalue \tcode{t} is \defn{swappable} if and only if \tcode{t} is
swappable with any rvalue or lvalue, respectively, of type \tcode{T}.

\enterexample User code can ensure that the evaluation of \tcode{swap} calls
is performed in an appropriate context under the various conditions as follows:
\begin{codeblock}
#include <utility>

// Requires: \tcode{std::forward<T>(t)} shall be swappable with \tcode{std::forward<U>(u)}.
template <class T, class U>
void value_swap(T&& t, U&& u) {
  using std::experimental::ranges::swap;
  swap(std::forward<T>(t), std::forward<U>(u));         // OK: uses ``swappable with'' conditions
                                                        // for rvalues and lvalues
}

// Requires: lvalues of \tcode{T} shall be swappable.
template <class T>
void lv_swap(T& t1, T& t2) {
  using std::experimental::ranges::swap;
  swap(t1, t2);                                         // OK: uses swappable conditions for
}                                                       // lvalues of type \tcode{T}

namespace N {
  struct A { int m; };
  struct Proxy { A* a; };
  Proxy proxy(A& a) { return Proxy{ &a }; }

  void swap(A& x, Proxy p) {
    std::experimental::ranges::swap(x.m, p.a->m);  // OK: uses context equivalent to swappable
                                                   // conditions for fundamental types
  }
  void swap(Proxy p, A& x) { swap(x, p); }         // satisfy symmetry constraint
}

int main() {
  int i = 1, j = 2;
  lv_swap(i, j);
  assert(i == 2 && j == 1);

  N::A a1 = { 5 }, a2 = { -5 };
  value_swap(a1, proxy(a2));
  assert(a1.m == -5 && a2.m == 5);
}
\end{codeblock}
\exitexample
\end{itemdescr}

\rSec2[concepts.lib.corelang.destructible]{Concept \tcode{Destructible}}

\pnum
The \tcode{Destructible} concept specifies properties of all types, instances of
which can be destroyed at the end of their lifetime, or reference types.

\indexlibrary{\idxcode{Destructible}}%
\begin{itemdecl}
template <class T>
concept bool Destructible = is_nothrow_destructible<T>::value; // \seebelow
\end{itemdecl}

\begin{itemdescr}
\pnum
There need not be any subsumption relationship between \tcode{Destructible<T>}
and \tcode{is_\-no\-throw_\-destruct\-ible<T>::value}.

\pnum
\enternote Unlike the \tcode{Destructible} library concept in the \Cpp
Standard~(\cxxref{utility.arg.requirements}), this concept forbids destructors
that are \tcode{noexcept(false)}, even if non-throwing. \exitnote
\end{itemdescr}

\rSec2[concepts.lib.corelang.constructible]{Concept \tcode{Constructible}}

\pnum
The \tcode{Constructible} concept constrains the initialization of a variable of
a type with a given set of argument types.

\indexlibrary{\idxcode{Constructible}}%
\begin{itemdecl}
template <class T, class... Args>
concept bool Constructible =
  Destructible<T> && is_constructible<T, Args...>::value; // \seebelow
\end{itemdecl}

\begin{itemdescr}
\pnum
There need not be any subsumption relationship between \tcode{Constructible<T, Args...>}
and \tcode{is_constructible<T, Args...>::value}.
\end{itemdescr}

\rSec2[concepts.lib.corelang.defaultconstructible]{Concept \tcode{DefaultConstructible}}

\indexlibrary{\idxcode{DefaultConstructible}}%
\begin{itemdecl}
template <class T>
concept bool DefaultConstructible = Constructible<T>;
\end{itemdecl}

\rSec2[concepts.lib.corelang.moveconstructible]{Concept \tcode{MoveConstructible}}

\indexlibrary{\idxcode{MoveConstructible}}%
\begin{itemdecl}
template <class T>
concept bool MoveConstructible =
  Constructible<T, T> && ConvertibleTo<T, T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
If \tcode{T} is an object type, then let \tcode{rv} be an rvalue of type \tcode{T}
and \tcode{u2} a distinct object of type \tcode{T} equal to \tcode{rv}.
\tcode{MoveConstructible<T>} is satisfied only if

\begin{itemize}
\item After the definition \tcode{T u = rv;}, \tcode{u} is equal to \tcode{u2}.

\item \tcode{T\{rv\}} is equal to \tcode{u2}.

\item If \tcode{T} is not \tcode{const}, \tcode{rv}'s resulting state is valid
but unspecified~(\cxxref{lib.types.movedfrom}); otherwise, it is unchanged.
\end{itemize}
\end{itemdescr}

\rSec2[concepts.lib.corelang.copyconstructible]{Concept \tcode{CopyConstructible}}

\indexlibrary{\idxcode{CopyConstructible}}%
\begin{itemdecl}
template <class T>
concept bool CopyConstructible =
  MoveConstructible<T> &&
  Constructible<T, T&> && ConvertibleTo<T&, T> &&
  Constructible<T, const T&> && ConvertibleTo<const T&, T> &&
  Constructible<T, const T> && ConvertibleTo<const T, T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
If \tcode{T} is an object type, then let \tcode{v} be an lvalue of type (possibly
\tcode{const}) \tcode{T} or an rvalue of type \tcode{const T}.
\tcode{CopyConstructible<T>} is satisfied only if

\begin{itemize}
\item After the definition \tcode{T u = v;}, \tcode{u} is equal to \tcode{v}.

\item \tcode{T\{v\}} is equal to \tcode{v}.
\end{itemize}

\end{itemdescr}

\rSec1[concepts.lib.compare]{Comparison concepts}

\rSec2[concepts.lib.compare.general]{General}

\pnum
This section describes concepts that establish relationships and orderings
on values of possibly differing object types.

\rSec2[concepts.lib.compare.boolean]{Concept \tcode{Boolean}}

\pnum
The \tcode{Boolean} concept specifies the requirements on a type that is usable in Boolean contexts.

\indexlibrary{\idxcode{Boolean}}%
\begin{itemdecl}
template <class B>
concept bool Boolean =
  Movable<decay_t<B>> && // (see \ref{concepts.lib.object.movable})
  requires(const remove_reference_t<B>& b1,
           const remove_reference_t<B>& b2, const bool a) {
    { b1 }       -> ConvertibleTo<bool>&&;
    { !b1 }      -> ConvertibleTo<bool>&&;
    { b1 && a }  -> Same<bool>&&;
    { b1 || a }  -> Same<bool>&&;
    { b1 && b2 } -> Same<bool>&&;
    { a && b2  } -> Same<bool>&&;
    { b1 || b2 } -> Same<bool>&&;
    { a || b2  } -> Same<bool>&&;
    { b1 == b2 } -> ConvertibleTo<bool>&&;
    { b1 == a  } -> ConvertibleTo<bool>&&;
    { a == b2  } -> ConvertibleTo<bool>&&;
    { b1 != b2 } -> ConvertibleTo<bool>&&;
    { b1 != a  } -> ConvertibleTo<bool>&&;
    { a != b2  } -> ConvertibleTo<bool>&&;
  };
\end{itemdecl}

\pnum
Given \tcode{const} lvalues \tcode{b1} and \tcode{b2} of type
\tcode{remove_reference_t<B>}, then \tcode{Boolean<B>} is satisfied only if

\begin{itemize}
\item \tcode{bool(b1) == !bool(!b1)}.
\item \tcode{(b1 \&\& b2)}, \tcode{(b1 \&\& bool(b2))}, and
      \tcode{(bool(b1) \&\& b2)} are all equal to
      \tcode{(bool(b1) \&\& bool(b2))}, and have the same short-circuit evaluation.
\item \tcode{(b1 || b2)}, \tcode{(b1 || bool(b2))}, and
      \tcode{(bool(b1) || b2)} are all equal to
      \tcode{(bool(b1) || bool(b2))}, and have the same short-circuit evaluation.
\item \tcode{bool(b1 == b2)}, \tcode{bool(b1 == bool(b2))}, and
      \tcode{bool(bool(b1) == b2)} are all equal to \tcode{(bool(b1) == bool(b2))}.
\item \tcode{bool(b1 != b2)}, \tcode{bool(b1 != bool(b2))}, and
      \tcode{bool(bool(b1) != b2)} are all equal to \tcode{(bool(b1) != bool(b2))}.
\end{itemize}

\pnum \enterexample The types \tcode{bool}, \tcode{std::true_type}, and
\tcode{std::bitset<$N$>::reference} are \tcode{Boolean} types.
Pointers, smart pointers, and types with explicit conversions to \tcode{bool} are
not \tcode{Boolean} types.\exitexample

\rSec2[concepts.lib.compare.equalitycomparable]{Concept \tcode{EqualityComparable}}

\indexlibrary{\idxcode{WeaklyEqualityComparableWith}}%
\begin{itemdecl}
template <class T, class U>
concept bool WeaklyEqualityComparableWith =
  requires(const remove_reference_t<T>& t,
           const remove_reference_t<U>& u) {
    { t == u } -> Boolean&&;
    { t != u } -> Boolean&&;
    { u == t } -> Boolean&&;
    { u != t } -> Boolean&&;
  };
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{t} and \tcode{u} be \tcode{const} lvalues of types
\tcode{remove_reference_t<T>} and \tcode{remove_reference_t<U>} respectively.
\tcode{Weakly\-Equality\-Comparable\-With<T, U>} is satisfied only if:
\begin{itemize}
\item \tcode{t == u}, \tcode{u == t}, \tcode{t != u}, and \tcode{u != t}
      have the same domain.
\item \tcode{bool(u == t) == bool(t == u)}.
\item \tcode{bool(t != u) == !bool(t == u)}.
\item \tcode{bool(u != t) == bool(t != u)}.
\end{itemize}
\end{itemdescr}

\indexlibrary{\idxcode{EqualityComparable}}%
\begin{itemdecl}
template <class T>
concept bool EqualityComparable = WeaklyEqualityComparableWith<T, T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{a} and \tcode{b} be objects of type \tcode{T}.
\tcode{EqualityComparable<T>} is satisfied only if:

\begin{itemize}
\item \tcode{bool(a == b)} if and only if \tcode{a} is equal to \tcode{b}.
\end{itemize}

\pnum
\enternote The requirement that the expression \tcode{a == b} is equality preserving
implies that \tcode{==} is reflexive, transitive, and symmetric.\exitnote
\end{itemdescr}

\indexlibrary{\idxcode{EqualityComparableWith}}%
\begin{itemdecl}
template <class T, class U>
concept bool EqualityComparableWith =
  EqualityComparable<T> &&
  EqualityComparable<U> &&
  CommonReference<
    const remove_reference_t<T>&,
    const remove_reference_t<U>&> &&
  EqualityComparable<
    common_reference_t<
      const remove_reference_t<T>&,
      const remove_reference_t<U>&>> &&
  WeaklyEqualityComparableWith<T, U>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{t} be a \tcode{const} lvalue of type \tcode{remove_reference_t<T>}, \tcode{u} be a
\tcode{const} lvalue of type \tcode{remove_reference_t<U>}, and \tcode{C} be:
\begin{codeblock}
common_reference_t<const remove_reference_t<T>&, const remove_reference_t<U>&>
\end{codeblock}
\tcode{EqualityComparableWith<T, U>} is satisfied only if:

\begin{itemize}
\item \tcode{bool(t == u) == bool(C(t) == C(u))}.
\end{itemize}
\end{itemdescr}

\rSec2[concepts.lib.compare.stricttotallyordered]{Concept \tcode{StrictTotallyOrdered}}

\indexlibrary{\idxcode{StrictTotallyOrdered}}%
\begin{itemdecl}
template <class T>
concept bool StrictTotallyOrdered =
  EqualityComparable<T> &&
  requires(const remove_reference_t<T>& a,
           const remove_reference_t<T>& b) {
    { a < b }  -> Boolean&&;
    { a > b }  -> Boolean&&;
    { a <= b } -> Boolean&&;
    { a >= b } -> Boolean&&;
  };
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{a}, \tcode{b}, and \tcode{c} be \tcode{const} lvalues of type \tcode{remove_reference_t<T>}.
\tcode{StrictTotallyOrdered<T>} is satisfied only if

\begin{itemize}
\item Exactly one of \tcode{bool(a < b)}, \tcode{bool(a > b)}, or
      \tcode{bool(a == b)} is \tcode{true}.
\item If \tcode{bool(a < b)} and \tcode{bool(b < c)}, then
      \tcode{bool(a < c)}.
\item \tcode{bool(a > b) == bool(b < a)}.
\item \tcode{bool(a <= b) == !bool(b < a)}.
\item \tcode{bool(a >= b) == !bool(a < b)}.
\end{itemize}

\end{itemdescr}

\begin{itemdecl}
template <class T, class U>
concept bool StrictTotallyOrderedWith =
  StrictTotallyOrdered<T> &&
  StrictTotallyOrdered<U> &&
  CommonReference<
    const remove_reference_t<T>&,
    const remove_reference_t<U>&> &&
  StrictTotallyOrdered<
    common_reference_t<
      const remove_reference_t<T>&,
      const remove_reference_t<U>&>> &&
  EqualityComparableWith<T, U> &&
  requires(const remove_reference_t<T>& t,
           const remove_reference_t<U>& u) {
    { t < u }  -> Boolean&&;
    { t > u }  -> Boolean&&;
    { t <= u } -> Boolean&&;
    { t >= u } -> Boolean&&;
    { u < t }  -> Boolean&&;
    { u > t }  -> Boolean&&;
    { u <= t } -> Boolean&&;
    { u >= t } -> Boolean&&;
  };
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{t} be a \tcode{const} lvalue of type \tcode{remove_reference_t<T>},
\tcode{u} be a \tcode{const} lvalue of type \tcode{remove_reference_t<U>},
and \tcode{C} be:
\begin{codeblock}
common_reference_t<const remove_reference_t<T>&, const remove_reference_t<U>&>
\end{codeblock}
\tcode{StrictTotallyOrderedWith<T, U>} is satisfied only if

\begin{itemize}
\item \tcode{bool(t < u) == bool(C(t) < C(u)).}
\item \tcode{bool(t > u) == bool(C(t) > C(u)).}
\item \tcode{bool(t <= u) == bool(C(t) <= C(u)).}
\item \tcode{bool(t >= u) == bool(C(t) >= C(u)).}
\item \tcode{bool(u < t) == bool(C(u) < C(t)).}
\item \tcode{bool(u > t) == bool(C(u) > C(t)).}
\item \tcode{bool(u <= t) == bool(C(u) <= C(t)).}
\item \tcode{bool(u >= t) == bool(C(u) >= C(t)).}
\end{itemize}
\end{itemdescr}

\rSec1[concepts.lib.object]{Object concepts}

\pnum
This section describes concepts that specify the basis of the
value-oriented programming style on which the library is based.
%% object types (See the rationale in Appendix~\ref{decomposition}).}

\rSec2[concepts.lib.object.movable]{Concept \tcode{Movable}}

\indexlibrary{\idxcode{Movable}}%
\begin{itemdecl}
template <class T>
concept bool Movable =
  is_object<T>::value &&
  MoveConstructible<T> &&
  Assignable<T&, T> &&
  Swappable<T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
There need not be any subsumption relationship between \tcode{Movable<T>} and
\tcode{is_object<T>::value}.
\end{itemdescr}

\rSec2[concepts.lib.object.copyable]{Concept \tcode{Copyable}}

\indexlibrary{\idxcode{Copyable}}%
\begin{itemdecl}
template <class T>
concept bool Copyable =
  CopyConstructible<T> &&
  Movable<T> &&
  Assignable<T&, const T&>;
\end{itemdecl}

\rSec2[concepts.lib.object.semiregular]{Concept \tcode{Semiregular}}

\indexlibrary{\idxcode{Semiregular}}%
\begin{itemdecl}
template <class T>
concept bool Semiregular =
  Copyable<T> &&
  DefaultConstructible<T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\enternote The \tcode{Semiregular} concept is satisfied by types that
behave similarly to built-in types like \tcode{int}, except that they may not be
comparable with \tcode{==}.\exitnote
\end{itemdescr}

\rSec2[concepts.lib.object.regular]{Concept \tcode{Regular}}

\indexlibrary{\idxcode{Regular}}%
\begin{itemdecl}
template <class T>
concept bool Regular =
  Semiregular<T> &&
  EqualityComparable<T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
\enternote The \tcode{Regular} concept is satisfied by types that behave
similarly to built-in types like \tcode{int} and that are comparable with \tcode{==}.\exitnote
\end{itemdescr}

\rSec1[concepts.lib.callable]{Callable concepts}

\rSec2[concepts.lib.callable.general]{General}

\pnum
The concepts in this section describe the requirements on function
objects~(\ref{function.objects}) and their arguments.

\rSec2[concepts.lib.callable.invocable]{Concept \tcode{Invocable}}

\pnum
The \tcode{Invocable} concept specifies a relationship between a callable
type~(\cxxref{func.def}) \tcode{F} and a set of argument types \tcode{Args...} which
can be evaluated by the library function \tcode{invoke}~(\ref{func.invoke}).

\indexlibrary{\idxcode{Invocable}}%
\begin{itemdecl}
template <class F, class... Args>
concept bool Invocable =
  requires(F&& f, Args&&... args) {
    invoke(std::forward<F>(f), std::forward<Args>(args)...); // not required to be equality preserving
  };
\end{itemdecl}

\begin{itemdescr}
\pnum
\enternote Since the \tcode{invoke} function call
expression is not required to be
equality-preserving~(\ref{concepts.lib.general.equality}), a function that generates random numbers
may satisfy \tcode{Invocable}.\exitnote
\end{itemdescr}

\rSec2[concepts.lib.callable.regularinvocable]{Concept \tcode{RegularInvocable}}

\indexlibrary{\idxcode{RegularInvocable}}%
\begin{itemdecl}
template <class F, class... Args>
concept bool RegularInvocable =
  Invocable<F, Args...>;
\end{itemdecl}

\begin{itemdescr}
\pnum
The \tcode{invoke} function call expression shall be equality-preserving and
shall not modify the function object or the arguments~(\ref{concepts.lib.general.equality}).
\enternote This requirement supersedes the
annotation in the definition of \tcode{Invocable}. \exitnote

\pnum
\enternote A random number generator does not satisfy
\tcode{RegularInvocable}.\exitnote

\pnum
\enternote The distinction between \tcode{Invocable} and
\tcode{RegularInvocable} is purely semantic.\exitnote
\end{itemdescr}

\rSec2[concepts.lib.callable.predicate]{Concept \tcode{Predicate}}

\indexlibrary{\idxcode{Predicate}}%
\begin{itemdecl}
template <class F, class... Args>
concept bool Predicate =
  RegularInvocable<F, Args...> &&
  Boolean<result_of_t<F&&(Args&&...)>>;
\end{itemdecl}

\rSec2[concepts.lib.callable.relation]{Concept \tcode{Relation}}

\indexlibrary{\idxcode{Relation}}%
\begin{itemdecl}
template <class R, class T, class U>
concept bool Relation =
  Predicate<R, T, T> &&
  Predicate<R, U, U> &&
  CommonReference<
    const remove_reference_t<T>&,
    const remove_reference_t<U>&> &&
  Predicate<R,
    common_reference_t<
      const remove_reference_t<T>&,
      const remove_reference_t<U>&>,
    common_reference_t<
      const remove_reference_t<T>&,
      const remove_reference_t<U>&>> &&
  Predicate<R, T, U> &&
  Predicate<R, U, T>;
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{r} be an expression such that \tcode{decltype((r))} is \tcode{R},
\tcode{t} be an expression such that \tcode{decltype((t))} is \tcode{T},
\tcode{u} be an expression such that \tcode{decltype((u))} is \tcode{U},
and \tcode{C} be \tcode{common_reference_t<const remove_reference_t<T>\&,
const remove_reference_t<U>\&>}.
\tcode{Relation<R, T, U>} is satisfied only if

\begin{itemize}
\item \tcode{bool(r(t, u)) == bool(r(C(t), C(u))).}
\item \tcode{bool(r(u, t)) == bool(r(C(u), C(t))).}
\end{itemize}
\end{itemdescr}

\rSec2[concepts.lib.callable.strictweakorder]{Concept \tcode{StrictWeakOrder}}

\indexlibrary{\idxcode{Relation}}%
\begin{itemdecl}
template <class R, class T, class U>
concept bool StrictWeakOrder = Relation<R, T, U>;
\end{itemdecl}

\begin{itemdescr}
\pnum
A \tcode{Relation} satisfies \tcode{StrictWeakOrder} only if
it imposes a \techterm{strict weak ordering} on its arguments.

\pnum
The term
\techterm{strict}
refers to the
requirement of an irreflexive relation (\tcode{!comp(x, x)} for all \tcode{x}),
and the term
\techterm{weak}
to requirements that are not as strong as
those for a total ordering,
but stronger than those for a partial
ordering.
If we define
\tcode{equiv(a, b)}
as
\tcode{!comp(a, b) \&\& !comp(b, a)},
then the requirements are that
\tcode{comp}
and
\tcode{equiv}
both be transitive  relations:

\begin{itemize}
\item
\tcode{comp(a, b) \&\& comp(b, c)}
implies
\tcode{comp(a, c)}
\item
\tcode{equiv(a, b) \&\& equiv(b, c)}
implies
\tcode{equiv(a, c)}
\enternote
Under these conditions, it can be shown that
\begin{itemize}
\item
\tcode{equiv}
is an equivalence relation
\item
\tcode{comp}
induces a well-defined relation on the equivalence
classes determined by
\tcode{equiv}
\item
The induced relation is a strict total ordering.
\exitnote
\end{itemize}
\end{itemize}
\end{itemdescr}