More than code

More Than Code
The efficiency of your iteration of reading, practicing and thinking decides your understanding of the world.
  1. 首页
  2. daily
  3. 正文

Daily C/C++ 编译期计算

2021年9月2日 618点热度 0人点赞 0条评论

Daily C/C++ 编译期计算

今天这篇文章是有关模板元编程,也相当与是学习吴咏炜老师的课的一个笔记,参考文章在这里链接

首先就是一个结论,C++模板是图灵完全的,也就是说通过C++的模板,你可以在编译期间模拟一个完整的图灵机

先上一段代码

template <int n>
struct factorial {
  static const int value =
    n * factorial<n - 1>::value;
};

template <>
struct factorial<0> {
  static const int value = 1;
};

这是一个递归的阶乘函数,要注意的是我们要先定义这个递归,然后再特化出0的情况

通过反汇编编译生成的代码,我们可以发现通过value得到的值是一个常数

如果你传入了一个负数的n,那么gcc就可能会报错

fatal error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum)

可以看到是深度溢出了,平常使用如果得到这样的情况,我们可以用对应的指令来增加这个最值,当然这里我们是通过static_assert来保证不是符号即可。就有点像运行时的assert了有没有

编译期的计算,最主要的就是要把计算变成类型推导,再看下面的代码

template <bool cond,
          typename Then,
          typename Else>
struct If;

template <typename Then,
          typename Else>
struct If<true, Then, Else> {
  typedef Then type;
};

template <typename Then,
          typename Else>
struct If<false, Then, Else> {
  typedef Else type;
};

可以看到这里我们是定义了判断语句,当cond为true时,我们定义type为then,否则定义type为else

所以这样我们可以通过If<cond, Then, Else>::type来得到结果

再看循环

template <bool condition,
          typename Body>
struct WhileLoop;

template <typename Body>
struct WhileLoop<true, Body> {
  typedef typename WhileLoop<
    Body::next_type::cond_value,
    typename Body::next_type>::type
    type;
};

template <typename Body>
struct WhileLoop<false, Body> {
  typedef
    typename Body::res_type type;
};

template <typename Body>
struct While {
  typedef typename WhileLoop<
    Body::cond_value, Body>::type
    type;
};

这里的代码相对于原本文章做了一点小修正

这个写法就很有函数式编程那个感觉,我们定义了一个模板参数为bool和Body的循环

其中Body需要有三个静态成员,分别是res_type, next_type和cond_value,代表了循环结束时的值,下一个状态以及循环条件

那么为了计算,我们还需要代表数值的类型

template <class T, T v>
struct integral_constant {
  static const T value = v;
  typedef T value_type;
  typedef integral_constant type;
};

两个模板参数分别是类型以及对应类型的值,同时我们也可以通过value_type和type来访问这两个属性

然后我们再定义一个循环体用来传给while

template <int result, int n>
struct SumLoop {
  static const bool cond_value =
    n != 0;
  static const int res_value =
    result;
  typedef integral_constant<
    int, res_value>
    res_type;
  typedef SumLoop<result + n, n - 1>
    next_type;
};

template <int n>
struct Sum {
  typedef SumLoop<0, n> type;
};

可以看到,SumLoop就是循环体,当0不为0的时候,循环条件就是真,而结束状态则是通过模板的result得到的一个数值类型res_type,而下一个状态则是同样的循环体,我们累加result并递减n,这样可以让我们达到累加的目的

那么Sum就可以得到1到n的累加和,而这些都是在编译期通过模板参数的推导就可以得到的,是不是很神奇。

C++标准库有一个头文件是type_traits,即类型特点,是用来帮助我们提取某个类型的特点

再举个例子

typedef std::integral_constant<
  bool, true> true_type;
typedef std::integral_constant<
  bool, false> false_type;

template <typename T>
class SomeContainer {
public:
  …
  static void destroy(T* ptr)
  {
    _destroy(ptr,
      is_trivially_destructible<
        T>());
  }

private:
  static void _destroy(T* ptr,
                       true_type)
  {}
  static void _destroy(T* ptr,
                       false_type)
  {
    ptr->~T();
  }
};

我们定义true_type和false_type,然后在destroy中我们判断,如果这个析构函数是可以平凡析够的,我们就不需要单独处理他,否则就需要显式的调用这个类型的析构函数

这样在优化编译的情况下,编译器就会帮助我们把不需要的析构操作全部删除,这样比我们运行时再去判断是否可以平凡析构更有效率

然后提一下C++中的using,除去使用命名空间和成员函数等操作,using其实和typedef类似,可以声明别名

typedef A B
using B = A

这两个是一样的,但是using的好处在于他可以对模板声明别名

template<typename T>
using Vec = MyVector<T, MyAlloc<T>>

Vec<int> vec    // MyVector<int, MyAlloc<int>>

这样想是不是vector也有这个用法,毕竟我们平常用的时候都是vector<int>

但是也有可能是默认参数,比如vector<T, allocator<T>> = ...>

最后再给出一个函数式编程中的map实现方法

template <
  template <typename, typename>
  class OutContainer = vector,
  typename F, class R>
auto fmap(F&& f, R&& inputs)
{
  typedef decay_t<decltype(
    f(*inputs.begin()))>
    result_type;
  OutContainer<
    result_type,
    allocator<result_type>>
    result;
  for (auto&& item : inputs) {
    result.push_back(f(item));
  }
  return result;
}

使用

vector<int> v{1, 2, 3, 4, 5};
int add_1(int x)
{
    return x + 1;
}

auto result = fmap(add_1, v);

可以看到,我们默认的输出容器是vector,这个输出迭代器有两个模板参数

上面的&&是万能引用,首先我们用decltype推导出映射后的参数类型,然后使用decay_t来将其变成普通的值类型

然后定义对应类型的容器,使用类似OutContainer<T, allocator<T>>的写法

然后遍历输入,并将映射后的值放到容器中并返回

标签: c++
最后更新:2021年9月2日

sheep

think again

点赞
< 上一篇
下一篇 >

文章评论

取消回复

COPYRIGHT © 2021 heavensheep.xyz. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS