concepts.tex

%!TEX root = std.tex

\begin{addedblock}
\setcounter{chapter}{18}
\rSec0[concepts.lib]{Concepts library}

\ednote{This chapter is inserted between the chapters [language.support] and [diagnostics]. All
subsequence chapters should be renumbered as appropriate, but they aren't here for the sake of
simplicity).}

\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_v1/concepts>}      \\
\ref{concepts.lib.compare}    & Comparison concepts            &                      \\
\ref{concepts.lib.object}     & Object concepts                &                      \\
\ref{concepts.lib.functions}  & Function concepts              &                      \\
\end{libsumtab}

\pnum
In this Clause, \tcode{CamelCase} identifiers ending with ``\tcode{Type}'' denote
\oldtxt{template aliases}\newtxt{alias templates}.

\pnum
The concepts in this Clause are defined in the namespace \tcode{std::experimental::ranges_v1}.

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

\pnum
An expression is \techterm{equality preserving} if, given equal inputs, the expression results in
equal outputs. \newtxt{The inputs to an expression is the set of the expression's operands. The
output of an expression is the expression's result and all operands modified by the expression.}
\enternote 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. \exitnote

\pnum
A \techterm{regular function} is a function that is equality preserving,
i.e., a function that returns equal output when passed equal input. A regular
function that returns a value may copy or move the returned object, or may return a
reference. \enternote Regular functions may have side effects. \exitnote

\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 \oldtxt{the same results}\newtxt{equal outputs} absent any
\newtxt{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 \techterm{requires-expression} in this document are
required to be equality preserving, except for those annotated with the comment
``not \newtxt{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 \techterm{requires-expression} modify \oldtxt{what}\newtxt{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 \techterm{requires-expression} declares an expression that is non-modifying
for some constant lvalue operand, additional variants 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 variant is explicitly required with
differing semantics. Such implicit expression variants must meet the semantic
requirements of the declared expression. The extent to which an implementation
validates the syntax of these implicit expression variants is unspecified.

\ednote{The motivation for this relaxation of syntactic checking is to avoid an exponential
blow-up in the concept definitions and in compile times that would be required to check every
permutation of cv-qualification and value category for expression operands.}

\enterexample
\begin{codeblock}
template <class T>
concept bool C() {
  return 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 variants 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 variants 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 variant with a
non-constant rvalue second operand, since expression \#2 already specifies exactly
such an expression explicitly.
\exitexample

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

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

\oldtxt{Since }\tcode{T} fails to \oldtxt{satisfy}\newtxt{meet} the implicit
requirements of \tcode{C}, so \tcode{C<T>()} is not satisfied\oldtxt{ in principle}.
\oldtxt{Whether it is satisfied in practice is undefined.} \newtxt{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.corelang]{Core language concepts}

\rSec2[concepts.lib.corelang.general]{In 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 Same}

\indexlibrary{\idxcode{Same}}%
\begin{itemdecl}
template <class T, class U>
concept bool Same() {
  return @\seebelow@;
}
\end{itemdecl}

\begin{itemdescr}
\pnum
\tcode{Same<T, U>\newtxt{()}} is \oldtxt{an alias for \tcode{true} when}\newtxt{satisfied if and
only if} \tcode{T} and \tcode{U} denote the same type\oldtxt{ after the elimination of aliases;
otherwise, it is an alias for \tcode{false}}.

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

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

\indexlibrary{\idxcode{DerivedFrom}}%
\begin{itemdecl}
template <class T, class U>
concept bool Derived@\newtxt{From}@() {
  return @\seebelow@;
}
\end{itemdecl}

\begin{itemdescr}
\pnum
\tcode{Derived\newtxt{From}<T, U>\newtxt{()}} \oldtxt{has the same value as}\newtxt{is satisfied if and only if}
\tcode{is_base_of<U, T>::value}\newtxt{ is \tcode{true}}.
\end{itemdescr}

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

\indexlibrary{\idxcode{ConvertibleTo}}%
\begin{itemdecl}
template <class T, class U>
concept bool Convertible@\newtxt{To}@() {
  return @\seebelow@;
}
\end{itemdecl}

\begin{itemdescr}
\pnum
\tcode{Convertible\newtxt{To}<T, U>\newtxt{()}} \oldtxt{has the same value as}\newtxt{is satisfied
if and only if} \tcode{is_convertible<T, U>::value}\newtxt{ is \tcode{true}}.
\end{itemdescr}

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

\pnum
If \tcode{T} and \tcode{U} can both be explicitly converted to \oldtxt{a}\newtxt{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
\oldtxt{Informally, two types \tcode{T} and \tcode{U}
model the \tcode{Common} concept when the type alias \tcode{CommonType<T, U>}
is well-formed and names a common type of \tcode{T} and \tcode{U}.}

\indexlibrary{\idxcode{Common}}%
\begin{itemdecl}
template <class T, class U>
using CommonType = common_type_t<T, U>;

template <class T, class U>
concept bool Common() {
  return requires (T t, U u) {
    typename CommonType<T, U>;
    typename CommonType<U, T>;
    requires Same<CommonType<U, T>, CommonType<T, U>>();
    CommonType<T, U>(std::forward<T>(t));
    CommonType<T, U>(std::forward<U>(u));
  };
}
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{C} be \tcode{CommonType<T, U>}. Let \tcode{t1} and \tcode{t2} be objects
of type \tcode{T}, and \tcode{u1} and \tcode{u2} be objects of type \tcode{U}.
\oldtxt{The types \tcode{T} and \tcode{U} model }\tcode{Common\newtxt{<T, U>()}}
\newtxt{is satisfied} if and only if
\begin{itemize}
\item \tcode{C(t1)} equals \tcode{C(t2)} if and only if \tcode{t1} equals \tcode{t2}.
\item \tcode{C(u1)} equals \tcode{C(u2)} if and only if \tcode{u1} equals \tcode{u2}.
\end{itemize}

\pnum
\enternote Users are free to specialize \tcode{common_type} when at least one parameter is a
user-defined type. Those specializations are considered by the \tcode{Common} concept.\exitnote

\end{itemdescr}

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

\indexlibrary{\idxcode{Integral}}%
\begin{itemdecl}
template <class T>
concept bool Integral@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ is_integral<T>::value;
@\newtxt{\}}@
\end{itemdecl}

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

\indexlibrary{\idxcode{SignedIntegral}}%
\begin{itemdecl}
template <class T>
concept bool SignedIntegral@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ Integral<T>@\newtxt{()}@ && is_signed<T>::value;
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
\enternote \tcode{SignedIntegral<T>\newtxt{()}} may be \oldtxt{true}\newtxt{satisfied} even for
types that are not signed integral types~(\cxxref{basic.fundamental}).
\exitnote
\end{itemdescr}

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

\indexlibrary{\idxcode{UnsignedIntegral}}%
\begin{itemdecl}
template <class T>
concept bool UnsignedIntegral@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ Integral<T>@\newtxt{()}@ && !SignedIntegral<T>@\newtxt{()}@;
@\newtxt{\}}@
\end{itemdecl}

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

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

\indexlibrary{\idxcode{Assignable}}%
\begin{itemdecl}
template <class T, class U = T>
concept bool Assignable@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ requires(T@\newtxt{\&\&}@ a, U@\newtxt{\&\&}@ b) {
    { std::forward<T>(a) = std::forward<U>(b) } -> Same<T&>;
  };
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{t} be an lvalue of type \tcode{T}. If \tcode{U} is an \newtxt{lvalue} reference type, let \tcode{v}
be a lvalue of type \tcode{U}; otherwise, let \tcode{v} be an rvalue of type \tcode{U}.
Then \oldtxt{types \tcode{T} and \tcode{U} model} \tcode{Assignable\newtxt{<T, U>()}}
\newtxt{is satisfied} if and only if

\begin{itemize}
\item \tcode{\oldtxt{(}std::addressof(t = v) == std::addressof(t)\oldtxt{) != false)}}.
\end{itemize}
\end{itemdescr}

\rSec2[concepts.lib.corelang.swappable]{Concept Swappable}
\ednote{Remove subclause [swappable.requirements]. Replace references to
[swappable.requirements] with [concepts.lib.corelang.swappable].}

\indexlibrary{\idxcode{Swappable}}%
\begin{itemdecl}
template <class T>
concept bool Swappable() {
  return requires(T t, T u) {
    @\newtxt{(void)}@swap(std::forward<T>(t), std::forward<T>(u));
  };
}

template <class T, class U>
concept bool Swappable() {
  return Swappable<T>() &&
    Swappable<U>() &&
    Common<T, U>@\newtxt{()}@ &&
    requires(T t, U u) {
      @\newtxt{(void)}@swap(std::forward<T>(t), std::forward<U>(u));
      @\newtxt{(void)}@swap(std::forward<U>(u), std::forward<T>(t));
    };
}
\end{itemdecl}

\begin{itemdescr}
\pnum
\newtxt{\enternote The casts to \tcode{void} in the required expressions indicate
that the value - if any - of the call to \tcode{swap} does not participate in the
semantics. Callers are effectively forbidden to rely on the return type or value of
a call to \tcode{swap}, and user customizations of \tcode{swap} need not return
equal values when given equal operands. \exitnote}

\ednote{The following is copied almost verbatim from [swappable.requirements]}

\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
\oldtxt{types \tcode{T} and \tcode{U} model} \tcode{Swappable\newtxt{<T, U>()}}
\newtxt{is satisfied}. \oldtxt{Types \tcode{T} and \tcode{U} model}
\tcode{Swappable\newtxt{<T, U>()}} \newtxt{is satisfied} if and only if:

\begin{itemize}
\item the requires clause above is evaluated in the context described below, and

\item these expressions have the following effects:

\begin{itemize}
\item the object referred to by \tcode{t} has the value originally held by \tcode{u} and
\item the object referred to by \tcode{u} has the value originally held by \tcode{t}.
\end{itemize}
\end{itemize}

\pnum
The context in which the requires clause is evaluated shall
ensure that a binary non-member function named ``\tcode{swap}'' is selected via overload
resolution~(\cxxref{over.match}) on a candidate set that includes:

\begin{itemize}
\item the two \tcode{swap} function templates defined in
\tcode{<utility>}~(\ref{utility}) and

\item the lookup set produced by argument-dependent lookup~(\cxxref{basic.lookup.argdep}).
\end{itemize}

\enternote If \tcode{T} and \tcode{U} are both fundamental types or arrays of
fundamental types and the declarations from the header \tcode{<utility>} are in
scope, the overall lookup set described above is equivalent to that of the
qualified name lookup applied to the expression \tcode{std::swap(t, u)} or
\tcode{std::swap(u, t)} as appropriate. \exitnote

\enternote It is unspecified whether a library component that has a swappable
requirement includes the header \tcode{<utility>} to ensure an appropriate
evaluation context. \exitnote

\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::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::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::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}

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

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

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

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

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

\indexlibrary{\idxcode{Boolean}}%
\begin{itemdecl}
template <class B>
concept bool Boolean@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ requires(@\newtxt{const }@B b1, @\newtxt{const }@B b2@\newtxt{, const bool a}@) {
    bool(b1);
    { b1 } -> bool;
    bool(!b1);
    { !b1 } -> bool;
    { b1 && b2 } -> Same<bool>;
    @\newtxt{\{ b1 \&\& a \} -> Same<bool>;}@
    @\newtxt{\{ a \&\& b1 \} -> Same<bool>;}@
    { b1 || b2 } -> Same<bool>;
    @\newtxt{\{ b1 || a \} -> Same<bool>;}@
    @\newtxt{\{ a || b1 \} -> Same<bool>;}@
    @\newtxt{\{ b1 == b2 \} -> bool;}@
    @\newtxt{\{ b1 != b2 \} -> bool;}@
    @\newtxt{\{ b1 == a \} -> bool;}@
    @\newtxt{\{ a == b1 \} -> bool;}@
    @\newtxt{\{ b1 != a \} -> bool;}@
    @\newtxt{\{ a != b1 \} -> bool;}@
  };
@\newtxt{\}}@
\end{itemdecl}

\pnum
Given values \tcode{b1} and \tcode{b2} of type \tcode{B}, then \oldtxt{type \tcode{B} models}
\tcode{Boolean\newtxt{<B>()}} \newtxt{is satisfied} if and only if

\begin{itemize}
\item \tcode{bool(b1) == [](bool x) \{ return x; \}(b1)}.
\item \tcode{bool(b1) == !bool(!b1)}.
\item \tcode{(b1 \&\& b2)}, \tcode{(b1 \&\& bool(b2))}, and
      \tcode{(bool(b1) \&\& b2)} are all \oldtxt{semantically identical}\newtxt{equal} to
      \tcode{(bool(b1) \&\& bool(b2))}, \oldtxt{including}\newtxt{and have the same} short-circuit evaluation.
\item \tcode{(b1 || b2)}, \tcode{(b1 || bool(b2))}, and
      \tcode{(bool(b1) || b2)} are all \oldtxt{semantically identical}\newtxt{equal} to
      \tcode{(bool(b1) || bool(b2))}, \oldtxt{including}\newtxt{and have the same} short-circuit evaluation.
\item \newtxt{\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 \newtxt{\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<\newtxt{$N$}>::reference} are \tcode{Boolean} types.\exitexample

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

\ednote{Remove table [equalitycomparable] in [utility.arg.requirements]. Replace references to
[equalitycomparable] with [concepts.lib\newtxt{.compare}.equalitycomparable].}

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

\begin{itemdescr}
\pnum
Let \tcode{a}\oldtxt{,} \newtxt{and} \tcode{b}\oldtxt{, and \tcode{c}} be well-formed objects
of type \tcode{T}. \oldtxt{Then type \tcode{T} models} \tcode{EqualityComparable\newtxt{<T>()}}
\newtxt{is satisfied} if and only if

\begin{itemize}
\item \tcode{\newtxt{bool}(a == a)\oldtxt{ != false}}.
\item \tcode{\newtxt{bool}(a == b)\oldtxt{ != false}} if and only if \tcode{a} is equal to \tcode{b}.
\item \oldtxt{\tcode{(a == b) != false} if and only if \tcode{(b == a) != false}.}
\item \newtxt{\tcode{bool(a != b) == !bool(a == b)}}.
\item \oldtxt{\tcode{(a != b) != false} if and only if \tcode{(a == b) == false}}.
\item \oldtxt{\tcode{(a == b) != false \&\& (b == c) != false} if and only if \tcode{(a == c) != false}.}
\end{itemize}

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

\pnum
\enternote Not all arguments will be well-formed for a given type. For example, $NaN$ is not a
well-formed floating point value, and many types' moved-from states are not well-formed. This
does not mean that the type does not \oldtxt{model}\newtxt{satisfy} \tcode{EqualityComparable}.\exitnote
\end{itemdescr}

\begin{itemdecl}
template <class T, class U>
concept bool EqualityComparable() {
  return Common<T, U>@\newtxt{()}@ &&
    EqualityComparable<T>() &&
    EqualityComparable<U>() &&
    EqualityComparable<CommonType<T, U>>() &&
    requires(@\newtxt{const }@T a, @\newtxt{const }@U b) {
      {a == b} -> Boolean;
      {b == a} -> Boolean;
      {a != b} -> Boolean;
      {b != a} -> Boolean;
    };
}
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{a} be an object of type \tcode{T}, \tcode{b} be an object of type \tcode{U}, and \tcode{C} be
\tcode{CommonType<T, U>}. Then \oldtxt{types \tcode{T} and \tcode{U} model}
\tcode{EqualityComparable\newtxt{<T, U>()}} \newtxt{is satisfied} if and only if

\begin{itemize}
\item \newtxt{\tcode{bool(a == b) == bool(C(a) == C(b))}.}
\item \oldtxt{\tcode{(a == b) != false} if and only if \tcode{(C(a) == C(b)) != false}.}
\item \newtxt{\tcode{bool(a != b) == bool(C(a) != C(b))}.}
\item \oldtxt{\tcode{(a != b) != false} if and only if \tcode{(C(a) != C(b)) != false}.}
\item \newtxt{\tcode{bool(b == a) == bool(C(b) == C(a))}.}
\item \oldtxt{\tcode{(b == a) != false} if and only if \tcode{(C(b) == C(a)) != false}.}
\item \newtxt{\tcode{bool(b != a) == bool(C(b) != C(a))}.}
\item \oldtxt{\tcode{(b != a) != false} if and only if \tcode{(C(b) != C(a)) != false}.}
\end{itemize}
\end{itemdescr}

\ednote{BUGBUG There is concern on the committee that the \tcode{Common} requirement is
overconstraining here. (In \tcode{Relation} too.}

\rSec2[concepts.lib.compare.totallyordered]{Concept TotallyOrdered}

\ednote{Remove table [lessthancomparable] in [utility.arg.requirements]. Replace uses of
\tcode{LessThanComparable} with \tcode{TotallyOrdered} (acknowledging that this is a breaking
change that makes type requirements stricter). Replace references to [lessthancomparable] with
references to [concepts.lib\newtxt{.compare}.totallyordered]}

\indexlibrary{\idxcode{TotallyOrdered}}%
\begin{itemdecl}
template <class T>
concept bool TotallyOrdered() {
  return EqualityComparable<T>() &&
    requires (@\newtxt{const }@T a, @\newtxt{const }@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 well-formed objects of type \tcode{T}. Then \oldtxt{type
\tcode{T} models} \tcode{TotallyOrdered\newtxt{<T>()}} \newtxt{is satisfied} if and only if

\begin{itemize}
\item \newtxt{Exactly one of \tcode{bool(a < b)}, \tcode{bool(b < a)}, or
      \tcode{bool(a == b)} is \tcode{true}.}
\item \oldtxt{\tcode{(a < a) == false}.}
\item \oldtxt{If \tcode{(a < b) != false}, then \tcode{(b < a) == false}.}
\item If \tcode{\newtxt{bool}(a < b)\oldtxt{ != false}} and \tcode{\newtxt{bool}(b < c)\oldtxt{ != false}}, then
      \tcode{\newtxt{bool}(a < c)\oldtxt{ != false}}.
\item \oldtxt{Exactly one of the following is true: \tcode{(a < b) != false}, or
      \tcode{(b < a) != false}, or \tcode{(a == b) != false}.}
\item \newtxt{\tcode{bool(a > b) == bool(b < a)}.}
\item \oldtxt{\tcode{(a > b) != false} if and only if \tcode{(b < a) != false}.}
\item \newtxt{\tcode{bool(a <= b) == !bool(b < a)}.}
\item \oldtxt{\tcode{(a <= b) != false} if and only if \tcode{(b < a) == false}.}
\item \newtxt{\tcode{bool(a >= b) == !bool(a < b)}.}
\item \oldtxt{\tcode{(a >= b) != false} if and only if \tcode{(b > a) == false}.}
\end{itemize}

\pnum
\enternote Not all arguments will be well-formed for a given type. For example, $NaN$ is not a
well-formed floating point value, and many types' moved-from states are not well-formed. This
does not mean that the type does not \oldtxt{model}\newtxt{satisfy} \tcode{TotallyOrdered}.\exitnote
\end{itemdescr}

\begin{itemdecl}
template <class T, class U>
concept bool TotallyOrdered() {
  return Common<T, U>@\newtxt{()}@ &&
    TotallyOrdered<T>() &&
    TotallyOrdered<U>() &&
    TotallyOrdered<CommonType<T, U>>() &&
    EqualityComparable<T, U>() &&
    requires (@\oldtxt{T a, U b}\newtxt{const T t, const U u}@) {
      { @\oldtxt{a}\newtxt{t}@ < @\oldtxt{b}\newtxt{u}@ } -> Boolean;
      { @\oldtxt{a}\newtxt{t}@ > @\oldtxt{b}\newtxt{u}@ } -> Boolean;
      { @\oldtxt{a}\newtxt{t}@ <= @\oldtxt{b}\newtxt{u}@ } -> Boolean;
      { @\oldtxt{a}\newtxt{t}@ >= @\oldtxt{b}\newtxt{u}@ } -> Boolean;
      { @\oldtxt{b}\newtxt{u}@ < @\oldtxt{a}\newtxt{t}@ } -> Boolean;
      { @\oldtxt{b}\newtxt{u}@ > @\oldtxt{a}\newtxt{t}@ } -> Boolean;
      { @\oldtxt{b}\newtxt{u}@ <= @\oldtxt{a}\newtxt{t}@ } -> Boolean;
      { @\oldtxt{b}\newtxt{u}@ >= @\oldtxt{a}\newtxt{t}@ } -> Boolean;
    };
}
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{\oldtxt{a}\newtxt{t}} be an object of type T, \tcode{\oldtxt{b}\newtxt{u}} be an object
of type \tcode{U}, and \tcode{C} be \tcode{CommonType<T, U>}. Then \oldtxt{types \tcode{T} and
\tcode{U} model} \oldtxt{\tcode{EqualityComparable}}
\newtxt{\tcode{TotallyOrdered<T,U>()>} is satisfied} if and only if

\begin{itemize}
\item \newtxt{\tcode{bool(t < u) == bool(C(t) < C(u))}.}
\item \oldtxt{\tcode{(a < b) != false} if and only if \tcode{(C(a) < C(b)) != false}.}
\item \newtxt{\tcode{bool(t > u) == bool(C(t) > C(u))}.}
\item \oldtxt{\tcode{(a > b) != false} if and only if \tcode{(C(a) > C(b)) != false}.}
\item \newtxt{\tcode{bool(t <= u) == bool(C(t) <= C(u))}.}
\item \oldtxt{\tcode{(a <= b) != false} if and only if \tcode{(C(a) <= C(b)) != false}.}
\item \newtxt{\tcode{bool(t >= u) == bool(C(t) >= C(u))}.}
\item \oldtxt{\tcode{(a >= b) != false} if and only if \tcode{(C(a) >= C(b)) != false}.}
\item \newtxt{\tcode{bool(u < t) == bool(C(u) < C(t))}.}
\item \oldtxt{\tcode{(b < a) != false} if and only if \tcode{(C(b) < C(a)) != false}.}
\item \newtxt{\tcode{bool(u > t) == bool(C(u) > C(t))}.}
\item \oldtxt{\tcode{(b > a) != false} if and only if \tcode{(C(b) > C(a)) != false}.}
\item \newtxt{\tcode{bool(u <= t) == bool(C(u) <= C(t))}.}
\item \oldtxt{\tcode{(b <= a) != false} if and only if \tcode{(C(b) <= C(a)) != false}.}
\item \newtxt{\tcode{bool(u >= t) == bool(C(u) >= C(t))}.}
\item \oldtxt{\tcode{(b >= a) != false} if and only if \tcode{(C(b) >= C(a)) != false}.}
\end{itemize}
\end{itemdescr}

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

\pnum
This section \oldtxt{describes the foundational}\newtxt{defines} concepts that describe the basis of the
value-oriented programming style on which the library is based. \oldtxt{The purpose of these concepts is
to establish a foundation for equational reasoning in programs.} \ednote{These concepts reuse many of the
names of concepts that traditionally describe features of types to describe families of object types (See
the rationale in Appendix~\ref{decomposition}).}

\rSec2[concepts.lib.object.destructible]{Concept Destructible}
\ednote{Remove table [destructible] in [utility.arg.requirements]. Replace
references to [destructible] with references to
[concepts.lib.\oldtxt{corelang}\newtxt{object}.destructible].}

\pnum
\newtxt{The \tcode{Destructible} concept is the base of the hierarchy of object concepts.
It describes properties that all such object types have in common.}

\indexlibrary{\idxcode{Destructible}}%
\begin{itemdecl}
template <class T>
concept bool Destructible@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ requires (T t@\newtxt{, const T ct, T* p}@) {
    { t.@$\sim$@T() } noexcept;
    @\newtxt{\{ \&t \} -> Same<T*>; // not \newtxt{required to be} equality preserving}@
    @\newtxt{\{ \&ct \} -> Same<const T*>; // not \newtxt{required to be} equality preserving}@
    @\newtxt{delete p;}@
    @\newtxt{delete[] p;}@
  };
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\ednote{\oldtxt{REVIEW: The expression \tcode{t.$\sim$T()} comes straight from the requirements table for the
\tcode{Destructible} concept in C++14. However, \tcode{t.$\sim$T()} is not valid if \tcode{T} is a
reference or array type. We need to decide whether we want \tcode{Destructible<int\&>} and
\tcode{Destructible<int[42]>} to be true or false.}}

\pnum
\newtxt{The expression requirement \tcode{\&ct} does not require implicit expression variants.}

\pnum
\oldtxt{A}\newtxt{Given a (possibly \tcode{const}) lvalue \tcode{t} of type \tcode{T} and pointer
\tcode{p} of type \tcode{T*},} \oldtxt{type \tcode{T} models} \tcode{Destructible\newtxt{<T>()}}
\newtxt{is satisfied} if and only if

\begin{itemize}
\item After \newtxt{evaluating} the expression \tcode{\oldtxt{u}\newtxt{t}.$\sim$T()},
\newtxt{\tcode{delete p}, or \tcode{delete[] p},} all resources owned by
\oldtxt{\tcode{u}}\newtxt{the denoted object(s)} are reclaimed.
\item \newtxt{\tcode{\&t == addressof(t)}.}
\item \newtxt{The expression \tcode{\&t} is non-modifying.}
\end{itemize}
\end{itemdescr}

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

\pnum
\newtxt{The \tcode{Constructible} concept is used to constrain the type of a
variable to be either an object type constructible from a given set of argument
types, or a reference type that can be bound to those arguments.}

\indexlibrary{\idxcode{Constructible}}%
\begin{itemdecl}
@\newtxt{template <class T, class ...Args>}@
@\newtxt{concept bool \xname{ConstructibleObject} = // \expos}@
  @\newtxt{Destructible<T>() \&\& requires (Args\&\& ...args) \{}@
    @\newtxt{T\{std::forward<Args>(args)...\}; // not required to be equality preserving}@
    @\newtxt{new T\{std::forward<Args>(args)...\}; // not required to be equality preserving}@
  @\newtxt{\};}@

@\newtxt{template <class T, class ...Args>}@
@\newtxt{concept bool \xname{BindableReference} = // \expos}@
  @\newtxt{is_reference<T>::value \&\& requires (Args\&\& ...args) \{}@
    @\newtxt{T(std::forward<Args>(args)...);}@
  @\newtxt{\};}@

template <class T, class ...Args>
concept bool Constructible@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return \xname{ConstructibleObject}<T, Args...> ||}@
    @\newtxt{\xname{BindableReference}<T, Args...>;}@
  @\oldtxt{requires ( Args...args ) \{}@
    @\oldtxt{T\{forward<Args>(args)...\};}@
  @\oldtxt{\};}@
@\newtxt{\}}@
\end{itemdecl}

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

\ednote{Remove table [defaultconstructible] in [utility.arg.requirements]. Replace
references to [defaultconstructible] with references to
[concepts.lib.\oldtxt{corelang}\newtxt{object}.defaultconstructible].}

\indexlibrary{\idxcode{DefaultConstructible}}%
\begin{itemdecl}
template <class T>
concept bool DefaultConstructible@\newtxt{() \{} \oldtxt{=}@
  @\newtxt{return Constructible<T>() \&\&}@
    requires @\newtxt{(const size_t n)}@ {
      @\newtxt{new}@ T@\newtxt{[n]}@{}; @\newtxt{// not \newtxt{required to be} equality preserving}@
    };
@\newtxt{\}}@
\end{itemdecl}

\pnum
\newtxt{\enternote The array allocation expression \tcode{new T[n]\{\}} implicitly
requires that \tcode{T} has a non-explicit default constructor. \exitnote}

\rSec2[concepts.lib.object.moveconstructible]{Concept MoveConstructible}
\ednote{Remove table [moveconstructible] in [utility.arg.requirements]. Replace
references to [moveconstructible] with references to
[concepts.lib.\oldtxt{corelang}\newtxt{object}.moveconstructible].}

\indexlibrary{\idxcode{MoveConstructible}}%
\begin{itemdecl}
template <class T>
concept bool MoveConstructible@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return Constructible<T, remove_cv_t<T>\&\&>() \&\&}@
    @\newtxt{ConvertibleTo<remove_cv_t<T>\&\&, T>();}@
    @\oldtxt{requires (T t) \{}@
      @\oldtxt{T(move(t));}@
    @\oldtxt{\};}@
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{rv} be an rvalue of type \oldtxt{\tcode{T}} \newtxt{\tcode{remove_cv_t<T>}}.
Then \oldtxt{a type \tcode{T} models} \tcode{MoveConstructible\newtxt{<T>()}} \newtxt{is satisfied}
if and only if

\begin{itemize}
\item After the definition \tcode{T u = rv;}, \tcode{u} is equal to the value of
\tcode{rv} before the construction.
\item \oldtxt{\tcode{T(rv)}} \newtxt{\tcode{T\{rv\}} or \tcode{*new T\{rv\}}} is equal
to the value of \tcode{rv} before the construction.
\end{itemize}

\pnum
\tcode{rv}'s \newtxt{resulting} state is unspecified. \enternote \tcode{rv} must still meet the
requirements of the library component that is using it. The operations listed
in those requirements must work as specified whether \tcode{rv} has been moved
from or not.\exitnote

\ednote{\newtxt{Ideally, \tcode{MoveConstructible} would include an array allocation
requirement \tcode{new T[1]\{std::move(t)\}}. This is not currently possible since
[expr.new]/19 requires an accessible default constructor even when all array elements
are initialized.}}
\end{itemdescr}

\rSec2[concepts.lib.object.copyconstructible]{Concept CopyConstructible}
\ednote{Remove table [copyconstructible] in [utility.arg.requirements]. Replace
references to [copyconstructible] with references to
[concepts.lib.\oldtxt{corelang}\newtxt{object}.copyconstructible].}

\indexlibrary{\idxcode{CopyConstructible}}%
\begin{itemdecl}
template <class T>
concept bool CopyConstructible@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ MoveConstructible<T>@\newtxt{()}@ &&
    @\newtxt{Constructible<T, const remove_cv_t<T>\&>() \&\&}@
    @\newtxt{ConvertibleTo<remove_cv_t<T>\&, T>() \&\&}@
    @\newtxt{ConvertibleTo<const remove_cv_t<T>\&, T>() \&\&}@
    @\newtxt{ConvertibleTo<const remove_cv_t<T>\&\&, T>();}@
    @\oldtxt{requires (T a, const T\& b) \{}@
      @\oldtxt{T(a);}@
      @\oldtxt{T(b);}@
      @\oldtxt{T((const T\&\&)b);}@
    @\oldtxt{\};}@
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{v} be an lvalue of type (possibly \tcode{const}) \oldtxt{\tcode{T}}
\newtxt{\tcode{remove_cv_t<T>}} or an rvalue of type \oldtxt{\tcode{const T}}
\newtxt{\tcode{const remove_cv_t<T>}}. Then \oldtxt{a type \tcode{T} models}
\tcode{CopyConstructible\newtxt{<T>()}} \newtxt{is satisfied} if and only if

\begin{itemize}
\item After the definition \tcode{T u = v;}, \tcode{v} \oldtxt{is unchanged and }is equal
to \tcode{u}.
\item \oldtxt{\tcode{T(v)}} \newtxt{\tcode{T\{v\}} or \tcode{*new T\{v\}}} is equal
to \tcode{v}\oldtxt{ and \tcode{v} is unchanged}.
\end{itemize}

\ednote{\newtxt{Ideally, \tcode{CopyConstructible} would include an array
allocation requirement \tcode{new T[1]\{t\}}. This is not currently possible since
[expr.new]/19 requires an accessible default constructor even when all array elements
are initialized.}}
\end{itemdescr}

\rSec2[concepts.lib.object.movable]{Concept Movable}
\ednote{Remove table [moveassignable] in [utility.arg.requirements]. Replace
references to [moveassignable] with references to
[concepts.lib.\oldtxt{corelang.moveassignable}\newtxt{object.movable}].}

\indexlibrary{\idxcode{Movable}}%
\begin{itemdecl}
template <class T>
concept bool @\oldtxt{MoveAssignable =}\newtxt{Movable() \{}@
  @\newtxt{return MoveConstructible<T>() \&\&}@
    @\newtxt{Assignable<T\&, T\&\&>();}@
    @\oldtxt{requires(T a, T b) \{}@
      @\oldtxt{\{ a = std::move(b) \} -> Same<T\&>;}@
    @\oldtxt{\};}@
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{rv} be an rvalue of type \tcode{T}
and let \tcode{t} be an lvalue of type \tcode{T}. Then \oldtxt{type \tcode{T} models}
\tcode{\oldtxt{MoveAssignable}\newtxt{Movable<T>()}} \newtxt{is satisfied} if and only if

\begin{itemize}
\item \oldtxt{\tcode{(addressof(t = rv) == addressof(t)) != false)}.}
\item After the assignment \newtxt{\tcode{t = rv},} \tcode{t} is equal to the value
of \tcode{rv} before the assignment.
\end{itemize}

\pnum
\tcode{rv}'s \newtxt{resulting} state is unspecified. \enternote \tcode{rv} must still meet the
requirements of the library component that is using it. The operations listed
in those requirements must work as specified whether \tcode{rv} has been moved
from or not.\exitnote
\end{itemdescr}

\rSec2[concepts.lib.object.copyable]{Concept Copyable}
\ednote{Remove table [copyassignable] in [utility.arg.requirements]. Replace
references to [copyassignable] with references to
[concepts.lib.\oldtxt{corelang.copyassignable}\newtxt{object.copyable}].}

\indexlibrary{\idxcode{Copyable}}%
\begin{itemdecl}
template <class T>
concept bool @\oldtxt{CopyAssignable =}\newtxt{Copyable() \{}@
  @\newtxt{return CopyConstructible<T>() \&\&}@
    @\oldtxt{MoveAssignable}\newtxt{Movable}@<T>@\newtxt{()}@ &&
    @\newtxt{Assignable<T\&, const T\&>();}@
    @\oldtxt{requires(T a, T b, const T\& c) \{}@
      @\oldtxt{\{ a = b \} -> Same<T\&>;}@
      @\oldtxt{\{ a = c \} -> Same<T\&>;}@
      @\oldtxt{\{ a = (const T\&\&)c \} -> Same<T\&>;}@
    @\oldtxt{\};}@
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{t} be an lvalue of type \tcode{T}, and \tcode{v} be an lvalue of type (possibly
\tcode{const}) \tcode{T} or an rvalue of type \tcode{const T}. Then \oldtxt{type \tcode{T} models}
\tcode{\oldtxt{CopyAssignable}\newtxt{Copyable<T>()}} \newtxt{is satisfied} if and only if

\begin{itemize}
\item \oldtxt{\tcode{(addressof(t = v) == addressof(t)) != false)}.}
\item After the assignment \newtxt{\tcode{t = v},} \tcode{t} is equal to \tcode{v}\oldtxt{ and \tcode{v} is unchanged}.
\end{itemize}
\end{itemdescr}

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

\indexlibrary{\idxcode{Semiregular}}%
\begin{itemdecl}
template <class T>
concept bool Semiregular@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return Copyable<T>() \&\&}@
    DefaultConstructible<T>@\newtxt{();} \oldtxt{\&\&}@
    @\oldtxt{CopyConstructible<T> \&\&}@
    @\oldtxt{Destructible<T> \&\&}@
    @\oldtxt{CopyAssignable<T> \&\&}@
    @\oldtxt{requires(T a, size_t n, T* p) \{}@
      @\oldtxt{// Object}@
      @\oldtxt{\{ \&a \} -> Same<T*>;}@
      @\oldtxt{// Destruction}@
      @\oldtxt{\{ a.~T() \} noexcept;}@
      @\oldtxt{// Allocation}@
      @\oldtxt{\{ new T \} -> Same<T*>;}@
      @\oldtxt{\{ new T[n] \} -> Same<T*>}@;
      @\oldtxt{// Deallocation}@
      @\oldtxt{delete p;}@
      @\oldtxt{delete[] p;}@
    @\oldtxt{\};}@
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
\oldtxt{Let \tcode{a} be any well-formed object of type \tcode{T}. Then type \tcode{T} models
\tcode{Semiregular} if and only if}

\begin{itemize}
\item \oldtxt{\tcode{(\&a == addressof(a)) != false}.}
\item \oldtxt{\tcode{a} is not a volatile object or const volatile object~(\cxxref{basic.type.qualifier}).}
\end{itemize}

\pnum
\enternote The \tcode{Semiregular} concept is \oldtxt{modeled}\newtxt{satisfied} by types that
\oldtxt{have} 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 Regular}

\indexlibrary{\idxcode{Regular}}%
\begin{itemdecl}
template <class T>
concept bool Regular@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ Semiregular<T>@\newtxt{()}@ &&
    EqualityComparable<T>@\newtxt{()}@;
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
\enternote The \tcode{Regular} concept is \oldtxt{modeled}\newtxt{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.functions]{Function concepts}

\rSec2[concepts.lib.functions.general]{In general}

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

\rSec2[concepts.lib.functions.function]{Concept Function}

\indexlibrary{\idxcode{Function}}%
\begin{itemdecl}
template <class F, class...Args>
using ResultType = result_of_t<F(Args...)>;

template <class F, class...Args>
concept bool Function@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ @\oldtxt{Destructible<T> \&\&}@
    CopyConstructible<@\oldtxt{T}\newtxt{F}@>@\newtxt{()}@ &&
    requires (F f, Args@\newtxt{\&\&}@...args) {
      typename ResultType<F, Args...>;
      @\oldtxt{\{ \&f \} -> Same<F*>;}@
      @\oldtxt{\{ f.~F() \} noexcept;}@
      @\oldtxt{\{ new F \} -> Same<F*>}@;
      @\oldtxt{delete new F}@;
      { f(std::forward<Args>(args)...) } -> Same<ResultType<F, Args...>>; @\newtxt{// not \newtxt{required to be} equality preserving}@
    };
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
\oldtxt{Let \tcode{f} be any object of type \tcode{F}. Then types \tcode{F} and \tcode{Args...} model
\tcode{Function} if and only if}

\begin{itemize}
\item \oldtxt{\tcode{(\&f == addressof(f)) != false}.}
\end{itemize}

\pnum
\oldtxt{The function call expression need not be equality-preserving; that is, the expression
\tcode{f(args...)} is allowed to return non-equal objects when called with equal arguments,
and still model \tcode{Function}.}

\pnum
\enternote \oldtxt{Since models of \tcode{Function} are allowed to be non-equality-preserving, a
function that generates random numbers may model \tcode{Function}}\newtxt{Since the function call
expression of \tcode{Function} is not required to be
equality-preserving~(\ref{concepts.lib.general.equality}), a function that generates random numbers
may satisfy \tcode{Function}}.\exitnote
\end{itemdescr}

\rSec2[concepts.lib.functions.regularfunction]{Concept RegularFunction}

\indexlibrary{\idxcode{RegularFunction}}%
\begin{itemdecl}
template <class F, class...Args>
concept bool RegularFunction@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ Function<F, Args...>@\newtxt{()}@;
@\newtxt{\}}@
\end{itemdecl}

\begin{itemdescr}
\pnum
\oldtxt{Models of}\newtxt{The function call expression of} \tcode{RegularFunction} shall be
equality-preserving~(\ref{concepts.lib.general.equality})\oldtxt{; that is, when passed equal
arguments, they shall return equal objects}. \newtxt{\enternote This requirement supersedes the
annotation on the function call expression in the definition of \tcode{Function}. \exitnote}

\pnum
\enternote A random number generator \oldtxt{is not a model of}\newtxt{does not satisfy}
\tcode{RegularFunction}.\exitnote

\pnum
\enternote There is no syntactic difference between \tcode{Function} and
\tcode{RegularFunction}.\exitnote
\end{itemdescr}

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

\indexlibrary{\idxcode{Predicate}}%
\begin{itemdecl}
template <class F, class...Args>
concept bool Predicate@\newtxt{() \{}\oldtxt{ =}@
  @\newtxt{return}@ RegularFunction<F, Args...>@\newtxt{()}@ &&
    @\oldtxt{Convertible}\newtxt{Boolean}@<ResultType<F, Args...>@\oldtxt{, bool}@>@\newtxt{()}@;
@\newtxt{\}}@
\end{itemdecl}

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

\indexlibrary{\idxcode{Relation}}%
\begin{itemdecl}
template <class @\oldtxt{F}\newtxt{R}@, class T>
concept bool Relation() {
  return Predicate<@\oldtxt{F}\newtxt{R}@, T, T>@\newtxt{()}@;
}

template <class R, class T, class U>
concept bool Relation() {
  return Relation<R, T>() &&
    Relation<R, U>() &&
    Common<T, U>@\newtxt{()}@ &&
    Relation<R, CommonType<T, U>>() &&
    @\newtxt{Predicate<R, T, U>() \&\&}@
    @\newtxt{Predicate<R, U, T>();}@
    @\oldtxt{requires (R r, T a, U b) \{}@
      @\oldtxt{\{ r(a, b) \} -> Boolean;}@
      @\oldtxt{\{ r(b, a) \} -> Boolean;}@
    @\oldtxt{\};}@
}
\end{itemdecl}

\begin{itemdescr}
\pnum
Let \tcode{r} be any well-formed object of type \tcode{R}, \tcode{a} be any well-formed object of
type \tcode{T}, \tcode{b} be any well-formed object of type \tcode{U}, and \tcode{C} be
\tcode{CommonType<T, U>}. Then \oldtxt{types \tcode{R}, \tcode{T}, and \tcode{U} model}
\tcode{Relation\newtxt{<R,T,U>()}} \newtxt{is satisfied} if and only if

\begin{itemize}
\item \newtxt{\tcode{bool(r(a, b)) == bool(r(C(a), C(b)))}.}
\item \oldtxt{\tcode{r(a, b) != false} if and only if \tcode{r(C(a), C(b)) != false}.}
\item \newtxt{\tcode{bool(r(b, a)) == bool(r(C(b), C(a)))}.}
\item \oldtxt{\tcode{r(b, a) != false} if and only if \tcode{r(C(b), C(a)) != false}.}
\end{itemize}
\end{itemdescr}

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

\indexlibrary{\idxcode{Relation}}%
\begin{itemdecl}
template <class @\oldtxt{F}\newtxt{R}@, class T>
concept bool StrictWeakOrder() {
  return Relation<@\oldtxt{F}\newtxt{R}@, T>();
}

template <class R, class T, class U>
concept bool StrictWeakOrder() {
  return Relation<R, T, U>();
}
\end{itemdecl}

\begin{itemdescr}
\pnum
\oldtxt{Let \tcode{comp} be a well-formed object of type \tcode{Comp}. Then type \tcode{Comp}
models concept} \newtxt{A \tcode{Relation} satisfies} \tcode{StrictWeakOrder} if and only if
it imposes a \techterm{strict weak ordering} on its arguments.

\ednote{Copied verbatim from [alg.sorting].}

{\color{black}
\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}
\end{addedblock}