最好的约束函数模板是如何用概念选出来的？

Question

在概念演示中，显示了这样的内容：

template <bidirectional_iterator It>
void sort(It begin, It end);            // #1

template <random_access_iterator It>
void sort(It begin, It end);            // #2

std::list<int> l{};
sort(l.begin(), l.end()); // #A  -> calls #1

std::vector<int> v{};
sort(v.begin(), v.end()); // #B  -> calls #2

对于调用 #A 很简单：只有 sort #1 可行，因为约束 random_access_iterator 不满足，所以它调用 #1.

但是对于调用 #B，两个 sort 都是可行的，因为两个约束（random_access_iterator 和 bidirectional_iterator 都满足）。那么"more efficient"sort #2是怎么选出来的呢？主持人说"it just works".

Answer 1

So how is the "more efficient" sort #2 chosen?

之所以有效，是因为在约束（由 subsumes 关系定义）上存在 部分排序 。

sort #2（带 randomaccess_iterator 的那个）比 sort #1（带 bidirectional_iterator 的那个）更受约束因为 randomaccess_iterator 包含 bidirectional_iterator:

template <class It>
concept bidirectional_iterator = requires /*...*/;

template <class It>
concept randomaccess_iterator = bidirectional_iterator<It> && requires /*...*/;

为了使这项工作约束在连词和析取的语言级别上是可感知的。

确定一个声明是否比另一个声明受到更多或更少约束的过程是这样的：约束规范化 -> 约束 subsumes 关系 ->（定义）约束偏序 -> (确定)声明是more/less约束关系。

简化，归一化是concepts模板参数在constraints的参数映射中的替换。

示例：

template <class T> concept integral        = std::is_integral_v<T>;
template <class T> concept signed_integral = integral<T> && std::is_signed_v<T>;
template <class T> concept integral_4      = integral<T> && sizeof(T) == 4;

void foo_1(integral auto)        // #0
void foo_1(signed_integral auto) // #1 
void foo_1(integral_4 auto)      // #2

auto test1()
{
    foo_1(std::uint16_t{});  // calls #0
    foo_1(std::uint32_t{});  // calls #2

    foo_1(std::int16_t{});   // calls #1
    //foo_1(std::int32_t{}); // error ambiguous between #1 and #2
}

integral的正常形式是std::is_integral_v<T>
signed_integral 的正常形式是 std::is_integral_v<T> ∧ std::is_signed_v<T>
正常形式integral_4是std::is_integral_v<T> ∧ sizeof(T) == 4
signed_integral 包含 integral
integral_4 包含 integral
#1 比 #0
#2 比 #0

示例：

template <class T> concept integral            = std::is_integral_v<T>;
template <class T> concept signed_integral_sad = std::is_integral_v<T> &&
                                                     std::is_signed_v<T>;
template <class T> concept integral_4_sad      = std::is_integral_v<T> && sizeof(T) == 4;


void foo_2(integral auto)             // #0
void foo_2(signed_integral_sad auto); // #1
void foo_2(integral_4_sad auto);      // #2


auto test2()
{
    foo_2(std::uint16_t{});   // calls #0
    //foo_2(std::uint32_t{}); // error ambiguous between #0 and #2

    //foo_2(std::int16_t{});  // error ambiguous between #0 and #1
    //foo_2(std::int32_t{});  // error ambiguous between #0, #1 and #2
}

integral的正常形式是std::is_integral_v<T>
signed_integral_sad的正常形式是std::is_integral_v<T> ∧ std::is_signed_v<T>
正常形式integral_4_sad是std::is_integral_v<T> ∧ sizeof(T) == 4

不过有个规定

§13.5.1.2 Atomic constraints [temp.constr.atomic]

Two atomic constraints, e1 and e2, are identical if they are formed from the same appearance of the same expression [...]

这意味着来自 3 个范式的 std::is_integral_v<T> 原子表达式在它们之间并不相同，因为它们不是由相同的表达式形成的。所以：

没有包含关系
没有更多约束关系

这导致了额外的歧义。

§ 13.5.1 Constraints [temp.constr.constr]

A constraint is a sequence of logical operations and operands that specifies requirements on template arguments. The operands of a logical operation are constraints. There are three different kinds of constraints:

(1.1) conjunctions (13.5.1.1)

(1.2) disjunctions (13.5.1.1), and

(1.3) atomic constraints (13.5.1.2).

§13.5.1.1 Logical operations [temp.constr.op]

There are two binary logical operations on constraints: conjunction and disjunction. [Note: These logical operations have no corresponding C++ syntax. For the purpose of exposition, conjunction is spelled using the symbol ∧ and disjunction is spelled using the symbol ∨]

§13.5.3 Constraint normalization [temp.constr.normal]

The normal form of an expression E is a constraint (13.5.1) that is defined as follows:

(1.1) The normal form of an expression ( E ) is the normal form of E.

(1.2) The normal form of an expression E1 || E2 is the disjunction (13.5.1.1) of the normal forms of E1 and E2.

(1.3) The normal form of an expression E1 && E2 is the conjunction of the normal forms of E1 and E2.

(1.4) The normal form of a concept-id C<A1, A2, ..., An> is the normal form of the constraint-expression of C, after substituting A1, A2, ..., An for C’s respective template parameters in the parameter mappings in each atomic constraint. [...]

(1.5) The normal form of any other expression E is the atomic constraint whose expression is E and whose parameter mapping is the identity mapping.

The process of obtaining the normal form of a constraint-expression is called normalization.

§13.5.4 Partial ordering by constraints [temp.constr.order]

A constraint P subsumes a constraint Q if and only if, for every disjunctive clause Pi in the disjunctive normal form ¹³⁰ of P, Pi subsumes every conjunctive clause Qj in the conjunctive normal form ¹³¹ of Q, where

(1.1) a disjunctive clause Pi subsumes a conjunctive clause Qj if and only if there exists an atomic constraint Pia in Pi for which there exists an atomic constraint Qjb in Qj such that Pia subsumes Qjb, and

(1.2) an atomic constraint A subsumes another atomic constraint B if and only if A and B are identical using the rules described in 13.5.1.2.

[Example: Let A and B be atomic constraints (13.5.1.2). The constraint A ∧ B subsumes A, but A does not subsume A ∧ B. The constraint A subsumes A ∨ B, but A ∨ B does not subsume A. Also note that every constraint subsumes itself. — end example]

[Note: The subsumption relation defines a partial ordering on constraints. This partial ordering is used to determine

(2.1) the best viable candidate of non-template functions (12.4.3),

(2.2) the address of a non-template function (12.5),

(2.3) the matching of template template arguments (13.4.3),

(2.4) the partial ordering of class template specializations (13.7.5.2), and

(2.5) the partial ordering of function templates (13.7.6.2).

— end note]

A declaration D1 is at least as constrained as a declaration D2 if

(3.1) D1 and D2 are both constrained declarations and D1’s associated constraints subsume those of D2; or

(3.2) D2 has no associated constraints.

A declaration D1 is more constrained than another declaration D2 when D1 is at least as constrained as D2, and D2 is not at least as constrained as D1.

130) A constraint is in disjunctive normal form when it is a disjunction of clauses where each clause is a conjunction of atomic constraints. [Example: For atomic constraints A, B, and C, the disjunctive normal form of the constraint A ∧ (B ∨ C) is (A ∧ B) ∨ (A ∧ C). Its disjunctive clauses are (A ∧ B) and (A ∧ C). — end example]

131) A constraint is in conjunctive normal form when it is a conjunction of clauses where each clause is a disjunction of atomic constraints. [Example: For atomic constraints A, B, and C, the constraint A ∧ (B ∨ C) is in conjunctive normal form. Its conjunctive clauses are A and (B ∨ C). — end example

最好的约束函数模板是如何用概念选出来的？

How is the best constrained function template selected with concepts?

c++

c++-concepts

c++20