《STL源码分析》学习笔记 — C++20 concepts

一、什么是concepts
二、concepts 的定义
三、constraints
- 1、Conjunctions
- 2、Disjunctions
- 3、Atomic constraints
- 4、约束标准化
- 5、约束的确定
四、requires 子句
五、requires 表达式
六、requires 表达式中的 requirements 分类
- 1、简单要求
- 2、类型要求
- 3、复合要求
- 4、嵌套要求
七、约束的偏序

在C++20之前的版本，迭代器相关类型的获取都是通过我们前面学习过的 iterator_traits。这个结构比较好理解。在C++20及之后，C++中提供了两个新的关键字 concept 和 requires 用于定义概念。

一、什么是concepts

在C++参考手册中，是这样描述概念的：

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

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

类模板、函数模板、非模板方法（特指类模板中的方法）可能会与某个约束相关联，用以特化对模板参数的要求。这可以被用来选择最合适的函数重载和模板特化。

这样的具名要求集合被称为概念。每个概念是一个断言，在编译时评估，而且该概念作为限制使用的模板的一部分。因此 concept 的违反将在编译时被检测到：

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

上述代码中 sort 算法需要的迭代器为随机访问迭代器，因此编译无法通过。

二、concepts 的定义

使用 concept 关键字的语法为：

template < template-parameter-list >
concept concept-name = constraint-expression;

如：

template <class T, class U>
concept Derived = std::is_base_of<U, T>::value;

concept 不能递归依赖自身，其模板参数也不能使用约束。除此之外，concept 的显式实例化、显式特化、部分特化都是不支持的。

concept 可以被用于 id 表达式中。当其限制被满足时，表达式为真；否则，表达式为假：

#include <iostream>

template<typename T>
concept dereferenceable = requires (T a) 
{
	*a;
};

int main()
{
	constexpr bool bl1 = dereferenceable<int>;
	std::cout << bl1 << std::endl;
	
	constexpr bool bl2 = dereferenceable<int*>;
	std::cout << bl2 << std::endl;
}

《STL源码分析》学习笔记 — C++20 concepts一、什么是concepts二、concepts 的定义三、constraints四、requires 子句五、requires 表达式六、requires 表达式中的 requirements 分类七、约束的偏序

concept 还能被用于类型限制中，作为类型模板参数声明、占位类型说明符以及复合要求中。其中，concept 被用于占位类型说明符主要是用于约束推导的类型：

#include <iostream>

template<typename T>
concept dereferenceable = requires (T a) 
{
	*a;
};

int main()
{
	int a = 1;
	auto b = a;
	dereferenceable auto c = a; //invalid，int 不满足 dereferenceable
	dereferenceable auto d = &a;
}

三、constraints

一个约束是一系列特化了模板参数要求的操作及操作数。它们可以直接出现在 requires 表达式中并且直接作为 concept 的一部分。

1、Conjunctions

我们可以使用 && 连接两个约束，用以表示与约束：

template <class T>
concept SignedIntegral = std::is_integral<T>::value && std::is_signed<T>::value;

类似逻辑表达式，这个表达式的评估是自左而右且短路的。

2、Disjunctions

类似地，我们使用 || 连接两个约束，用以表示或约束：

template <class T = void>
    requires EqualityComparable<T> || Same<T, void>
struct equal_to;

类似逻辑或表达式，同样是自左而右短路求值的。

3、Atomic constraints

原子约束由表达式 E 以及从 E 中出现的模板参数到约束实体中出现的模板参数的映射（也被称为参数映射）。原子操作在约束标准化时构成。E 永远不会是一个逻辑与或逻辑或的表达式（即前面提到的两种约束）。

原子约束的满足性检验是通过在 E 中替换参数映射和模板参数完成的。如果替换的结果是一个不合法的类型或表达式，则约束不被满足。否则，将E 从左值转化为右值后，应该是一个返回值类型为 bool 的 prvalue 常量表达式。当且仅当此表达式结果为 true 时，约束被满足。注意约束判定过程中不会对表达式返回值进行隐式类型转换。

template<typename T>
struct S {
    constexpr operator bool() const { return true; }
};
 
template<typename T>
    requires (S<T>{})
void f(T); // invalid

尽管 S<int>{} 表达式支持向 bool 类型的隐式转换，但是在约束评估过程中却并不会考虑。因此上述代码无法通过编译。

当从源码层面来说，两个原子约束是根据相同的表达式构成的且参数映射相同时，它们被认为是完全一致的：

#include <iostream>
using namespace std;

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

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

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

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

template<Meowable T>
void f1(T) {}

template<BadMeowableCat T>
void f1(T) {}

template<Meowable T>
void f2(T)
{
	cout << "f2(T) - Meowable" << endl;
}

template<GoodMeowableCat T>
void f2(T)
{
	cout << "f2(T) - GoodMeowableCat" << endl;
}

int main(int argc, char* argv[])
{
	f1(0); // invlaid

	f2(0);
}

（这部分功能可以结合后面的约束偏序看）对于 f1 模板函数的两个重载来说，它们是由不同的原子约束构成的，因此它们被认为是有二义性的。对于 f2 来说，GoodMeowableCat 是由 Meowable 构成的，而且其限制性更高，因此，将 f1(0) 注释掉后，运行结果为：

4、约束标准化

约束标准化就是将一个表达式转化为一系列由原子约束构成的 conjunctions 和 disjunctions。标准转化包括：

a. (E) 的标准化和 E 相同

b. E1 && E2 的标准化和 E1 和 E2 的 conjunctions 相同

c. E1 || E2 的标准化和 E1 和 E2 的 disjunctions 相同

d. 对于概念 C 来说，C<A1, A2, … , AN> 的标准化和使用 A1, A2, … , AN 替换 C 中的相应参数相同。如果这样替换之后的参数映射为无效类型或表达式，程序行为是不确定的，但是编译时并不会产生任何问题。

template<typename T> concept A = T::value || true;
template<typename U> 
concept B = A<U*>;  // U*value || true;

template<typename V> 
concept C = B<V&>; // V&*value || true;

5、约束的确定

与某个声明有关的约束是通过标准化具有如下顺序操作数的逻辑与表达式决定的：

对为每个受约束模板形参引入的约束表达式，根据其出现顺序；

在模板参数列表后面出现的requires子句中的约束表达式

对简写函数模板声明中每个拥有受约束占位符类型的形参所引入的约束表达式；

尾随requires子句中的约束表达式。

这个顺序决定了当约束被实例化以确定是否满足时的顺序。

受约束的声明只能以相同的语法形式重声明。不要求诊断。

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

四、requires 子句

关键字 requires 可以用于引入 requires 子句，以特化模板参数（即可以出现在函数声明之后，也可以在模板参数列表之后）或函数声明的限制：

template<typename T>
void f(T&&) requires Eq<T>; 
 
template<typename T> requires Addable<T> 
T add(T a, T b) ;

在此情况中，requires 后面的表达式必须是常量表达式：基础表达式如 Swappable, std::is_integral::value 和一系列使用 && 或 || 连接的基础表达式。

五、requires 表达式

requires 关键字同样可以被用在 requires 表达式开头。该表达式需要是一个 prvalue 表达式且类型为 bool （与约束的要求类似）。requires 表达式的语法如下：

requires { requirement-seq }		
requires ( parameter-list(optional) ) { requirement-seq }

parameter-list 是由逗号分隔开的参数列表，与函数声明类似，但是不支持默认参数。该列表不支持省略号（除了类模板中用于包展开的参数）。这些参数没有存储持续性、链接性和生命周期，且只能被用于协助特化要求。这些参数的作用域截止于 requirement-seq 的 }。

requirement-seq - 一系列要求，后面将介绍四种分类。

requirement 可能有赖于作用域内的模板参数，位于 parameter-list 中的局部参数以及任何其他在封闭上下文可见的声明。在表达式中将模板参数替换进 requires 表达式可能会导致不合法的类型或表达式的形成。在这种情况下，requires 表达式被评估为假而且不会导致程序的未知行为。替换行为和语义限制检查是按词素顺序进行的，并且在遇到可以决定 requires 表达式结果时停止。如果替换行为和语义限制检查成功，则该表达式被评估为真。如果在requires 表达式，有一个对于所有可能的模板参数的替换失败行为，则程序行为未知，且没有任何错误被检测到。

六、requires 表达式中的 requirements 分类

1、简单要求

简单必要条件是任意不以关键字 requires 开头的表达式陈述。该陈述断言该表达式是可用的。表达式是未被评估的操作数；只有语言的正确性被检验。

template<typename T>
concept Addable =
requires (T a, T b) {
    a + b; // simple requirement
};

2、类型要求

类型要求是跟在关键字 typename 后的类型名，以进行选择限制。此要求是命名要求是合法的：这可以被用于检验某个确定的命名嵌套名称存在，或是类模板特化确定了一个类型，或是别名模板特化确定了一个类型。一个确定了类模板特化的类型要求不需要类型是 complete 的。

template<typename T> using Ref = T&;
template<typename T> concept C =
requires {
    typename T::inner; // required nested member name
    typename S<T>;     // required class template specialization
    typename Ref<T>;   // required alias template substitution
};

3、复合要求

复合要求的格式为：

其中，return-type-requirement 为类型约束，且断言了命名表达式的属性。替换和语义约束检查按以下顺序进行：

模板参数被替换到表达式中；

如果 noexcept 关键字被使用，表达式必须不能是潜在可能抛出异常的；

如果 return-type-requirement 出现，那么：

模板参数会被替换到 return-type-requirement 中；

decltype((expression)) 必须满足类型约束的限制。否则 require 表达式将为 false。

template<typename T> concept C2 =
requires(T x) {
    {*x} -> std::convertible_to<typename T::inner>; // 表达式 *x 必须合法
                                                    // T::inner 必须合法
                                                    // *x 必须可以转化为T::inner
};

4、嵌套要求

嵌套要求的格式为：

它可以通过临时变量的形式被用于特化额外的限制。约束表达式必须在替换模板参数（如果有的话）之后可以被满足。将模板参数替换到嵌套要求中会造成约束表达式中的替换，仅限于确定是否满足约束表达式。

template <class T>
concept Semiregular = DefaultConstructible<T> &&
    CopyConstructible<T> && Destructible<T> && CopyAssignable<T> &&
requires(T a, size_t n) {  
    requires Same<T*, decltype(&a)>;  // 嵌套要求
    { a.~T() } noexcept;  // 复合要求
    requires Same<T*, decltype(new T)>; // 嵌套要求
    requires Same<T*, decltype(new T[n])>; // 嵌套要求
    { delete new T };  // 复合要求
    { delete new T[n] }; // 复合要求
};

七、约束的偏序

在任何深层的分析之前，约束会被标准化，通过替换约束体内每个命名的 concept 和 requires 表达式，直到仅剩下一系列原子操作的 conjunctions 和 disjunctions。

一个约束P可以被认为归入约束Q，如果根据P和Q中的原子约束的特征可以证明P包含Q的约束。类型和表达式不会被分析，例如： N > 0 N \gt 0 N>0 不会被归入 N ≥ 0 N \ge 0 N≥0。

具体地，首先P被转化为 disjunctive 标准形式，Q被转化为conjunctive 标准形式。P归入Q，当且仅当：

在P的分离标准形式中的每个分离的子句可以归入Q的联合标准形式中的每个联合子句，其中

一个分离子句归入一个联合子句，当且仅当分离子句中有一个原子约束U可以归入联合子句中的一个原子约束V。

一个原子约束A归入一个原子约束B，当且仅当它们完全相同的使用上述规则。

归入规则定义了约束的部分顺序，该顺序用以确定：

在重载解析时，一个非模板函数的最佳可行候选；

在重载集合中，一个非模板函数的地址；

一个模板中模板参数的最佳匹配；

类模板特化的部分顺序；

模板函数的部分顺序；

约束的顺序如下：

如果声明D1和D2被约束，而且D1的约束归入D2的约束（或者D2是未被约束的），那么D1被认为是至少与D2受到相同的限制。如果D1的限制程度不低于D2而D2的限制程度并非不低于D2。那么相比于D2，D1就是更受约束的：

template<typename T>
concept Decrementable = requires(T t) { --t; };
template<typename T>
concept RevIterator = Decrementable<T> && requires(T t) { *t; };
 
// RevIterator 归入 Decrementable
 
template<Decrementable T>
void f(T); // #1
 
template<RevIterator T>
void f(T); // #2 受限制更严格
 
void testf()
{
	f(0);       // int 只满足Decrementable ，选择#1
	f((int*)0); // int* 满足 Decrementable 和 RevIterator, 选择 #2 因为该约束更严格
}
 
template<class T>
void g(T); // #3 未被限制
 
template<Decrementable T>
void g(T); // #4
 
void testg()
{
	g(true);  // bool 不满足Decrementable，选择#3
	g(0);     // int 满足 Decrementable, 选择#4因为该约束更严格
}
 
template<typename T>
concept RevIterator2 = requires(T t) { --t; *t; };
 
template<Decrementable T>
void h(T); // #5
 
template<RevIterator2 T>
void h(T); // #6

void testh()
{
	// h((int*)0); // 表达式中的归入关系不会被评估，引发二义性
}

《STL源码分析》学习笔记 — C++20 concepts一、什么是concepts二、concepts 的定义三、constraints四、requires 子句五、requires 表达式六、requires 表达式中的 requirements 分类七、约束的偏序

《STL源码分析》学习笔记 — C++20 concepts

一、什么是concepts

二、concepts 的定义

三、constraints

1、Conjunctions

2、Disjunctions

3、Atomic constraints

4、约束标准化

5、约束的确定

四、requires 子句

五、requires 表达式

六、requires 表达式中的 requirements 分类

1、简单要求

2、类型要求

3、复合要求

4、嵌套要求

七、约束的偏序

继续阅读

C语言第四章自述2第四章选择结构程序设计

面试题:vector和map的区别，异同。空间分布，100万数据存哪个比较合适。一、迭代器区别二、vector三、Map、Set四、vector_map 为什么比map效率高五、如何选择六、容器选择原则七、效率对比

C++ 多线程用条件变量确定线程的执行顺序而不是使用 sleep(1)

POJ 1284 Primitive Roots (欧拉函数&原根定理)

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

成员函数初始化列表

2021-08-13c++——类之操作符重载

swmm与lisflood-fp源码如何一起编译 CMake命令

Windows下VS开发环境环境安装工程项目设置关于Debug和Release的提示

一文看懂字符串的加减乘除

C++ 第十五周报告1--《冒泡法排序》

C++实现简单顺序表

C经典书籍笔记——C陷阱与缺陷②(语法陷阱之优先级)一、错误案列二、优先级规律

线性表之顺序表的实现

C++判断素数、求最大公约数代码判断一个数是否为素数求两个数的最大公约数

SequoiaDB巨杉数据库C++驱动概述