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

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 是使满意)。那么“更高效”的 sort #2 是如何选择的呢？主持人说“它只是有效”。

Answer 1

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

之所以可行，是因为约束条件存在部分排序(由包含 关系定义)。

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 关系 ->(定义)约束偏序 ->(确定)声明是多/少约束关系。

简而言之，归一化是约束参数映射中概念模板参数的替代。

---

例子:

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]

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

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

• 不存在包含关系
• 没有更多约束关系

这会导致额外的歧义。

---

§ 13.5.1 Constraints [temp.constr.constr]

1. 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]

1. 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]

1. 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.

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

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

1. 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]

2. [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]

3. 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.

4. 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