发表于 | 阅读次数:

本文主要学习于从4行代码看右值引用

文章的主线是4行代码的故事…写博客的过程中感觉文脉有点混乱，但是其中的很多概念都是比较清晰的

和右值引用相关的概念比较多，比如：右值、纯右值、将亡值、universal references、引用折叠、移动语义、move语义和完美转发等等

引入右值引用主要为了解决C++98/03遇到的两个问题

1、临时对象非必要的昂贵的拷贝操作

2、模板函数中如何按照参数的实际类型进行转发

第一行代码

int i = getVar();

代码很简单，从getVar()函数获取一个整形值

然而，这行代码会产生两种类型的值，一种是左值i，一种是getVar()返回的临时值，这个临时值在表达式结束之后就销毁了

这个临时值就是一个右值(rvalue)，具体来说是一个纯右值(prvalue)，是不具名的

区分左值和右值的简单方法：看能不能对表达式取地址，如果能，则为左值；反之则为右值

在C++11中所有的值必属于左值、将亡值、纯右值三者之一

比如，非引用返回的临时变量、运算表达式产生的临时变量、原始字面量和lambda表达式都是纯右值

而将亡值是C++11新增的、与右值引用相关的表达式，比如，将要被移动的对象、T&&函数返回值、std::move返回值和转换为T&&的类型的转换函数的返回值等

将亡值将在后文中介绍

1
2
int j = 5;
auto f = []{ return 5;};

代码中5是一个原始字面量，[]{ return 5;}是lambda表达式，都属于纯右值，在表达式结束之后就销毁了

第二行代码

右值引用的特点

特点1

T&& k = getVar();

相比第一行多了”&&”，即右值引用

表达式结束后，getVar()产生的临时值不会被销毁，而是会被”续命“(……)，它的生命周期将会通过右值引用得以延续，和变量k的生命周期一样长

这里不展开了，《深度探索C++对象模型》中探讨过NRV(Named Return Value)优化

事实上，常量左值引用在C++98/03中也经常用于性能优化，因为常量左值引用是一个万能的引用类型，可以接受左值、右值、常量左值和常量右值

注意是const A& a = GetA();必须加上const

而A& a = GetA();会报一个编译错误，因为非常量左值引用只能接受左值

特点2

右值引用独立于左值和右值，意思是右值引用类型的变量可能是左值也可能是右值

举个例子 int** var1 = 1;

var1为右值引用，但var1本身是左值，因为具名变量都是左值

有一个有意思的问题，T&&是什么？一定是右值吗？代码如下

1
2
3
4
5
6
7
template<typename T>
void f(T&& t){}

f(10); //t是右值

int x = 10;
f(x); //t是左值

从代码中可以看到，T&&表示的值类型不确定，可能是左值也可能是右值，这一点看起来有点奇怪，但这就是右值引用的一个特点

特点3

T&& t在发生自动类型推断时，它是未定的引用类型(universal references)

如果被左值初始化那么它就是左值，如果被右值初始化那么它就是右值

你说你证明了哥德巴赫猜想，那你就是证明了哥德巴赫猜想；你说你没有证明哥德巴赫猜想，那你就是没有证明哥德巴赫猜想

它是左值还是右值取决于它的初始化

需要注意的是，仅仅是当发生自动类型推导（如函数模板的类型推断，或auto关键字）时，T&&才是universal references

再看看以下的例子

1
2
3
4
5
6
7
template<typename T>
void f(T&& param); 

template<typename T>
class Test {
    Test(Test&& rhs); 
};

param是universal reference，而rhs是Test&&右值引用

因为模板函数f发生了类型推导，而Test&&并没有发生类型推导，因为Test&&是确定的类型了

（再看一下特点2的例子就基本明白了）

根据这个特点，我们可以用来做很多事情，比如下文要介绍的移动语义和完美转发

再提一下引用折叠，可能存在左值引用和右值引用、右值引用和右值引用的折叠，C++11确定了引用折叠的规则

所有右值引用叠加到右值引用上仍然是一个右值引用

所有其他类型的引用之间的叠加都将变成左值引用

第三行代码

移动构造函数

T(T&& a) : m_val(val){ a.m_val = nullptr; }

这行代码实际来自一个类的构造函数，参数是一个右值引用

1
2
3
4
5
6
7
8
9
10
11
class A {
public:
	A() :m_ptr(new int(0)) { cout << "construct" << endl; }
	A(const A& a) :m_ptr(new int(*a.m_ptr)) {
		//深拷贝的拷贝构造函数
		cout << "copy construct" << endl;
	}
	~A() { delete m_ptr; }
private:
	int* m_ptr;
};

一个带有堆内存的类，必须提供一个深拷贝构造函数，否则会发生指针悬挂问题（类似double free）

提供深拷贝的拷贝构造函数虽然可以保证正确，但在有时候会产生额外的性能损耗

C++11给出了移动构造函数的解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class A {
public:
	A() :m_ptr(new int(0)) {}
	A(const A& a) :m_ptr(new int(*a.m_ptr)) { //深拷贝的拷贝构造函数
		cout << "copy construct" << endl;
	}
	A(A&& a) :m_ptr(a.m_ptr) {
		a.m_ptr = nullptr;
		cout << "move construct" << endl;
	}
	~A() { delete m_ptr; }
private:
	int* m_ptr;
};

A a = Get(false);

输出结果会是

1
2
3
construct
move construct
move construct

相比之下只多了一个构造函数，拷贝并没有调用深拷贝构造函数，而是调用了移动构造函数

它仅仅是将指针的所有者转移到了另外一个对象，同时将参数a的指针置为空（安全隐患？）

移动构造函数的参数是一个右值引用类型，前面已经提到，这里并没有发生类型推断，是确定的右值引用

为什么会匹配到这个构造函数？

因为这个构造函数只能接受右值参数，而函数返回值是右值（暂时没怎么看懂）

这里A&&可以看作是临时值的标识

待更细节

需要注意的是，在提供移动构造函数时也会提供一个拷贝构造函数，以防移动不成功时还能拷贝构造

std::move

既然移动语义是通过右值引用来匹配临时值的，自然会想左值是否也能借助移动语义来优化性能呢？

答案是肯定的，C++11提供了std::move来解决这个问题，它将左值转换为右值，从而方便应用移动语义

std::move将对象资源的所有权从一个对象转移到另一个对象

举个例子

1
2
3
4
5
6
7
std::list< std::string> tokens;
//省略初始化...
std::list< std::string> t = tokens; //这里存在拷贝
//省略代码块标志...
std::list< std::string> tokens;
//省略初始化...
std::list< std::string> t = std::move(tokens);  //这里没有拷贝

使用std::move几乎没有任何代价，只是转换了资源的所有权，实际将左值变成右值引用，然后应用移动语义，调用移动构造函数，避免了拷贝

事实上，C++11中所有的容器都实现了移动语义，以便进行性能优化

这里也要注意对move语义的理解，move实际上不能移动任何东西，唯一的功能是将一个左值强制转换为一个右值引用

如果是一些基本类型比如int和char[10]定长数组等类型，使用move仍然会发生拷贝（因为没有对应的移动构造函数）

因此，move对于含资源（堆内存或句柄）的对象来说更有意义

第四行代码

1
template <typename T>void f(T&& val){ foo(std::forward<T>(val)); }

C++11之前调用模板函数时，如何正确地传递参数是一个难以解决的问题

1
2
3
4
5
6
7
8
9
template<typename T>
void forwardValue(T& val) {
	processValue(val);	//右值参数会变成左值
}

template<typename T>
void forwardValue(const T& val) {
	processValue(val);	//参数都变为常量左值引用
}

C++11引入了完美转发：在函数模板中，完全依照模板的参数的类型（即保持参数的左值、右值特征），将参数传递给模板函数中调用的另一个函数

std::forward即按照参数的实际类型转发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>

using namespace std;

void processValue(int& a) { cout << "lvalue" << endl; }
void processValue(int&& a) { cout << "rvalue" << endl; }

template<typename T>
void forwardValue(T&& val) {
	processValue(std::forward<T>(val));	//照参数本来的类型转发
}

void Testdelcl() {
	int i = 0;
	forwardValue(i);	//传入左值
	forwardValue(0);	//传入右值
}

int main(int argc, char**argv) {
	Testdelcl();
	//输出:
	//lvalue
	//rvalue
	return 0;
}

右值引用T&&是一个universal references，可以接受左值或者右值，正是这个特性使它适合作为一个参数的路由，然后通过std::forward按照参数的实际类型去匹配对应的重载函数，最终实现完美转发

我们可以结合完美转发和移动语义来实现一个泛型的工厂函数，这个工厂函数可以创建所有类型的对象

1
2
3
4
5
template<typename... Args>
T* Instance(Args... args){
	return new T(std::forward<Args >(args)…);
}
//原文代码，没有看懂，T是什么...

这个工厂函数的参数是右值引用类型，内部使用std::forward按照参数实际类型进行转发

如果参数是右值，那么创建时自动匹配移动构造函数；如果是左值则匹配拷贝构造

万能的函数包装器

右值引用、完美转发再结合可变模板参数，可以写一个万能的函数包装器，接受所有的函数，委托执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<string>
using namespace std;

template<class Function, class... Args>
inline auto FuncWrapper(Function&& f, Args&&... args)
-> decltype(f(std::forward<Args>(args)...)) {
	//typedef decltype(f(std::forward<Args>(args)...)) ReturnType;
	return f(std::forward<Args>(args)...);
}

void test0(){
	cout << "void" << endl;
}

int test1(){
	return 1;
}

int test2(int x){
	return x;
}

string test3(string s1, string s2){
	return s1 + s2;
}

int main(int argc, char**argv) {
	FuncWrapper(test0);  // 没有返回值，打印1
	cout << FuncWrapper(test1) << endl; 	// 返回1
	cout << FuncWrapper(test2, 1) << endl;	// 返回1
	cout << FuncWrapper(test3, "aa", "bb") << endl; // 返回"aabb"
	return 0;
}

发表于 | 阅读次数:

由于我自己也是在学习的过程中，并没有形成具体的函数式思维，因此可能记录的学习过程比较乱

标准库的基本使用

std::pair

std::pair是标准库中所有键值数据(key-value data)的默认返回类型，是快速使用标准库的第一把钥匙

重载输出流

这段代码高亮有点问题，我本地md里正常，修不好……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<string>
#include<utility>
#include<functional>

using namespace std;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& _) {
	return out << "(" << _.first << "," << _.second << ")" << endl;
}

int main(int argc, char**argv) {
	std::string names[3] = { "lambda","C++","pwn" };
	int scores[3] = { 3,4,5 };
	std::pair <std::string, int> p0 = std::make_pair(names[1], scores[1]);
	//p0 = (C++,4)
	auto p1 = std::make_pair(names[2], scores[2]);
	//p1 = (pwn,5)
	auto p2 = std::make_pair(names[1], std::ref(scores[1]));
	scores[1] += 10;
	//p0 不变
	//p2 = (C++,14)     std::ref()
	cout << p0 << p1 << p2;
	return 0;
}

std::tuple

更一般地，元组(tuple)可以把多个不同数据类型的实例绑定到一个实例上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<string>
#include<tuple>
#include<functional>

using namespace std;

int main(int argc, char**argv) {
	std::string names[3] = { "C++","lambda","reverse" };
	char ranks[3] = { 'A','B','C' };
	int scores[3] = { 5,6,7 };

	auto student0 = std::make_tuple(names[0], ranks[0], scores[0]);
	std::cout << "student0  name:" << std::get<0>(student0)
		<< ", rank:" << std::get<1>(student0)
		<< ", score:" << std::get<2>(student0) << std::endl;
	//student0  name:C++, rank:A, score:5

	std::string s;
	char c;
	int i;
	auto student1 = std::make_tuple(names[1], ranks[1], scores[1]);
	std::tie(s, c, i) = student0;
	std::cout << "student1  name:" << s
		<< ", rank:" << c
		<< ", score:" << i << std::endl;
	//student1  name:C++, rank:A, score:5

	/*
	auto student2 = std::tie(names[2],ranks[2],scores[2]);
	auto[_1, _2, _3] = student2;	// C++17 structured binding
	std::cout << "student2  name:" << _1
		<< ", rank:" << _2
		<< ", score:" << _3 << std::endl;

	g++-7 main.cpp -std=c++17
	输出：student2  name:reverse, rank:C, score:7
	*/

	return 0;
}

tuple的组装和拆包任务分别由两个函数来担当

std::make_tuple创建一个元组，std::get获取确定位置的数据

注意到，std::tie既可以组装元组，也可以对一个元组进行拆包

1
std::tie(std::ignore, std::ignore, xxx) = student0;

std::ignore 可以作为解包时的占位符

auto[a,b,c]=xxx 是复制一份数据

std::tie()默认会创建原变量的引用

std::vector

基本的使用就不提了，后文会经常用到，考虑一下vector扩充内存的细节

当反复push_back()一个元素时，一旦达到了上限，vector会把可用空间大小扩充为之前的k倍，一般为2或1.5，具体由编译器决定

lambda函数

基本使用

举个两个简单的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char**argv) {
	auto addition = [](int _1, int _2)->int { return _1 + _2; };
	vector<int>a = { 1,2,3,4,5 };
	vector<int>b = { 6,7,8,9,10 };
	for (int i = 0, sz = a.size(); i < sz; i++) {
		a[i] = addition(a[i], b[i]);
	}
	for (auto e : a)cout << e << endl;

	return 0;
}

要注意的是，addition并不是lambda函数的名字，它只是被附身了而已…lambda本身是没有名字的，因此不能简单地实现递归

参数列表中的中括号，名为捕捉列表，用于捕捉当前lambda所在环境的变量

参数列表之后有一个箭头，箭头后跟着返回值的类型

最后，与函数声明完之后直接用大括号收尾不同，在这里可以暂时把lambda函数看做一个特殊的变量，所以最后用分号收尾

auto a_alias = [capture](parameters)->return_type{...};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char**argv) {
	int j = 1;
	auto by_val_lambda = [=] { return j + 1; };
	auto by_ref_lambda = [&] { return j + 1; };
	auto print = [=] {
		cout << "print by val lambda: " << by_val_lambda() << endl;
		cout << "print by ref lambda: " << by_ref_lambda() << endl;
	};
	print();
	j += 10;
	print();

	return 0;
}

结果如下

1
2
3
4
print by val lambda: 2
print by ref lambda: 2
print by val lambda: 2
print by ref lambda: 12		//引用传递

[=]表示按照值传递的方法捕捉父作用域的所有变量

[&]表示按照引用传递的方法捕捉父作用域的所有变量

如果想要捕捉特定的变量，可以直接写[var]或[&var]

甚至可以捕捉this指针，如果父作用域存在的话

lambda函数的出现减少了对命名空间的污染，也可以理解为增加了一种简单的局部函数的实现

可以直接把函数写在main函数里，用函数指针来管理

lambda递归

计算阶乘

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
#include<functional>
#include<vector>

using namespace std;

int main(int argc, char**argv) {
	std::function<int(int)>fact;
	fact = [&fact](int x)->int { return x <= 1 ? x : x * fact(x - 1); };
	cout << fact(5) << endl;
	return 0;
}

lambda实现递归时，可以提前声明fact，然后再用[&fact]捕获

当右值赋给fact时，也就是fact函数指针被lambda”附身”，fact的值改变，那么fact的引用也对应改变

以下为照抄部分：链接

准确地讲，上面根本不是lambda函数的递归调用，只是一般函数的递归而已

想要实现lambda函数的递归调用，必须首先对Y-组合子有一定的了解

简单地说，虽然lambda没有名字，但我们可以把它作为一个参数传递给更上层的函数调用

熟悉函数式编程的话会想起不动点组合子，也就是构造一个函数，返回它的不动点

1
2
fix :: (a -> a) -> a
fix f = let {x = f x} in x

抄不动了，我也不熟悉函数式啊…..但是直接用C++还是会写的…

函数式编程工具箱

把函数看作一等公民

传统的 C++ 把承载数据的变量作为一等公民，这些变量享有以下权利：

1、可以承载数据，也可以存在于更高级的数据结构中；

2、可以作为右值参与计算、函数调用；

3、可以作为左值参与赋值操作。

那么，如果把函数也当做一等公民，那么，函数也应当享有以下的权利：

1、函数就是数据，一个函数变量可以承载函数，也可以存在于更高级的数据结构中；

2、可以作为右值参与计算，或参与更高级的函数调用；

3、可以作为左值参与赋值操作。

这里给一个简单计算器的例子来理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <functional>
#include <cmath>
#include <map>

using namespace std;

int main(int argc, char**argv) {
	std::map<char, std::function<double(double, double)> > host;
	host['+'] = [](double a, double b)->double { return a + b; };
	host['-'] = [](double a, double b)->double { return a - b; };
	host['*'] = [](double a, double b)->double { return a * b; };
	host['/'] = [](double a, double b)->double { return a / b; };
	host['^'] = [](double a, double b)->double { return pow(a, b); };
	cout << "1.1 + 2.2= " << host['+'](1.1, 2.2) << endl; // => 3.3
	cout << "1.1 - 2.2= " << host['-'](1.1, 2.2) << endl; // => -1.1
	cout << "1.1 * 2.2= " << host['*'](1.1, 2.2) << endl; // => 2.42
	cout << "1.1 / 2.2= " << host['/'](1.1, 2.2) << endl; // => 0.5
	cout << "1.1 ^ 2.2= " << host['^'](1.1, 2.2) << endl; // => 1.23329

	return 0;
}

这里我们使用了标准库提供的std::map来存储核心匹配关系，即一个运算符对应一个运算关系

这时map存储的数据不再是数字，而是一个具体的函数，一种具体的运算方法，这就是刚刚提到的公民权利的第一条和第三条(‘+’作为一个函数载体，作为左值)

而第二条：作为右值参与计算或参与更高级的函数调用，根据以下的三个工具来理解

基本工具

map，filter，fold分别表示对集合而言的三种操作：映射、筛选、折叠

映射

映射操作：对一个列表vec内的所有元素依照某种运算法则f进行运算，从而得到一个全新的列表[f(x) for x in vec]，这确实是一个基于列表的循环操作

提到函数式编程时，遵循两个原则：

1、DRY(Don’t Repeat Yourself)，一个组件只有一次实现，绝不特化过多的实现

2、重视逻辑推演而非执行过程，侧重如何通过逻辑上的组合、推演，来完备的定义问题的解，执行过程交给计算机即可

STL中提供了两个工具：std::for_each和std::transform，后者支持更好甚至支持两个列表同时计算

for_each写法比for+auto复杂，关键是还保证了顺序执行，相比for优势全无，不过这一点也可以使它应用于一个非纯函数的工具

纯函数是指没有副作用、没有后继状态变化，对相同输入总会反馈相同结果的一类特殊函数

某种意义上说，函数式编程(尽量)要求使用纯函数从而方便测试(反馈唯一)、维护(没有副作用)、自动并行化(没有后继的状态变化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char**argv) {
	std::vector<int> a = { 1,2,3,4 };
	int sum = 0, idx = 1, sum2 = 0;
	auto add_to_sum = [&sum](int _) {sum += _; };
	auto add_to_sum_with_idx = [&sum2, &idx](int _) {sum2 += (_ * idx++); };
	
	for (auto e : a) cout << " " << e;
	cout << endl;	
	for_each(a.begin(), a.end(), add_to_sum);
	cout << sum << endl;	// 1+2+3+4
	for_each(a.begin(), a.end(), add_to_sum_with_idx);
	cout << sum2 << endl;	// 1 * 1 + 2 * 2 + 3 * 3 + 4 * 4
	//可以考虑差比数列求和 AP * GP，这里只是个简单的非纯函数例子

	return 0;
}

回到transform，它不保证按序执行，它要求函数不改变迭代器（比如delete）或者修改范围内部元素（比如把下一个元素的值+1）

同时transform要求有返回值，每执行一次都会把结果存储在一个新的列表中

transform允许同时接受两个列表，但是此时要求后者的长度必须大于等于前者的长度，否则会产生未定义行为(Undefined Behavior)

实际上transform也可以实现就地操作，只要把输出的迭代器位置变换成自己的begin()就可以了

举个简单的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char**argv) {
	std::vector<int>a = { 1,2,3,4,5,6 };
	std::vector<int>b;
	std::transform(a.begin(), a.end(), std::back_inserter(b),
		[](int _)->int { return _ + 3; });
	//遍历a，每个数据+3后插入到vector b中

		return 0;
}

筛选

映射是所有操作的根基，因为所有操作都可以用映射进行解释，筛选和折叠也不例外

筛选：对一个列表内的所有元素应用一个谓词(predicate，谓词特指判断事物返回True或False的函数)，然后取出所有结果为True的元素，简单地说就是for循环 + if-else判断

STL提供了copy_if和remove_if来实现筛选，给出一个实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char**argv) {
	auto print_value = [](auto v) {for (auto e : v)cout << " " << int(e); cout << endl; };
#define DISPLAY_VALUE(v)do{cout<<#v":";print_value(v);}while(0);
	std::vector<int> a = { 1,2,3,4,5,6,7,8,9,0 };
	std::vector<int> b;
	std::copy_if(a.begin(), a.end(), std::back_inserter(b),
		[](int _) {return _ % 2; });
	DISPLAY_VALUE(a);
	DISPLAY_VALUE(b);

	a.erase(std::remove_if(a.begin(), a.end(), [](int _) { return _ % 2; }), a.end());
	DISPLAY_VALUE(a);
#undef DISPLAY_VALUE
	// 输出结果
	// a: 1 2 3 4 5 6 7 8 9 0
	// b: 1 3 5 7 9
	// a: 2 4 6 8 0
	
	return 0;
}

需要注意的是，copy_if需要额外开一块空间出来，remove_if则返回了需要删掉的元素的迭代器，然后再通过erase函数彻底删除元素

与transform类似，这里的谓词函数同样要求不得修改原始数据

折叠

折叠：对一个列表和一个初始值应用一个二元函数，然后依次按某一特定方向将整个列表折叠起来

看完代码就能理解这个描述了

STL中提供了accumulate和inner_product，两者都是左折叠函数，分别是执行求和、计算向量内积的函数

后者实际上是先对两个列表应用一个二元运算（默认乘法），把结果存入一个列表中，再对这个列表折叠（默认求和）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>

using namespace std;

int main(int argc, char**argv) {
	auto print_value = [](auto v) {for (auto e : v)cout << " " << int(e); cout << endl; };
#define DISPLAY_VALUE(v)do{cout<<#v":";print_value(v);}while(0);
	std::vector<int> a = { 1,2,3,4,5,6,7,8,9,10 };
	int sum = std::accumulate(a.begin(), a.end(), 0,
		[](int acc, int _) { return acc + _; });
	cout << sum << ", ";
	DISPLAY_VALUE(a);
	// 55, a: 1 2 3 4 5 6 7 8 9 10

	int prod = std::accumulate(a.begin(), a.end(), 1,
		[](int acc, int _) { return acc * _; });
	cout << prod << ", ";
	DISPLAY_VALUE(a);
	// 3628800, a: 1 2 3 4 5 6 7 8 9 10

	//反转vector
	std::vector<int> a_re = std::accumulate(a.begin(), a.end(), std::vector<int>(),
		[](std::vector<int> acc, int _)->std::vector<int> {
		std::vector<int> __; __.push_back(_);
		std::copy(acc.begin(), acc.end(), std::back_inserter(__));
		return __;
	});
	DISPLAY_VALUE(a_re);
	// a_re: 10 9 8 7 6 5 4 3 2 1

#undef DISPLAY_VALUE

	return 0;
}

简单地说，应用的二元函数的第一个参数是累加值，第二个参数是列表中取出的值，返回值的类型应与初值和累加值的类型相同（熟练以后可以用auto代替）

最后一个反转vector略有一点难度，如果看不懂可以输出中间结果看看

考虑一个问题，由于C++依旧是基于面向过程和面向对象的语言，所以在函数式编程上的优化可能没有那么专业，而且C++会按语句依次执行，如果大量堆叠transform会不会造成性能下降呢？

这就是之后将要引入的内容：是否引入简单的lazy求值，以及简单的柯里化

题外话：这里我突然想到了一些东西，当看到这句话期末考完可能得等，它是很不符合语法的语句，但是我们可以轻易得知语句表达的含义。我猜测，眼睛读取信息时并行的读入这8个汉字，然后由大脑根据词组进行全排列，比如这8个字分成了四个词组，然后匹配最佳语义（又能扯到SFINAE了吗…）

函数的部分应用

