编程

expression template and CRTP

表达式模板和静态多态

表达式模板（expression template）是一种模板元编程技术，在编译期间延迟计算的求值，并构造表达计算的结构（expression tree）。利用expression tree的变换，可以实现运行前的自动循环融合（loop fusion）等功能。

静态多态（也叫CRTP）用一个模板基类来在编译期完成多态的实际实现的分发(与运行时使用virtual override的多态机制相对, 因此叫静态多态)，不同类型的子类将自身类型作为基类的模板参数来继承，以此通知基类将对应类型的调用分发给自己。静态多态消除了动态多态的开销，可以提升运行时性能，经常和表达式模板一起使用。

静态多态demo

下面以一个简单demo展示上述静态多态的原理和用法：

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
#include <iostream>
#include <vector>

template <class T>
struct Animal {
  void Say() {
    static_cast<T*>(this)->Say_();
  }
};

struct Dog : Animal<Dog> {
  void Say_() {
    std::cout << "wang wang wang!" << std::endl;
  }
};

struct Cat : Animal<Cat> {
  void Say_() {
    std::cout << "meow meow meow~" << std::endl;
  }
};

class Zoo {
 public:
  template <class T>
  void AddAnimal(Animal<T> animal) {
    animal.Say();
  }
};

int main() {
  Dog dog{};
  Cat cat{};
  Zoo zoo{};
  zoo.AddAnimal(dog);
  zoo.AddAnimal(cat);
  return 0;
}

表达式模板demo

wiki上给出了一个表达式模板很好的例子，对vector加法进行循环融合。原理大致如下：

  1. 将+法操作符封装为表达式求和类型VecSum的构造函数，因此在+法时不进行实际的求值，而是进行表达式树的构建
  2. 在对Vec进行赋值操作时进行表达式求值，此时对VecSum表达式中的[]操作符递归调用，直到完成实际的求和。

代码如下：

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
#include <iostream>
#include <vector>
#include <assert.h>

template <typename E>
class VecExpression {
  public:
    double operator[](size_t i) const {
      return static_cast<E const&>(*this)[i];
    }
    size_t size() const {return static_cast<E const&>(*this).size();}
};

class Vec : public VecExpression<Vec> {
  std::vector<double> elems;

 public:
  double operator[](size_t i) const { return elems[i];}
  double &operator[](size_t i) { return elems[i]; }
  size_t size() const { return elems.size();}

  Vec(size_t n) : elems(n) {}
  Vec(std::initializer_list<double> init) : elems(init) {};

  // 从VecExpression构建Vec, 此时对表达式求值
  template <typename E>
  Vec(VecExpression<E> const& expr) : elems(expr.size()) {
    for (size_t i = 0; i != expr.size(); i++) {
      elems[i] = expr[i];
    }
  }  

  void dump() {
    for (auto &elem : elems) {
      std::cout << elem << " ";
    }
    std::cout << std::endl;
  }
};

// 静态多态
template <typename E1, typename E2>
class VecSum : public VecExpression<VecSum<E1, E2>> {
  E1 const& _u;
  E2 const& _v;

 public:
  VecSum(E1 const &u, E2 const &v) : _u(u), _v(v) {
    assert(u.size() == v.size());
  }
 // Vec的构造函数中被调用，此时求值
  double operator[](size_t i) const { return _u[i] + _v[i]; }
  size_t size() const { return _v.size(); }
};

// 将VecSum的构造函数封装成+运算符
template <typename E1, typename E2>
VecSum<E1, E2> operator+(VecExpression<E1> const &u, VecExpression<E2> const &v) {
  std::cout << __PRETTY_FUNCTION__ << std::endl;
  return VecSum<E1, E2>(*static_cast<const E1*>(&u), *static_cast<const E2*>(&v));
}

int main() {
  Vec v0 = {1, 1, 1};
  Vec v1 = {2, 2, 2};
  Vec v2 = {3, 3, 3};
  Vec v3 = {4, 5, 6};

  Vec sum = v0 + v1 + v2 + v3;
  sum.dump();
  return 0;
}

输出如下：

1
2
3
4
VecSum<E1, E2> operator+(const VecExpression<E>&, const VecExpression<E2>&) [with E1 = Vec; E2 = Vec]
VecSum<E1, E2> operator+(const VecExpression<E>&, const VecExpression<E2>&) [with E1 = VecSum<Vec, Vec>; E2 = Vec]
VecSum<E1, E2> operator+(const VecExpression<E>&, const VecExpression<E2>&) [with E1 = VecSum<VecSum<Vec, Vec>, Vec>; E2 = Vec]
10 11 12
编程

cpp variadic template

C++变长模板使用

C++11开始支持支持变长模板（variadic template），模板参数可以为任意多个, 变长模板参数用省略号来标识(…)。

变长模板参数通常以递归的形式打开（因此需要定义一个没有变长参数的base case模板），下面借用一个例子来说明:

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

template <typename Arg>
void Foo(Arg arg) {
  std::cout << __PRETTY_FUNCTION__ << "\n";
}

template <typename First, typename... Args>
void Foo(First first, Args... args) {
  std::cout << __PRETTY_FUNCTION__ << "\n";
  Foo(first);
  Foo(args...);
}

int main() {
  std::string one = "one";
  const char* two = "two";
  Foo(one);
  std::cout << std::endl;
  Foo(one, two);
  return 0;
}

上面代码的输出如下：

1
2
3
4
5
void Foo(Arg) [with Arg = std::__cxx11::basic_string<char>]

void Foo(First, Args ...) [with First = std::__cxx11::basic_string<char>; Args = {const char*}]
void Foo(Arg) [with Arg = std::__cxx11::basic_string<char>]
void Foo(Arg) [with Arg = const char*]

求和

下面尝试使用变长模板来实现一个求和的函数。

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

template <typename Arg>
Arg Sum(Arg arg) {
  std::cout << __PRETTY_FUNCTION__ << "\n";
  return arg;
}

template <typename First, typename... Args>
First Sum(First first, Args... args) {
  std::cout << __PRETTY_FUNCTION__ << "\n";
  return first + Sum(args...);
}

int main() {
  std::cout << Sum(1, 2, 3, 4, 5) << std::endl;
  return 0;
}

得到的结果如下：

1
2
3
4
5
6
First Sum(First, Args ...) [with First = int; Args = {int, int, int, int}]
First Sum(First, Args ...) [with First = int; Args = {int, int, int}]
First Sum(First, Args ...) [with First = int; Args = {int, int}]
First Sum(First, Args ...) [with First = int; Args = {int}]
Arg Sum(Arg) [with Arg = int]
15

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Mermaid

installation:

1
npm install hexo-mermaid-diagrams

usage:

1
2
{% mermaid type %}
{% endmermaid %}

e.g.

1
2
3
4
5
6
7
{% mermaid %}
graph TD;
    A-->B;
    A-->C;
    B-->D;
    C-->D;
{% endmermaid %}
A
B
C
D

Math

默认render会把latex公式中的_渲染成HTML中的<i>, 需要更换render。

1
2
3
4
5
6
npm install hexo-math --save
cd PATH_TO_YOUR_HEXO_BLOG
hexo math install
# NOW, add plugins: hexo-math into the _config.yml
npm uninstall hexo-renderer-marked --save
npm install hexo-renderer-kramed --save

注意， kramed的inline公式需要改变写法，增加单行代码引用包围， 例如：

1
`$a_t$`
/!-- -->