在处理柯里化之前，我们先思考这个问题：如何对一个函数进行部分应用

举个例子，比如最常见的除法a/b，能否只传递其中的一个参数给这个除法运算，从而得到一个接收另一个参数的函数？话很绕口，但是代码不绕口

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>

using namespace std;

int main(int argc, char**argv) {
	auto div = [](int a, int b)->int { return a / b; };
	auto div3 = [div](int a)->int {return div(a, 3); };
	auto ten_div = [div](int b)->int {return div(10, b); };
	cout << div(10, 3) << " " << div3(10) << " " << ten_div(3) << endl;
	// 输出都是3
	return 0;
}

这只是个简陋的例子，看不出来这有什么用……

再给出使用std::bind()的更优雅（繁琐）的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <functional>

using std::cout;
using std::endl;

void f(int x, int y, const int &z){
	cout << "=> f(" << x << ", " << y << ", " << z << ")" << endl;
}

int g(int x, int y, int z) { return x + y * z; }


int main(int argc,char**argv){
	using namespace std::placeholders;
	int n = 5;
    //std::placeholders::_1,_2... 占位符
	auto fyx5 = std::bind(f, _2, _1, n);
	fyx5(1, 2); // => f(2, 1, 5)
	auto f5yy = std::bind(f, n, std::ref(n), std::cref(n));
	f5yy(); // => f(5, 5, 5)
	n += 2; f5yy(); // => f(5, 7, 7)

	auto gxxx = std::bind(g, _1, _1, _1);
	cout << "5 + 5 * 5 = " << gxxx(5) << endl; // => 5 + 5 * 5= 30
    //这里gxxx(5,1,2,3,4,5)的结果也是一样的，因为占位符都用的第一个参数
    
	auto gx45 = std::bind(std::bind(g, _1, _2, 5), _1, 4);
    //内层std::bind返回一个函数对象，绑定了第三个参数；外层则绑定第二个参数
	cout << "3 + 4 * 5 = " << gx45(3) << endl; // => 3 + 4 * 5= 23

	return 0;
}

这个例子其实并没有做到部分应用，只是使用了占位符std::placeholders::_1,_2,...来实现效果

std::bind()的参数默认是值传递，若需要引用传递，必须使用std::ref()或std::cref()

更好的写法，一个简单的柯里化尝试

1
2
3
4
5
6
7
auto c_xor = [](char _1)->auto{
		return[_1](char  _2)->auto{
			return [_1, _2](char _3) {
				return _1 ^ _2 ^ _3;
			};
		};
	};

可以这样调用 char c = c_xor('a')('b')('c');

柯里化

我们不想为了柯里化而柯里化，把每一个函数的声明都写的十分冗长；也不想用std::bind每次都把所有参数写出来，形式不够简洁

两个方案

1、需要额外手动维护一个记录参数的容器

2、利用变长模板进行函数包装

把元组应用到函数上

原本函数调用是由编译器来托管所有参数进栈出栈，现在只能一次来一个参数，自然会想到用一个容器来托管所有参数，一旦调用，就把这些参数都喂给原始函数

当然是选择tuple了…但是如果能直接把tuple内的参数直接喂给函数就好了

最近的C++17标准中提供了apply函数来完成这一操作

这里我们自己写一份

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<tuple>
#include<utility>
#include<functional>

using namespace std;

template<class Func, class Tuple, std::size_t... I>
constexpr auto tuple_apply_impl(Func&& f, Tuple&& t,
	std::index_sequence<I...>) {
	return std::invoke(std::forward<Func>(f), std::get<I>(std::forward<Tuple>(t))...);
	// 如果f的范围限定为函数对象
    // 那么f(args...)和std::invoke(f,args...)是完全等价的
}

template<class Func, class Tuple>
constexpr auto tuple_apply(Func&& f, Tuple&& t) {
	return tuple_apply_impl(
		std::forward<Func>(f), std::forward<Tuple>(t),
		std::make_index_sequence<std::tuple_size<std::remove_reference_t<Tuple>>::value>{} 
		// 借助std::make_index_sequence<>在编译时把下标序列构造出来
		// 然后应用到std::get<I>上
	);
}


int main(int argc, char**argv) {
	auto add = [](int a, int b)->int { return a + b; };
	auto add_3_nums = [](int a, int b, int c)->int { return a + b + c; };
	cout << std::apply(add, std::make_pair(1, 2)) << endl;
	cout << std::apply(add_3_nums,std::make_tuple(1,2,3))<< endl;
	
	cout << tuple_apply(add,std::make_pair(1,2)) << endl;
	// 这里编译后就会执行 std::invoke(add,std::get<0>(t),std::get<1>(t))
	
	cout << tuple_apply(add_3_nums,std::make_tuple(1,2,3)) << endl;
	// 3 6 3 6
	return 0;
}

// g++-7 main.cpp -std=c++17 编译成功，vs的C++版本不够

function_traits

如何判断这个函数需要多少个参数呢？

这里我们需要写一个类型判断器，把函数解构，获取一个函数的必要信息：返回类型(return type)是什么，参数(arity)需要多少个，每一个参数的类型(argument type)是什么

我们把这些东西包装到一个function_traits类型中

并且把函数的类型规范到形如std::function<Return(Args...)>

当然为了确保我们的类型是真实可靠的，借助于C++非常严格的类型检验功能std::is_same<U,V>::value，同时借助typeid().name()把这个类型具体是什么输出出来

如果使用的是GCC，typeid().name()会得到编译器装饰过的类型别名(decorated name)，难以阅读

这里使用GCC自带的工具c++filt或者__cxa_demagle来帮助把类型名替换为代码中的原始名称

这里使用的是后者，并且用函数realname()帮助我们把类型直接转成正常形式

学习于 知乎专栏，遗憾的是我这里g++-7跑不了这个代码，在宏相关的地方有报错，但是我不会debug…

贴一下function_traits.hpp的代码，后面可以正常使用，我并没有尝试理解这段代码…

后面的两段柯里化代码都需要借助这份hpp头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
// filename: function_traits.hpp
#ifndef __FUNCTION_TRAITS_HPP__
#define __FUNCTION_TRAITS_HPP__
namespace __utils{

template <class F> struct function_traits;

// normal function, static member function
template <class Return, class...Args>
struct function_traits<Return(Args...)>
{
    using func_type = std::function<Return(Args...)>;
    using return_type = Return;
    static constexpr std::size_t arity = sizeof...(Args);
    template <std::size_t I> struct argument
    {
        static_assert(I < arity,
            "error: invalid index of this function's parameter.");
        using type = typename 
            std::tuple_element<I, std::tuple<Args...>>::type;
    };
};

// function pointer, &f
template <class Return, class...Args>
struct function_traits<Return(*)(Args...)>
    : public function_traits<Return(Args...)> {};

// std::function
template <class Return, class...Args>
struct function_traits<std::function<Return(Args...)>>
    : public function_traits<Return(Args...)> {};

// functor, callable object, struct with overloaded operator()
template <typename Functor>
struct function_traits
    : public function_traits<decltype(&Functor::operator())> {};

// lambda expression, const member function pointer
template <class Class, class Return, class...Args>
struct function_traits<Return(Class::*)(Args...) const>
    : public function_traits<Return(Args...)> {};

// member function pointer
template <class Class, class Return, class...Args>
struct function_traits<Return(Class::*)(Args...)>
    : public function_traits<Return(Args...)> {};

// member object pointer
template <class Class, class Return>
struct function_traits<Return(Class::*)> : public function_traits<Return()> {};

// clear reference F&, F&&
template <class F> struct function_traits<F&> : public function_traits<F> {};
template <class F> struct function_traits<F&&> : public function_traits<F> {};

// make_func(), return a std::function<> object from function-like object
template <class Func> auto make_func(Func && f)
{
    typename function_traits<Func>::func_type _f = std::forward<decltype(f)>(f);
    return std::forward<decltype(_f)>(_f);
}

// arity(), return numbers of parameters
template <class Func> inline constexpr std::size_t arity(Func &&)
{
    return function_traits<std::remove_reference_t<Func>>::arity;
}

// argument_type<Func, I>::type, return I-th parameter's type, I start from 0
template <class Func, std::size_t I> struct argument_type
{
    using type = typename function_traits<Func>::template argument<I>::type;
};

} // namespace __utils
#endif // __FUNCTION_TRAITS_HPP__

实现柯里化包装器

我们的要求依旧和之前一样，既要保持函数不必每次重写，也要保证形式上的简洁性

最初已经提到了这两个方案，顺着这个思路往下走

1、需要额外手动维护一个记录参数的容器

2、利用变长模板进行函数包装

带有一定lazy程度的currying

既然已经知道如何把元组应用到函数上了，那么只需要手动维护这个元组就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <tuple>
#include <functional>
#include <cassert>

using std::cout;
using std::endl;

#include "function_traits.hpp"

template <class Func, class Tuple, std::size_t... I>
constexpr auto tuple_apply_impl(const Func &f, Tuple && t, std::index_sequence<I...>)
{
    return f(std::get<I>(std::forward<Tuple>(t))...);
}

template <class Func, class Tuple>
constexpr auto tuple_apply(Func && f, Tuple && t)
{
    return tuple_apply_impl( std::forward<Func>(f), std::forward<Tuple>(t),
        std::make_index_sequence<std::tuple_size<std::remove_reference_t<Tuple>>::value>{});
}

template <class Func, class Tuple = std::tuple<> >
class curried_functor
{
private:
    Func f_;
    Tuple t_;
    std::size_t argc_;
    using final_ret_type = typename __utils::function_traits<Func>::return_type;
public:
    curried_functor(Func && f)
        : f_(std::forward<Func>(f)), argc_(__utils::arity(f_)) {}
    curried_functor(const Func &f, const Tuple &t)
        : f_(f), argc_(__utils::arity(f_)), t_(t) {}
    template <class... Args>
    auto operator()(Args&&... args) const -> final_ret_type
    {
        std::size_t tuple_len = std::tuple_size<Tuple>::value;
        std::size_t args_len = sizeof...(args);
        assert(tuple_len + args_len == argc_); // test if parameters don't match!
        auto argv = std::tuple_cat(t_, std::make_tuple(std::forward<Args>(args)...));
        return tuple_apply(f_, argv);
    }
    template <class Arg> auto curry(Arg && arg) const
    {
        std::size_t tuple_len = std::tuple_size<Tuple>::value;
        std::size_t arg_len = 1;
        assert(tuple_len + arg_len <= argc_); // test if too much curry!
        auto argv = std::tuple_cat(t_, std::make_tuple(std::forward<Arg>(arg)));
        return curried_functor<Func, decltype(argv)>(f_, argv);
    }
};

template <class Func> auto curry(Func && f)
{
    auto _f = __utils::make_func(f);
    return curried_functor<decltype(_f)>(std::forward<decltype(_f)>(_f));
}

#define DISPLAY(expr) do { cout << #expr"= " << expr << endl; } while (0);

int main()
{
    cout << "-------- 4 - 5= ? --------\n";
    auto sub = [](int a, int b)->int{ return a - b; };
    auto curried_sub = curry(sub);
    auto curried_sub_4 = curried_sub.curry(4);
    DISPLAY(curried_sub(4, 5)); // => -1
    DISPLAY(curried_sub_4(5)); // => -1
    DISPLAY(curried_sub.curry(4).curry(5)()); // => -1

    cout << "-------- 2 * 3 * 4= ? --------\n";
    auto mul3 = curry([](int a, int b, int c)->int{ return a * b * c; });
    DISPLAY(mul3(2, 3, 4)); // => 24
    DISPLAY(mul3.curry(2)(3, 4)); // => 24
    DISPLAY(mul3.curry(2).curry(3)(4)); // => 24
    DISPLAY(mul3.curry(2).curry(3).curry(4)()); // => 24
    return 0;
}

代码中的柯里化是具备了一定的lazy功能的，只有外部显式调用operator()的时候才会进行计算

但是这样并没有完全lazy计算，因为传参时，我们传递的值，而不是参数的计算定义或计算路径

仍然是看不懂，可能这就是库的作用吧

知乎专栏

把函数包装托管给编译器

利用模板特化，把函数包装托管给编译器

但是这里的柯里化就不再是延时求值了，而是每一次柯里化都返回一个真实的函数对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <tuple>
#include <functional>
#include <cassert>

using std::cout;
using std::endl;

#include "function_traits.hpp"

//这两个函数规定了一元函数和零元函数的柯里化规则
//在有了这个终止递归条件之后，我们就可以用变长模板来定义更一般的柯里化规则
template <class Return>
auto curry_impl(std::function<Return()> && f){
	return std::forward<decltype(f)>(f);
}

template <class Return, class Arg>
auto curry_impl(std::function<Return(Arg)> && f){
	return std::forward<decltype(f)>(f);
}



//在这里，所有的参数和函数对象都用右值引用进行转发，保证效率和值的不变性
//然后只需要把第一个参数写到调用列表就行了
//最后，[通过`function_traits::func_type`把函数规整到`std::function`对象]这一功能
//被我们封装到了curry()函数中
template <class Return, class Arg, class... Args>
auto curry_impl(std::function<Return(Arg, Args...)> && f){
	return[f = std::forward<decltype(f)>(f)](Arg arg){
		std::function<Return(Args...)> rest
			= [f = std::forward<decltype(f)>(f), arg = std::forward<Arg>(arg)]
			(Args... args)->Return { return f(arg, args...); };
		return curry_impl(std::forward<decltype(rest)>(rest));
	};
}


template <class Func> auto curry(Func && f){
	auto _f = __utils::make_func(f);
	return curry_impl(std::forward<decltype(_f)>(_f));
}


#define DISPLAY(expr) do { cout << #expr"= " << expr << endl; } while (0);

int main(int argc,char**argv){
	cout << "-------- subtraction --------\n";
	auto sub = [](int a, int b)->int { return a - b; };
	auto curried_sub = curry(sub);
	//使用时，可以保持原函数的写法不做改变，只需要外部对其进行一次curry()修饰即可
	auto curried_sub_4 = curried_sub(4);
	DISPLAY(curried_sub_4(5)); // => -1
	DISPLAY(curried_sub(4)(5)); // => -1

	cout << "-------- multiplication --------\n";
	auto mul3 = curry([](int a, int b, int c)->int { return a * b * c; });
	//curry()修饰
	DISPLAY(mul3(2)(3)(4)); // => 24
	DISPLAY(mul3(3)(4)(5)); // => 60
	DISPLAY(mul3(4)(5)(6)); // => 120
	DISPLAY(mul3(5)(6)(7)); // => 210
	return 0;
}

由于使用了模板特化来实现柯里化，为了保证编译不出错（变长模板展开需要有一个终止条件），所以在特化时我们只处理了没有参数和只有一个参数的情形

这样也严格的执行了柯里化的定义，即函数永远只接收一个参数，同时也确保了返回值是一个函数对象而不是之前那种包装了参数数据的特殊数据结构

函数组合

引入管道概念

管道是linux中一种特殊的文件，程序可以读取管道的数据，也可以把数据写到管道里传递给其他程序

比如ps -aux --sort -pcpu | less是最经典的检查CPU占用的命令

我们可以粗略的认为，运算符|接收两个参数lhs和rhs，左端提供数据，右端提供函数

重载|运算符

1
2
3
4
template <class Arg, class F>
auto operator|(Arg && arg, F && f) -> decltype(f(std::forward<Arg>(arg))) {
	return f(std::forward<Arg>(arg));
}

可以写出这样的代码

1
2
3
4
5
int result = 5 | [](int _) { return _ * 2; };

cout << (2 | [](int _) { return _ + 5; }
		  | [](int _) { return _ * 2; }
		  | [](int _) { return "result= " + std::to_string(_); }) << endl;

如果没有lambda支持，同样的功能可能单是函数声明就十分麻烦，千言万语不及一句随用随写

只要管道不要数据

现在假设我们有这样的一个管道链a | f | g，我们不再关心数据a，而关心函数的组合| f | g

其实就是f(g(x))

注意到每一个函数的类型都可能是不同的，而这是一个线性结构，所以选用tuple作为核心容器记录所有的函数；同时，对外公开两个方法composite()和operator()用于处理新函数和执行函数调用，内部则用递归的方法把函数一次调用

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<string>
#include<tuple>
#include<functional>

using namespace std;

template <class Arg, class F>
auto operator|(Arg && arg, F && f) -> decltype(f(std::forward<Arg>(arg))){
	return f(std::forward<Arg>(arg));
}

template <class... Fs>
class composited_functor{
private:
	const std::tuple<Fs...> fs_;
	const static std::size_t _size_ = sizeof...(Fs);

	template <class Arg, std::size_t I>
	auto call_impl(Arg && arg, const std::index_sequence<I>&) const
		-> decltype(std::get<I>(fs_)(std::forward<Arg>(arg))){
		return std::get<I>(fs_)(std::forward<Arg>(arg));
	}

	template <class Arg, std::size_t I, std::size_t... Is>
	auto call_impl(Arg && arg, const std::index_sequence<I, Is...>&) const
		-> decltype(call_impl(std::get<I>(fs_)(std::forward<Arg>(arg)), std::index_sequence<Is...>{}))
	{
		return call_impl(std::get<I>(fs_)(std::forward<Arg>(arg)), std::index_sequence<Is...>{});
	}

	template <class Arg> auto call(Arg && arg) const
		-> decltype(call_impl(std::forward<Arg>(arg), std::make_index_sequence<_size_>{})){
		return call_impl(std::forward<Arg>(arg), std::make_index_sequence<_size_>{});
	}
public:
	composited_functor() : fs_(std::tuple<>()) {}
	composited_functor(std::tuple<Fs...> && fs) : fs_(std::forward<decltype(fs)>(fs)) {}

	template <class F>
	inline auto composite(F && f) const{
		return composited_functor<Fs..., F>(std::tuple_cat(fs_, std::make_tuple(std::forward<F>(f))));
	}

	template <class Arg>
	inline auto operator()(Arg && arg) const{
		return call(std::forward<Arg>(arg));
	}
};

template <class... Fs, class F>
auto operator,(composited_functor<Fs...> && composited, F && f){
	return composited.composite(std::forward<F>(f));
}


int main(int argc, char**argv) {
	cout << (
        2 | ( composited_functor<>()
		 , [](int _) { return _ + 5; }
		 , [](int _) { return _ * 2; }
		 , [](int _) { return "result = " + std::to_string(_); } ) 
    		)
          << endl;
	// result = 14
	return 0;
}

haskell里用.运算符来表示函数组合，因为C++不允许重载这个操作符…….

这不是bug，这是feature

于是这里重载了逗号运算符

这种写法…composited_functor<>()太碍眼了，完全可以不需要的，我们换个思路重新考虑一下这个问题

特殊的应用符

Haskell里有一个特殊的运算符$来消除括号，同样地我们也可以引入C++中，Haskell中$定义如下

1
2
($) :: (a -> b) -> a -> b
f $ x = f x

换句话说就是可以不写括号，直接把数据应用到函数上

由于C++不能创建新的运算符，只好曲线救国，换一个运算符来实现功能

这里选择operator<<

注意需要function_traits.hpp头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<string>
#include<tuple>
#include<functional>

#include"./function_traits.hpp"

template <class Arg, class F>
auto operator|(Arg && arg, F && f) -> decltype(f(std::forward<Arg>(arg))){
	return f(std::forward<Arg>(arg));
}

// ($) :: (a -> b) -> a -> b
// f $ x = f x
template <class Return, class Arg>
auto operator<<(std::function<Return(Arg)> && f, Arg && arg){
	return f(std::forward<Arg>(arg));
}

template <class Return>
auto curry_impl(std::function<Return()> && f){
	return std::forward<decltype(f)>(f);
}

template <class Return, class Arg>
auto curry_impl(std::function<Return(Arg)> && f){
	return std::forward<decltype(f)>(f);
}

template <class Return, class Arg, class... Args>
auto curry_impl(std::function<Return(Arg, Args...)> && f){
	auto _f = [f = std::forward<decltype(f)>(f)](Arg arg){
		std::function<Return(Args...)> rest
			= [f = std::forward<decltype(f)>(f), arg = std::forward<Arg>(arg)]
			(Args... args)->Return { return f(arg, args...); };
		return curry_impl(std::forward<decltype(rest)>(rest));
	};
	return __utils::make_func(_f);
}

template <class Func> auto curry(Func && f){
	auto _f = __utils::make_func(f);
	return curry_impl(std::forward<decltype(_f)>(_f));
}


// (.) :: (b -> c) -> (a -> b) -> a -> c
// f . g = \x -> f $ g x
template <class MaybeA, class MaybeB, class MaybeC>
auto operator<<(std::function<MaybeC(MaybeB)> && f, std::function<MaybeB(MaybeA)> && g)
-> std::function<MaybeC(MaybeA)>{
	std::function<MaybeC(MaybeA)> composited
		= [f = std::forward<decltype(f)>(f), g = std::forward<decltype(g)>(g)]
		(MaybeA arg)->MaybeC { return f(g(arg)); };
	return __utils::make_func(composited);
}


int main(int argc, char**argv) {
	std::cout << ( curry( [](int _) { return _ + 5; } )  << 4 )
		      << std::endl;
	// 9 

	std::cout << 
		( 
			curry( [](int _) { return "result= " + std::to_string(_); } )
		 << curry( [](int _) { return _ * 2; } )
		 << curry( [](int _) { return _ + 5; } )
		 << 4 
		)
			  << std::endl;
	// => result= 18

	return 0;
}

很像 Haskell 的 f $ g $ h x ，不过得益于 lambda 代码不至于过于冗长

现在我们手上已经有了柯里化和函数组合这两个工具了。借助这两个工具，我们可以非常自然地把逻辑用函数来进行抽象，把参数的传递用柯里化来代替，从而更简单的组合我们的代码，更大限度的减少不良代码。这里需要再次强调一次，那就是DRY 原则，不要反复重复没用的代码。编程的最大乐趣在于一层一层的把逻辑抽象，从而用简洁的代码，通过一层一层的组合、堆叠，完成一个又一个复杂的任务。可能之前我们手上只有一种实现的方法，而现在道路多了之后，就会大大地解放我们的思路，方便我们思考出最适合自己的一条实现方案。

吾头在否？

发表于 | 阅读次数:

介绍一些基本技巧，本文是很多博客和书籍的学习笔记，各部分内容可能会有少许重复

其中的代码我虽然已经写了很多遍了，但是让我不看资料……我还真写不出来

权当自己存的编译期代码库吧

越来越感觉自己代码量的不足，这么菜还怎么看chromium里10个G的C++代码

元函数与type_traits

类型元函数

考虑如下情形：我们希望进行类型映射F，F(int)=unsigned int，F(long)=unsigned long

这种映射可以看成函数，只不过输入和输出都是类型而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename T>	//输入(模板参数)
struct Fun_ { using type = T; };

template<>		//特化（映射）
struct Fun_<int> { using type = unsigned int; };

template<>		//特化（映射）
struct Fun_<long> { using type = unsigned long; };

Fun_<int>::type num = 3;	//unsigned int num = 3;

template<typename T>
using Fun = typename Fun_<T>::type;

Fun<int> num1 = 3;

Fun不是一个标准的元函数，因为它没有内嵌类型type。但是它具有输入(T)，输出(Fun)，也明确定义了映射规则，因此可以视作元函数。

事实上，代码中展示的也是C++标准库中定义元函数的常用方式，比如std::enable_if和std::enable_if_t，前者就像Fun_一样是内嵌了type类型的元函数；后者像Fun一样是基于前者给出的定义，用于简化使用。

命名方式

此处约定如下：如果函数返回值需要用某种依赖型的名称表示，那么函数被命名为XXX_的形式（以下划线为后缀）；反之非依赖型则不包含下划线

1
2
3
4
5
6
7
8
9
10
11
template<int a,int b>
struct Add_ {	//依赖型
	constexpr static int value = a + b;
	//value静态变量，依赖于Add_存在
};

template<int a,int b>	//非依赖型
constexpr int Add = a + b;	

constexpr int x1 = Add_<2, 3>::value;
constexpr int x2 = Add<2, 3>;

type_traits

type_traits是由boost库引入的，由C++11纳入其中，头文件，实现了类型变换、类型比较与判断等功能。

1
2
3
4
#include<type_traits>

std::remove_reference<int&>::type num1 = 3;
std::remove_reference_t<int&> num2 = 4;

更多的一些用于编译期判断的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <type_traits>

using namespace std;

int main() {
	std::cout << "int: " << std::is_const<int>::value << std::endl;
	std::cout << "const int: " << std::is_const<const int>::value << std::endl;

	//判断类型是否相同
	std::cout << std::is_same<int, int>::value << "\n";// true
	std::cout << std::is_same<int, unsigned int>::value << "\n";// false

	//添加、移除const
	cout << std::is_same<const int, add_const<int>::type>::value << endl;
	cout << std::is_same<int, remove_const<const int>::type>::value << endl;

	//添加引用
	cout << std::is_same<int&, add_lvalue_reference<int>::type>::value << endl;
	cout << std::is_same<int&&, add_rvalue_reference<int>::type>::value << endl;

	//取公共类型
	typedef std::common_type<unsigned char, short, int>::type NumericType;
	cout << std::is_same<int, NumericType>::value << endl;

	return 0;
}

还有一个朽化(std::decay)操作

为类型T应用从左值到右值（lvalue-to-rvalue）、数组到指针（array-to-pointer）和函数到指针（function-to-pointer）的隐式转换。转换将移除类型T的cv限定符（const和volatile限定符），并定义结果类型为成员decay::type的类型。

1
2
3
4
5
6
typedef std::decay<int>::type A;           // int
typedef std::decay<int&>::type B;          // int
typedef std::decay<int&&>::type C;         // int
typedef std::decay<constint&>::type D;     // int
typedef std::decay<int[2]>::type E;        // int*
typedef std::decay<int(int)>::type F;      // int(*)(int)

朽化还可以将函数类型转换成函数指针类型，从而将函数指针变量保存起来，以便在后面延迟执行

using FnType = typename std::decay::type;实现函数指针类型的定义

（暂时不太理解，可能与惰性求值有关）

编译期类型推导

auto

NULL

decltype

RTTI机制为每一个类型产生一个type_info类型的数据，而typeid查询返回的变量相应type_info数据，通过name成员函数返回类型的名称，同时C++11中typeid还提供了hash_code这个成员函数用于返回类型的唯一哈希值

泛型编程中我们需要的就是编译时确定类型，RTTI无法满足这样的要求；

而编译时类型推导，除了auto，还有就是decltype

decltype并不是像auto一样从变量声明的初始化表达式获得类型，而是以一个普通表达式作为参数，返回该表达式的类型，而且decltype并不会对表达式进行求值

推导表达式类型

1
2
int i = 4;
decltype(i) a;	//推导结果为int，a的类型为int

定义类型

与using/typedef合用，用于定义类型

1
2
3
4
5
6
7
using size_t = decltype(sizeof(0));	// 返回值为size_t类型

vector<int> vec;
typedef decltype(vec.begin()) vectype;
for (vectype i = vec.begin(); i != vec.end(); i++) {
	// ...
}

重用匿名类型

举个例子：重新使用匿名结构体

1
2
3
4
5
6
struct {
	int x;
	double y;
}anon_s;

decltype(anon_s) as;

追踪函数返回类型

结合auto，这也是decltype最大的用途

1
2
3
4
template <typename _Tx, typename _Ty>
auto multiply(_Tx x, _Ty y)->decltype(_Tx*_Ty){
    return x*y;
}

结合右值引用和完美转发，更能体现这一点

1
2
3
4
template <class Arg, class F>
auto operator|(Arg && arg, F && f) -> decltype(f(std::forward<Arg>(arg))){
    return f(std::forward<Arg>(arg));
}

模板型模板参数&容器模板

C++元函数可以操作的数据包含3类：数值、类型与模板，统一被称作元数据，以示与运行期所操作的数据的区别。

模板作为元函数的输入

1
2
3
4
5
6
7
8
9
10
11
#include<type_traits>
template< template<typename>class T1, typename T2 >
struct Fun_ {
	using type = typename T1<T2>::type;
};

template< template<typename>class T1, typename T2 >
using Fun = typename Fun_<T1, T2>::type;

Fun<std::remove_reference, int&> num1 = 3;
Fun_<std::remove_reference, int&>::type num2 = 4;

其中元函数Fun接收两个参数：一个模板和一个类型

从函数式编程的角度来说，Fun是一个典型的高阶函数，即以另一个函数为输入参数的函数

总结为数学表达式 $Fun(T_1,t_2)=T_1(t_2)$

而模板作为元函数的输出相关内容在实际中使用较少，就不介绍了（其实是我不会）

容器模板

我们需要的是一个容器：用来保存数组中的每个元素，元素可以是数值、类型或模板。典型的容器仅能保存相同类型的数据，但已经可以满足绝大多数的使用需求。

C++11中引入了变长参数模板(variadic template)，借由此实现我们的容器

1
2
3
4
5
6
7
8
template<int... Vals> struct IntContainer;
template<typename... Types> struct TypeContainer;

template<template<typename>class... T>struct TemplateCont;
//可以存放模板作为其元素，每个模板元素可以接收一个类型作为参数

template<template<typename...>class... T>struct TemplateCont2;
//同样以模板作为其元素，但每个模板可以放置多个类型信息

这些语句实际上只是声明而非定义，事实上这是一个元编程中的一个惯用法：仅在必要时才引入定义，其他的时候直接使用声明即可。

关于变长参数模板后文还会提到

顺序、分支与循环

顺序执行

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<type_traits>
template<typename T>
struct RemoveReferenceConst_ {
private:	//private确保函数的使用者不会误用中间结果inter_type作为返回值
	using inter_type = typename std::remove_reference<T>::type;
public:		
	using type = typename std::remove_const<inter_type>::type;
};

template<typename T>
using RemoveReferenceConst = typename RemoveReferenceConst_<T>::type;

RemoveReferenceConst<const int&> num = 1;

代码中先根据T计算出inter_type，再用这个中间结果计算出type

结构体中的所有声明都要看成执行的语句，不能更换顺序

这里改变顺序确实会报错，类似地，在下文 分支选择与短路逻辑 中有一些想法

在编译期，编译器会扫描两遍结构体中的代码，第一遍处理声明，第二遍才会深入到函数定义中。

如果先扫描到type，发现它依赖于未定义的inter_type，就不会继续扫描而是报错。

分支执行

std::conditional(_t)

conditional和conditional_t为type_traits中提供的2个元函数，定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
namespace std {
	template<bool B, typename T, typename F>
	struct conditional {
		using type = T;
	};

	template<typename T, typename F>
	struct conditional<false, T, F> {
		using type = F;
	};

	template<bool B, typename T, typename F>
	using conditional_t = typename conditional<B, T, F>::type;
}

注意这里只偏特化了false的情况，但是却可以完美的表达true的情形。

我个人猜测与编译器最佳匹配的实现有关，后面也会提到SFINAE

逻辑行为：如果B为真，则函数返回T，否则返回F

1
2
3
4
5
6
7
8
//测试代码
int main(int argc, char**argv) {
	std::conditional<true, char, int>::type x = 3;
	std::cout << sizeof(x) << std::endl;	// 1 char
	std::conditional_t<false, char, int> y = 4;
	std::cout << sizeof(y) << std::endl;	// 4 int
	return 0;
}

使用特化实现分支

特化天生就是用于引入差异的，因此可以用于实现分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct A; struct B;

template<typename T>
struct Fun_{
	constexpr static size_t value = 0;
};

template<>
struct Fun_<A> {
	constexpr static size_t value = 1;
};

template<>
struct Fun_<B> {
	constexpr static size_t value = 2;
};

constexpr size_t v = Fun_<B>::value;	//依赖型 2
// Fun_<int>::value == 0; <typename> 传入int

Fun_元函数实际上引入了3个分支，分别对应输入参数为A、B与默认情况

这里A和B只是用于特化的类型，因此只需要声明，不需要定义

可能与下一章异类词典中用类名作为键类似

C++14中另一种特化方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>

struct A; struct B;

//非依赖
template<typename T>
constexpr size_t Fun = 0; 

template<>
constexpr size_t Fun<A> = 1;

template<>
constexpr size_t Fun<B> = 2;

constexpr size_t h = Fun<int>;

int main(int argc, char**argv) {
	std::cout << Fun<int><<std::endl;	// 0
	std::cout << Fun<A> << std::endl;	// 1
	return 0;
}

这段代码里特化的2处模板，vs报constexpr在此处无效，不清楚为什么

必须在其首次使用之前对 变量 “Fun [其中 T=A]” 进行显式专用化()

书上提醒：在非完全特化的类模板中引入完全特化的分支代码是非法的

注释代码g++编译失败，vs成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>

template<typename TW>
struct Wrapper {	//包装
	/*
	template<typename T>
	struct Fun_ {
		constexpr static size_t value = 0;
	};

	template<>
	struct Fun_<int> {
		constexpr static size_t value = 1;
	};
	// vs中运行正常
	// g++报错:
	//explicit specialization in non-namespace scope
	//template parameters not deducible in partial specialization
	*/

	template<typename T, typename TDummy = void>
	struct Fun_ {
		constexpr static size_t value = 0;
	};

	template<typename TDummy> // Dummy 挂名，傀儡
	struct Fun_<int, TDummy> {
		constexpr static size_t value = 1;
	};
};

int main(int argc, char**argv) {
	std::cout << Wrapper<int>::Fun_<int>::value;
	return 0;
}

改进后的代码引入了一个伪参数TDummy，用于将原有的完全特化转换为部分特化

但是设定了默认值void，因此可以直接以Fun_<int>调用这个元函数，无需赋值

使用std::enable_if(_t)

1
2
3
4
5
6
7
8
9
10
11
//代码原型
namespace std {
	template<bool B, typename T = void>
	struct enable_if {};

	template<class T>	//这里当然不会直接传true...可以其他计算结果
	struct enable_if<true, T> { using type = T; };

	template<bool B, class T = void>
	using enable_if_t = typename enable_if<B, T>::type;
}

这里T不是特别重要，重要的是当B为true时，enable_if元函数可以返回结果type，可以基于此构造实现分支

代码实例

1
2
3
4
5
6
7
template<bool IsFeedbackOut, typename T,
	std::enable_if_t<IsFeedbackOut>* = nullptr>	//这里多了  * = nullptr，暂时没搞懂作用，
auto FeedbackOut_(T&&) { /*...*/ }

template<bool IsFeedbackOut, typename T,
	std::enable_if_t<IsFeedbackOut>* = nullptr> //可能是习惯用法吧，可作为伪参数？
auto FeedbackOut_(T&&) { /*...*/ }

这里引入分支，根据IsFeedback的值来匹配模板

SFINAE

SFINAE(Substitution Failure Is Not An Error)，译为”匹配失败并非错误”

当匹配模板时，编译器即使已经匹配到了一个足够好的选择，也会把所有选择都尝试匹配，最后选择最佳的

这里std::enable_if(_t)正是利用了这一点

有些情况下，我们希望引入重名函数，它们无法通过参数类型加以区分，这时enable_if(_t)能在一定程度上解决相应的重载问题

补充

std::enable_if(_t)也有一些缺点，并不像模板特化那么直观，可读性较差

这里给出的代码实例是一个典型的编译期与运行期结合的使用方式，FeedbackOut_中包含了运行期的逻辑，而选择哪个FeedbackOut_则是通过编译期的分支来实现

计算实例

利用二分法计算整数的平方根，结果向下取整

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>

template <bool Flag, class MaybeA, class MaybeB> class IfElse;

template <class MaybeA, class MaybeB>
class IfElse<true, MaybeA, MaybeB> {
public:
	using ResultType = MaybeA;
};

template <class MaybeA, class MaybeB>
class IfElse<false, MaybeA, MaybeB> {
public:
	using ResultType = MaybeB;
};

template <int N, int L, int R> struct __Sqrt {
	enum { mid = (L + R + 1) / 2 };

	using ResultType = typename IfElse<(N < mid * mid),
		__Sqrt<N, L, mid - 1>, __Sqrt<N, mid, R> >::ResultType;

	enum { result = ResultType::result };
};

template <int N, int L> struct __Sqrt<N, L, L> { enum { result = L }; };

template <int N> struct _Sqrt { enum { result = __Sqrt<N, 1, N>::result }; };


int main(int argc, char**argv) {
	std::cout << _Sqrt<10>::result;	// 3
	return 0;
}

编译期分支与多返回类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>

/*
运行期函数返回地址在编译时必须确定，因此会报错
auto wrap1(bool Check) {
	if (Check)return (int)0;
	else return (double)0;
}
*/

//但在编译期，可以一定程度上打破这种限制
template<bool Check, std::enable_if_t<Check>* = nullptr>
auto fun() {
	return (int)0;
}

template<bool Check, std::enable_if_t<!Check>* = nullptr>
auto fun() {
	return (double)0;
}

template<bool Check>
auto wrap2() {
	return fun<Check>();
}

int main(int argc, char**argv) {
	std::cerr << wrap2<true>() << std::endl;
	return 0;
}

这是一种典型的编译期分支和运行期函数结合的例子，C++17引入了if constexpr来简化代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>

template<bool Check>
auto fun() {
	if constexpr (Check) {
		return (int)0;
	}
	else {
		return (double)0;
	}
}

int main(int argc, char**argv) {
	std::cerr << fun<true>() << std::endl;
	return 0;
}

其中if constexpr必须接收一个常量表达式

循环执行

为了更有效地操纵元数据，往往选择递归的形式来实现循环

举个例子：给定一个无符号数，求该整数所对应的二进制表示中1的个数

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>

template<size_t Input>
constexpr size_t OnesCount = (Input % 2) + OnesCount< (Input / 2) >;

template<> constexpr size_t OnesCount<0> = 0;
//这里vs又报错了...好像和上次一样
//E2386:"constexpr"在此处无效
//E1449:必须在其首次使用之前对变量"OnesCount[其中Input=0Ui64]"进行显式专用化
//虽然报错但还是能运行...之前也是

constexpr size_t res = OnesCount<45>;

循环使用更多的一类情况则是处理数组，以下给出一个实例

1
2
3
4
5
6
7
8
template<size_t...Inputs>
constexpr size_t Accumulate = 0;

template<size_t CurInput,size_t...Inputs>
constexpr size_t Accumulate<CurInput, Inputs...>
	= CurInput + Accumulate<Inputs>;

constexpr size_t res = Accumulate<1, 2, 3, 4, 5>;

当输入数组为空时，会匹配第一个模板特化，返回0；如果有正数个参数，则匹配第二个模板特化

以下使用C++17中的折叠表达式(fold expression)简化循环

1
2
3
4
5
6
template<size_t... values>
constexpr size_t fun() {
	return (0 + ... + values);
}

const size_t res = fun<1, 2, 3, 4, 5>();

小心实例化爆炸与编译崩溃

编译时实例化的模板会被保存起来用以可能的复用，对于一般的C++程序，可以极大地提升编译速度；但是对模板元编程来说，很可能造成灾难，考虑以下代码：

计算 $\sum_{i=1}^{A+ID}i$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>

template<size_t A>
struct Wrap_ {
	template<size_t ID, typename TDummy = void>
	struct imp {
		constexpr static size_t value = ID + imp<ID - 1>::value;
	};

	template<typename TDummy>
	struct imp<0, TDummy> {	//伪参数
		constexpr static size_t value = 0;
	};

	template<size_t ID>
	constexpr static size_t value = imp<A + ID>::value;
};

int main(int argc, char**argv) {
	std::cerr << Wrap_<3>::value<2> << std::endl;
	//产生Wrap_<3>::imp的一系列实例
	std::cerr << Wrap_<10>::value<2> << std::endl;
	//产生Wrap_<10>::imp的一系列实例
	//这两个系列不同名，不能复用
	return 0;
}

循环所产生的全部实例都会在编译器中保存，如果有大量实例，很可能会内存超限甚至崩溃

解决方案：把循环拆分出来以复用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>

template<size_t ID>
struct imp {
	constexpr static size_t value = ID + imp<ID - 1>::value;
};

template<>
struct imp<0> {
	constexpr static size_t value = 0;
};

template<size_t A>
struct Wrap_ {
	template<size_t ID>
	constexpr static size_t value = imp<A + ID>::value;
};

int main(int argc, char**agrv) {
	std::cerr << Wrap_<3>::value<2> << std::endl;	// == imp<3+2>
	std::cerr << Wrap_<10>::value<2> << std::endl;	// == imp<10+2>
	//思考实例化的过程，确实是可复用的
	return 0;
}

但是也有一些不足之处：之前的代码imp被置于Wrap_中，体现二者的紧密联系，从名称污染的角度来说，这样做不会让imp污染Wrap_外围的名字空间

后一种实现中，imp将对名字空间造成污染：在相同的名字空间中，我们无法再引入一个名为imp的构造，以供其他元函数使用

权衡：如果元函数的逻辑比较简单，同时不会产生大量实例，那么保留前一种（对编译器来说比较糟糕的形式）；反之，如果元函数逻辑比较复杂（典型情况是多重循环嵌套），又可能产生很多实例，就选择后一种以节省编译资源。

当然，选择后一种方式时，我们可以引入专用的名字空间来尽力避免名称污染

分支选择与短路逻辑

计算实例：计算1~N是否全为奇数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>

template<size_t N>
constexpr bool is_odd = ((N % 2) == 1);

template<size_t N>
struct AllOdd_ {
	constexpr static bool is_cur_odd = is_odd<N>;
	constexpr static bool is_pre_odd = AllOdd_<N - 1>::value;
	constexpr static bool value = is_cur_odd && is_pre_odd;
	//突然想问，既然前面提到了顺序执行，依照递归展开的逻辑，计算is_pre_odd需要依赖value
	//而这时value还没出现...
	//我猜想可能是编译器智能地预测了展开形式，直接匹配到了AllOdd_<0>，找到了退出时的value
	//因此栈回溯时也就找到了value，大概是这样智能的结束的递归吧...
};

template<>
struct AllOdd_<0> {
	constexpr static bool value = is_odd<0>;
};

int main(int argc, char**argv) {
	std::cout << AllOdd_<10>::value;
	getchar();
	return 0;
}

但这种逻辑短路的行为在上述程序中并没有得到利用——无论is_cur_odd是什么，AllOdd_都会对is_pre_odd进行求值，改进如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>

template<size_t N>
constexpr bool is_odd = ((N % 2) == 1);


template<bool cur, typename TNext>
constexpr static bool AndValue = false;	

template<typename TNext>	//模板作为模板参数
constexpr static bool AndValue<true, TNext> = TNext::value;
//只特化了true的情况，一旦cur为false，最佳匹配是上一个模板，直接返回false，停止展开
//和std::enable_if一样是 SFINAE


template<size_t N>
struct AllOdd_ {
	constexpr static bool is_cur_odd = is_odd<N>;
	constexpr static bool value = AndValue<is_cur_odd, AllOdd_<N - 1>>;
	//上一个版本的代码，相当于在AndValue第一个参数为false时依然展开AllOdd_<N-1>
};

template<>
struct AllOdd_<0> {
	constexpr static bool value = is_odd<0>;
};


int main(int argc, char**argv) {
	std::cout << AllOdd_<10>::value;
	return 0;
}

奇特的递归模板式

奇特的递归模板式(Cruiously Recurring Template Pattern,CRTP)是一种派生类的声明方式

奇特之处在于：派生类会将其本身作为模板参数传递给其基类

1
2
3
template<typename D>class Base{ /*...*/ };
//基类以派生类的名字作为模板参数...
class Derived:public Base<Derived>{ /*...*/ };

似乎看上去有循环定义的嫌疑，但它确实是合法的…

静态多态

给出两个方面的例子

例1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;

template<typename Child>
struct Base {
	void interface() {
		static_cast<Child*>(this)->implementation();
	}
};

struct Derived :Base<Derived> {
	void implementation() {
		cerr << "Derived implementation\n";
	}
};

int main(int argc, char**argv) {
	Derived d;
	d.interface();

	return 0;
}

注意这里使用的是static_cast而不是dynamic_cast，因为只有继承了Base的类型才能调用interface，而且这里是向下转型，所以这样的行为是安全的

这样既实现了虚函数的效果，又没有虚函数调用时的开销，同时类的体积相比使用虚函数也会减少（不需要存储虚表指针），但是缺点是无法动态绑定

例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
using namespace std;

template<typename Child>
class Animal {
public:
	void Run() {
		static_cast<Child*>(this)->Run();
	}
};

class Dog :public Animal<Dog> {
public:
	void Run() {
		cout << "Dog Run" << endl;
	}
};

class Cat :public Animal<Cat> {
public:
	void Run() {
		cout << "Cat Run" << endl;
	}
};

template<typename T>
void Action(Animal<T>& animal) {
	animal.Run();
}

int main(int argc, char**argv) {
	Dog dog;
	Action(dog);

	Cat cat;
	Action(cat);

	return 0;
}

Animal中的Run是通过类型转换后调用模板类型的Run方法实现的

在Action模板函数中接收Animal类型的引用(或指针)并在其中调用了animal对象的Run方法，由于这里传入的是不同的子类对象，因此Action中的animal也会有不同的行为

添加方法，减少冗余

假设我们现在需要实现一个数学运算库，支持Vector2、Vector3等等，如果我们将每个类分别声明并实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//Vec3
struct Vector3
{
	float x;
	float y;
	float z;

	Vector3() = default;

	Vector3(float _x, float _y, float _z);

	inline Vector3& operator+=(const Vector3& rhs);
	inline Vector3& operator-=(const Vector3& rhs);
	//....
};

inline Vector3 operator+(const Vector3& lhs, const Vector3& rhs);
inline Vector3 operator-(const Vector3& lhs, const Vector3& rhs);
//....

//Vec2
struct Vector2
{
	float x;
	float y;

	Vector2() = default;

	Vector2(float _x, float _y);

	inline Vector2& operator+=(const Vector2& rhs);
	inline Vector2& operator-=(const Vector2& rhs);
	//....
};

inline Vector2 operator+(const Vector2& lhs, const Vector2& rhs);
inline Vector2 operator-(const Vector2& lhs, const Vector2& rhs);
//....

我们会发现需要为每个类型都实现+=, -= ,++ , — , + , -等运算符重载，而且每个类型的一些运算符，行为都很类似，而且可以使用其他的运算符进行实现，比如+=, -=, ++, —都可以采用+，-运算符进行实现。这时我们就可以采用CRTP抽离出这些共同的类似方法，减少代码的冗余：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
template<typename T>
struct VectorBase
{
	T& underlying() { return static_cast<T&>(*this); }
	T const& underlying() const { return static_cast<T const&>(*this); }

	inline T& operator+=(const T& rhs) 
	{ 
		this->underlying() = this->underlying() + rhs;
		return this->underlying();
	}

	inline T& operator-=(const T& rhs)
	{
		this->underlying() = this->underlying() - rhs;
		return this->underlying();
	}
	
	//.....
};

struct Vector3 : public VectorBase<Vector3>
{
	float x;
	float y;
	float z;

	Vector3() = default;

	Vector3(float _x, float _y, float _z)
	{
		x = _x;
		y = _y;
		z = _z;
	}
};

inline Vector3 operator+(const Vector3& lhs, const Vector3& rhs)
{
	Vector3 result;
	result.x = lhs.x + rhs.x;
	result.y = lhs.y + rhs.y;
	result.z = lhs.z + rhs.z;
	return result;
}

inline Vector3 operator-(const Vector3& lhs, const Vector3& rhs)
{
	Vector3 result;
	result.x = lhs.x - rhs.x;
	result.y = lhs.y - rhs.y;
	result.z = lhs.z - rhs.z;
	return result;
}
//......

int main()
{
	Vector3 v0(6.0f, 5.0f, 4.0f);
	Vector3 v2(4.0f, 5.0f, 6.0f);

	v0 += v2;
	v0 -= v2;

	return 0;
}

通过把+=， -=等操作放到基类中并采用+ ,-运算符实现，这样一来所有继承自VectorBase的类，只要其定义了+，-运算符就可以自动获得+=, -=等运算符，减少了代码中的冗余。

在有多个类型存在相同方法，且这些方法可以借助于类的其他方法进行实现时，均可以采用CRTP进行精简代码。

模板中的变长参数

可变模板参数函数

基本形式

1
2
3
4
template<typename... Args>	//模板参数包，包含函数调用中的参数匹配的类型，比如char*,int
void show(Args... args) {	//args函数参数包，指出args的类型为Args
	//函数调用时，根据args反推Args类型（auto）
}

获取参数包信息

计算参数个数

一个实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>

using namespace std;

template<class... T>
void f(T... args) {
	cout << sizeof...(args) << endl;	//打印变参的个数
}

int main(int argc, char**argv) {
	f();				// 0
	f(1, 2);			// 2
	f(1, 2.4, "hello");	 // 3

	return 0;
}

获得每个参数

递归

递归方法需要一个终止函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>

using namespace std;

//递归终止函数
void print() {
	cout << "empty" << endl;
}

//展开函数
template<class T,class... Args>
void print(T head, Args... rest) {
	cout << "parameter " << head << endl;
	print(rest...);
}

int main(int argc, char**argv) {
	print(1, 2, 3, 4);
	// parameter 1
	// parameter 2
	// parameter 3
	// parameter 4
	// empty

	return 0;
}

求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>

using namespace std;

template<typename T>
T sum(T t) {
	return t;
}

template<typename T,typename... Types>
T sum(T first, Types... rest) {
	return first + sum<T>(rest...);
}

int main(int argc, char**argv) {
	cout << sum(1, 2, 3, 4, 5)<<endl;	// 15
	return 0;
}
逗号表达式

实例如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>

using namespace std;

template<class T>
void printarg(T t) {
	cout << t << "\t";
}

template<class... Args>
void expand(Args... args) {
	int arr[] = { (printarg(args),0)... };
}

int main(int argc, char**argv) {
	expand("hello",123, 'x');
	// hello   123     x
	return 0;
}

C/C++中的表达式会按顺序执行，同时这里用到了C++11的特性——初始化列表

(printarg(args),0)会先执行函数，再得到逗号表达式的结果0

通过初始化列表来初始化一个变长数组

{(printarg(args),0)...}将会展开成((printarg(arg1),0),(printarg(arg2),0),etc...)

最终会创建一个元素值都为0的数组int arr[sizeof…(Args)]

这里只用于展开参数包，我们可以将函数作为参数，就可以支持lambda表达式了

可变模板参数类

比较基本的就是这个tuple了…

1
2
3
std::tuple<int> tp1 = std::make_tuple(1);
std::tuple<int, double> tp2 = std::make_tuple(1, 2.5);
std::tuple<int, double, string> tp3 = std::make_tuple(1, 2.5, "");

由于可变参数模板的模板参数个数（绕口令?…）可以为0，所以以下定义也是合法的

std::tuple<> tp;

展开参数包的方法

模板偏特化和递归

（感觉和刚刚的求和没什么区别，换些实例）

实例1：IntegerMax
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <type_traits>

using namespace std;

//获取最大的整数
template<size_t arg, size_t... rest>
struct IntegerMax;

template<size_t arg>
struct IntegerMax<arg> :std::integral_constant<size_t, arg> {};

template<size_t arg1, size_t arg2, size_t... rest>
struct IntegerMax<arg1, arg2, rest...> :	//继承之后这个类也有value了...
	std::integral_constant<size_t, arg1 >= arg2 ?
	IntegerMax<arg1, rest...>::value :
	IntegerMax<arg2, rest...>::value > {
};

int main(int argc,char**argv) {
	cout << IntegerMax<2, 5, 1, 7, 3>::value << endl;	// 7
	return 0;
}

这段代码看起来比较复杂……实际上是一个继承，integral_constant<size_t,num>应该就是size_t num

实例2：MaxAlign

上一段代码改一下可以轻松实现获取最大内存对齐值的元函数MaxAlign

增加以下部分

1
2
3
4
5
6
7
8
9
template<typename... Args>
struct MaxAlign : std::integral_constant<int,
	IntegerMax<std::alignment_of<Args>::value...>::value > {};


int main() {
	cout << MaxAlign<int, short, double, char>::value << endl;	//  => 8
	return 0;
}
实例3：TypeSizeSum

我自己写的也不太熟练，还是再来一个求和吧，计算参数包中参数类型的size之和

突然想用LaTeX写Σ了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <type_traits>

using namespace std;

//前向声明
template<typename... Args>
struct Sum;

//基本定义
template<typename First, typename... Rest>
struct Sum<First, Rest...>{
	enum { value = Sum<First>::value + Sum<Rest...>::value };
};

//递归终止
template<typename Last>
struct Sum<Last>{
	enum { value = sizeof(Last) };
};


int main(int argc,char**argv) {
	cout<<Sum<int, double, short>::value;	//值为14
	return 0;
}

继承方式

MakeIndexes的作用是生成一个可变参数模板类的整数序列，最终输出的类型是：struct IndexSeq<0,1,2>

（看懂代码已属不易，这个类型的实际使用我还没有考虑）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <type_traits>

using namespace std;

//整形序列的定义
template<int...>
struct IndexSeq{};

//继承方式展开参数包
template<int N,int... Indexes>
struct MakeIndexes:MakeIndexes<N-1,N-1,Indexes...>{};

//说明（往前展开）
//MakeIndexes<3>: MakeIndexes<2, 2>{}
//MakeIndexes<2, 2>: MakeIndexes<1, 1, 2>{}
//MakeIndexes<1, 1, 2>: MakeIndexes<0, 0, 1, 2>
//{
//	typedef IndexSeq<0, 1, 2> type;
//}

//模板特化，终止展开参数包条件
template<int... Indexes>
struct MakeIndexes<0, Indexes...> {
	typedef IndexSeq<Indexes...> type;
};
//这里去掉了多出来的一个0


int main(int argc,char**argv) {
	using T = MakeIndexes<3>::type;
	cout << typeid(T).name() << endl;
	// struct IndexSeq<0,1,2>
	return 0;
}

发表于 | 阅读次数:

基本的就不说了，CTF逆向中常见的是CRC16和CRC32

CRC-16

生成多项式: $x^{16}+x^{12}+x^{5}+1$

二进制串: 1 0001 0000 0010 0001
故HEX为 0x1 1021

计算实例

计算字符’a’的CRC16校验码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<windows.h>
//以CRC16  0x1021  为例

int main(int argc, char**argv) {
	unsigned short crc = 'a';	//计算字符a的crc16校验码
	//左移8位，和手动计算一样，相当于右边直接补了8个0
	crc <<= 8;

	//计算8次，在右边添加的 8个0 经过循环后即是结果
	for (int i = 0; i < 8; i++) {	
		//如果最高位是1的话需要计算， 如果不是直接左移(左移可以想象成补0)
         //参考手算的图示，crc左移相当于取余数进行计算
		if ((crc & 0x8000) != 0) {
			crc <<= 1;
			crc = crc ^ 0x1021;
		}
		else {
			crc <<= 1;
		}
	}
	printf("%#x", (BYTE)crc);	// 0x87
	system("pause");
	return 0;
}

这里计算字符a的CRC16校验码，仅仅给出了代码，其中细节可以参见下文以CRC-8举例的一些说明

CRC-32

生成多项式:

二进制串:1 0000 0100 1100 0001 0001 1101 1011 0111
故HEX为 0x1 04C11DB7

（另一个CRC为1 1110 1101 1011 1000 1000 0011 0010 0000 = 0x1 EDB8 8320）

一些概念

注意到，上文计算实例中，如果一开始在数据前加了一些0，对结果没有影响，因此算法有缺陷。

于是真正的应用的CRC算法都做了一些改动，增加2个概念：余数初始值、结果异或值

余数初始值，在计算CRC值的开始，给CRC寄存器一个初始值…

结果异或值，其余计算完成后将CRC寄存器的值在与这个值进行异或作为最后的校验值

CRC16: 余数初始值 0x0000 结果异或值 0x0000 （上文程序中两处0x0000没有体现）

CRC32: 余数初始值0xFFFFFFFF 结果异或值 0xFFFFFFFF

CRC-8

生成多项式有很多，这里选一种: $x^8+x^7+x^6+x^4+x^2+1$

二进制串: 1 1101 0101

故HEX为 0x1 0xD5

CRC直接移位算法(以CRC-8为例)

改进1

回想迭代过程，当余数首位为0时，会直接再左移一位，直到首位为1，图中$g_k$表示余数

也可以表示为，每次迭代，根据余数的首位决定与之运算的二进制码的值，记作b

若首位为1，b为hex(1021)；若首位为0，b为0

图片

改进2

每次迭代，$g_k$的首位将会被移除（根据首位决定b的值），因为生成多项式对应二进制串的首位是1，因此只需考虑第2位后计算即可，这样就可以舍弃h的首位。比如CRC-8的h是111010101，b只需是11010101

图片

改进3

每次迭代，受到影响的是$g_k$的前m位(CRC-m)，所以构建一个m位的寄存器，此寄存器储存$g_k$的前m位。

每次迭代计算时先将S的首位抛弃，再将寄存器左移一位，同时将数据流g的下一位加入寄存器。

至于为什么要先给出代码，再给出算法分析…是因为我是写了代码才理解这个过程的

直接查表法

举个例子，将24位的数据组成1个block，这样g就被分成6个block

图片

经过4次迭代，B1被移出了寄存器，这里我们只关心4次迭代对B2和B3产生了什么影响

注意表中红色部分，先给出一个定义：

1
2
3
4
5
6
B23 = 0011 1010
b1  = 0000 0000
b2  = 0101 0100
b3  = 1010 1010
b4  = 1101 0101
b'  = b1 xor b2 xor b3 xor b4

4次迭代对B23来说，实际是与b1,b2,b3,b4进行了异或运算

即 B23 = B23 xor b1 xor b2 xor b3 xor b4 ，亦即 B23 = B23 xor b'

根据XOR性质，因此CRC运算满足结合律和交换律

解释

关于上面那张带红色的图，我TM看了半天才看懂是什么意思

图中模拟了4次迭代的过程，每次右移一位，S’相较S被划去了首位。b的值始终是前八位（和红色没关系），并且取值只有2种：00000000和11010101，$b_1,b_2,b_3,b_4$才是红色的那块。

如果B1的第一位为1，那么b为11010101000(11位)，则$b_1$ (红)为b的后8位也就是10101000；若B1第一位为0则b1为00000000，也就是说，b1由B1的第一位决定。

同理，$b_2$到$b_4$也是由B1的剩下三位决定的，注意第k+1层的S是由第k层的S’和b生成的，也就是说，根据B1四位决定的$b_1$到$b_4$，S初值中的B23 = B23 xor b1 xor b2 xor b3 xor b4。既然$b_1$到$b_4$是由B1的16种情况可以确定下来的，那么根据B1就可以求出b’，其中b' = b1 xor b2 xor b3 xor b4，于是可以建表，省去这四次迭代过程而直接使B23 xor b了。

到这里我才理解了各种博客出现的这句话….

b2是由B1迭代1次后的第2位决定（既是由B1的第1和第2位决定），同理,b3和b4都是由B1决定

TMD直接说 b2由B1的第二位决定不就好了嘛…

CRC-32 直接查表法代码实现

CRC-8中，B1 B2 B3都是4bits，这表明B2+B3的8bits最终需要异或的值由B1的4bits决定；

推广到CRC-32，B1 B2 B3都应该是16bits，表明B2+B3的32bits最终需要异或的值由B1的16bits决定。

CRC-8的table中有$2^4$个数据，那么CRC-32的table中有$2^8=256$个数据。

这也是CRC-32中一次性处理4字节数据的原因（CRC-8一次处理8个bits也就是1字节）

还有很多没搞清楚的地方，想弄清楚整个发展历程实在是太困难了

暂时弃坑

发表于 | 阅读次数:

基本语法

安装好后进入z3目录下，source ~/z3/bin/activate

照着官网教程学习下

1
2
3
4
5
from z3 import *
p = Bool('p')
q = Bool('q')
r = Bool('r')
solve(Implies(p,q),r==Not(q),And(Not(p),r))

结果[q = False, p = False, r = True]

这里Implies是离散数学中的蕴含式，只有(1,0)->0

1
2
3
4
5
6
from z3 import *
x = Int('x')
y = Int('y')
print simplify(x + y + 2*x + 3)
print simplify(x < y + x + 2)
print simplify(And(x + 1 >= 3,x**2 + x**2 + y**2 + 2 >= 5))

simplify函数简化表达式（我猜可能类似于编译优化中的策略？）

1
2
3
3 + 3*x + y
Not(y <= -2)
And(x >= 2, 2*x**2 + y**2 >= 3)

多项式与布尔代数的结合

1
2
3
4
from z3 import *
p = Bool('p')
x = Real('x')
solve(Or(x < 5,x > 10),Or(p, x**2 == 2),Not(p))

结果[x = -1.4142135623?, p = False]

1
2
3
4
5
6
from z3 import *

x = Real('x')
s = Solver()
s.add(2**x==3)
print s.check() # unknown

这样是错误的，因为这不是线性约束条件

显示z3内部表示形式

1
2
3
4
5
from z3 import *
x,y = Ints('x y')
print (Sqrt(2) + Sqrt(3))
print simplify(Sqrt(2)+Sqrt(3))
print simplify(Sqrt(2)+Sqrt(3)).sexpr()

输出结果

1
2
3
2**(1/2) + 3**(1/2)
3.1462643699?
(root-obj (+ (^ x 4) (* (- 10) (^ x 2)) 1) 4)

遍历模型

遍历约束条件

1
2
3
4
5
6
7
8
9
from z3 import *
x = Int('x')
y = Int('y')
s = Solver()
s.add(x>1,y>1,Or(x+y>3,x-y<2))

print "assertions:"
for c in s.assertions():
	print c

可用于debug，输出如下

1
2
3
4
assertions:
x > 1
y > 1
Or(x + y > 3, x - y < 2)

解决方案是一组断言约束的模型(model)

模型是使每个断言约束成立的解释

此方法显示了如何遍历所有模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from z3 import *
x = Real('x')
y = Real('y')
z = Real('z')

s = Solver()
s.add(x>1,y>1,x+y>3,z-x<10)
print s.check()

m = s.model()
print "x = %s" % m[x]
#The  expression  m[x]  returns  the  interpretation  of x in the model m

print "trasversing model"
for d in m.decls():
	print "%s = %s" % (d.name(),m[d])

输出结果：

1
2
3
4
5
6
sat
x = 3/2
trasversing model
z = 0
y = 2
x = 3/2

函数

关于函数，z3中的函数没有副作用并且是完全的(total)

1
2
3
4
5
6
7
8
9
10
11
12
13
from z3 import *

x = Int('x')
y = Int('y')

f = Function('f',IntSort(),IntSort())
s = Solver()
s.add( f( f(x) )==x, f(x)==y, x!=y)

print s.check()
m = s.model()
print "f(f(x)) = " , m.evaluate(f(f(x)))
print "f(x) = " , m.evaluate(f(x))

其中f是一个未解释的函数（之前已经提到过解释），接收一个类型（又称排序）为整数的参数并产生一个整数值

The solution(interpretation) for f should be read as f(0) is 1,f(1) is 0,and f(a) is 1 for all a different from 0 and 1.

验证摩根定律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from z3 import *

p,q = Bools('p q')
demorgan = And(p,q) == Not(Or(Not(p),Not(q)))
print demorgan

def prove(f):
	s = Solver()
	s.add(Not(f))
	if s.check()==unsat: #unsatisfied
		print "proved"
	else:
		print "failed to prove"

print "Proving demorgan"
prove(demorgan)

输出结果

1
2
3
And(p, q) == Not(Or(Not(p), Not(q)))
Proving demorgan
proved

以后大概很少尝试证明一些数学内容了，突然想起一句关于黎曼猜想的评论

无论对黎曼猜想的证明是否成立，仍然对Atiyah爵士一生挚爱数学致以敬意

列表推导

python支持列表推导，演示创建列表的简明方法

1
2
3
4
5
6
7
8
9
10
11
12
13
from z3 import *

print [x+1 for x in range(5)]

X = [Int('x%s'%i) for i in range(5)]
Y = [Int('y%s'%i) for i in range(5)]
print X

X_plus_Y = [ X[i]+Y[i] for i in range(5)]
print X_plus_Y

X_gt_Y = [X[i]>Y[i] for i in range(5)]
print And(X_gt_Y)

输出结果

1
2
3
4
[1, 2, 3, 4, 5]
[x0, x1, x2, x3, x4]
[x0 + y0, x1 + y1, x2 + y2, x3 + y3, x4 + y4]
And(x0 > y0, x1 > y1, x2 > y2, x3 > y3, x4 > y4)

创建3*3矩阵，两层循环

1
2
3
4
5
6
from z3 import *

x = [[ Int("x_%s_%s" % (i+1,j+1)) for j in range(3)]
	for i in range(3)]

pp(x)

其中pp()类似print，但它使用Z3Py格式化程序来表示列表和元组

输出结果

1
2
3
[[x_1_1, x_1_2, x_1_3],
 [x_2_1, x_2_2, x_2_3],
 [x_3_1, x_3_2, x_3_3]]

Z3Py还提供了创建Boolean，Integer和Real变量向量的函数，同样使用列表推导来实现

1
2
3
4
5
6
7
8
9
10
11
from z3 import *

X = IntVector('x',5)
Y = RealVector('y',5)
P = BoolVector('p',5)
print X
print Y
print P

print [y**2 for y in Y]
print Sum([y**2 for y in Y])

输出结果

1
2
3
4
5
[x__0, x__1, x__2, x__3, x__4]
[y__0, y__1, y__2, y__3, y__4]
[p__0, p__1, p__2, p__3, p__4]
[y__0**2, y__1**2, y__2**2, y__3**2, y__4**2]
y__0**2 + y__1**2 + y__2**2 + y__3**2 + y__4**2

BitVec

CTF中用的比较多的应该就是这种BitVec

1
2
3
4
5
6
7
8
9
from z3 import *

a = BitVecVal(-1,16)
b = BitVecVal(65535,16)
print simplify(a==b) # True

a = BitVecVal(-1,32)
b = BitVecVal(65535,32)
print simplify(a==b) # False

ULT是无符号数的比较之一，其余见文档

1
2
3
4
5
6
from z3 import *

x,y = BitVecs('x y',32)
solve(x+y==2,x>0,y>0)
solve(x&y == ~y)
solve(ULT(x,0)) # ULT: unsigned less than

输出结果

1
2
3
[y = 1, x = 1]
[y = 4294967295, x = 0]
no solution

逻辑移位>>最左都补0，算术移位最左补符号位，这里都是算术移位

1
2
3
4
5
6
from z3 import *

x,y = BitVecs('x y',32)
solve(x>>2==3)
solve(x<<2==3)
solve(x<<2==24)

输出结果

1
2
3
[x = 12]
no solution
[x = 6]

CTF&实例

1、解数独

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#coding:utf-8
from z3 import *

X = [ [ Int("x_%s_%s" %(i+1,j+1)) for j in range(9)]
	for i in range(9)]

#each cell contains a value in {1...9}
cells_c = [ And(1<=X[i][j],X[i][j]<=9)
	for i in range(9) for j in range(9)]

#each row
rows_c = [Distinct(X[i]) for i in range(9)]

#each column
cols_c = [Distinct(X[i][j]) for i in range(9)
	for j in range(9)]

#each 3*3 square
sq_c =[ 
	Distinct(
	    [ X[3*i0 + i][3*j0 + j]
            for i in range(3) for j in range(3) ]
            )
    	for i0 in range(3) for j0 in range(3) 
      ]

sudoku_c = cells_c + rows_c + cols_c + sq_c

# sudoku instance, we use '0' for empty cells
instance = ((0,0,0,0,9,4,0,3,0),
            (0,0,0,5,1,0,0,0,7),
            (0,8,9,0,0,0,0,4,0),
            (0,0,0,0,0,0,2,0,8),
            (0,6,0,2,0,1,0,5,0),
            (1,0,2,0,0,0,0,0,0),
            (0,7,0,0,0,0,5,2,0),
            (9,0,0,0,6,5,0,0,0),
            (0,4,0,9,7,0,0,0,0))

#这里的If没怎么看懂，应该是必须满足instance中不等于0的数必须等于X中对应的，And手输?.....
instance_c = [ If(instance[i][j] == 0,
                  True,
                  X[i][j] == instance[i][j])
               for i in range(9) for j in range(9) ]

s = Solver()
s.add(sudoku_c + instance_c)
if s.check() == sat:
    m = s.model()
    r = [ [ m.evaluate(X[i][j]) for j in range(9) ]
          for i in range(9) ]
    print_matrix(r)
else:
	print "failed to solve"

输出结果

1
2
3
4
5
6
7
8
9
[[5, 7, 2, 6, 9, 4, 1, 3, 8],
 [6, 4, 3, 5, 1, 8, 9, 2, 7],
 [1, 8, 9, 7, 3, 2, 5, 4, 6],
 [4, 7, 9, 3, 5, 6, 2, 1, 8],
 [8, 6, 3, 2, 7, 1, 4, 5, 9],
 [1, 5, 2, 8, 9, 4, 3, 6, 7],
 [6, 7, 3, 1, 8, 4, 5, 2, 9],
 [9, 8, 2, 3, 6, 5, 4, 7, 1],
 [1, 4, 5, 9, 7, 2, 6, 3, 8]]

2、CTF-1

HITB CTF 2016 soup meat tead

题目只给了源代码，稍作改动，如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// Soup Meat Tea (SMT) (TM)
//
// We welcome you to our delicious kitchen featuring many dishes from all
// around the world. With so many choices we really don't know the perfect
// combination. Fortunately our previous chef left the best set of dishes for
// a table of 8 people. Can you reconstruct the set of dishes?
//
// The service provided by our last chef can be found at.. find the ip/port
// as if it's a stego001 challenge :-)
//
// Compile with:    gcc -std=c99 soup_meat_tea.c -o soup_meat_tea
// Test with:       echo -n $'... payload ...'|./soup_meat_tea

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <unistd.h>

uint32_t state = 42;

typedef enum {
    D_SOUP_CHICKEN,
    D_SOUP_MEAT,
    D_SOUP_NAZI,
    D_CHICKEN_RAW,
    D_CHICKEN_BLACK,
    D_MEAT_BLACKANGUS,
    D_MEAT_WAGYU,
    D_MEAT_HORSE,
    D_TIRAMISU,
    D_ICE_BANANA,
    D_ICE_STRAWBERRY,
    D_OVERFLOW,
} dish_t;

const char *dishes[] = {
    "soup-chicken", "soup-meat", "soup-nazi", "chicken-raw", "chicken-black",
    "meat-blackangus", "meat-wagyu", "meat-horse", "tiramisu", "ice-banana",
    "ice-strawberry",
};

void dish(uint8_t d)
{
    state = ((state + d) * 3294782) ^ 3159238819;
}

int main()
{
    uint8_t input[32];
    read(0, input, 32);

    for (uint32_t idx = 0; idx < 32; idx++) {
        dish(input[idx]);
    }

    printf("That's some delicious.. ");
    for (uint32_t idx = 0; idx < 32; idx++) {
        if(input[idx] < D_OVERFLOW) {
            printf("%s ", dishes[input[idx]]);
        }
        else {
            printf("%s ", "<YUEATTHIS>");
        }
    }

    if(state == 0xde11c105) {
        system("/bin/cat flag.txt");
    }
    return 0;
}

里面有很多废话，就是输入32个unsigned char，经过一堆运算后让state==0xde11c105

先给出z3的exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from z3 import *
state = 42

def dish(d):
	global state
	state = ((state + d) * 3294782) ^ 3159238819

input = [BitVec('input_%d'%i,32) for i in range(32)]

for idx in range(32):
	dish(input[idx])


s = Solver()

for i in range(32):
	s.add(input[i]>=0,input[i]<=0xff)

s.add(state==0xde11c105)

if s.check()==sat:
	m = s.model()
	print m
	print repr("".join([chr(m[input[i]].as_long()) for i in range(32)]))

有一些疑问和要注意的

  1. dish函数里的global，捕获外界全局变量

  2. 因为代码中是unsigned char，我们为求简便，用BitVec表示，接着把每一个BitVec32的范围都限定在[0,255]，显然这里只用BitVec8可能是不好用的…python的类型我不熟悉，感觉挺迷的

    这里如何体现正负啊？？？算了就这么用吧

  3. C代码里由于没有体现类型…….所以直接就转成python函数了，如果有了强转，或者类型不能自动提升该如何是好？？

好吧我决定多做几个题看看wp再说

最后的结果是这样的

1

就是输入给远程程序的数据

题目中是unsigned char，根据上次南大校赛的一个错题，发现gdb调试时会出现无法解决的错误，程序读入char，pwntools一旦发出超过\x7f就会提升类型，不过这好像不是同一个问题

于是…试试echo -e | ./xxx

输出结果

2

3、CTF-3

3

z3脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from z3 import *
inp = [BitVec('a%d' %i, 56) for i in range(3)]
sol_1 = inp[0] - inp[1] + inp[2]
sol_2 = inp[1] +3 *(inp[2]+inp[0])
sol_3 = inp[2]*inp[1]

s = Solver()
s.add(sol_1==1550207830)
s.add(sol_2==12465522610)
s.add(sol_3==3651346623716053780)
print s.check()
m = s.model()
r = []
for i in inp:
    print m[i]

输出结果：

4