现代C++实战30讲
吴咏炜
前 Intel 资深软件架构师
立即订阅
3755 人已学习
课程目录
已更新 18 讲 / 共 30 讲
0/4登录后,你可以任选4讲全文学习。
课前必读 (2讲)
开篇词 | C++这么难,为什么我们还要用C++?
免费
课前必读 | 有关术语发音及环境要求
基础篇 (9讲)
01 | 堆、栈、RAII:C++里该如何管理资源?
02 | 自己动手,实现C++的智能指针
03 | 右值和移动究竟解决了什么问题?
04 | 容器汇编 I:比较简单的若干容器
05 | 容器汇编 II:需要函数对象的容器
06 | 异常:用还是不用,这是个问题
07 | 迭代器和好用的新for循环
08 | 易用性改进 I:自动类型推断和初始化
09 | 易用性改进 II:字面量、静态断言和成员函数说明符
提高篇 (7讲)
10 | 到底应不应该返回对象?
11 | Unicode:进入多文字支持的世界
12 | 编译期多态:泛型编程和模板入门
13 | 编译期能做些什么?一个完整的计算世界
14 | SFINAE:不是错误的替换失败是怎么回事?
15 | constexpr:一个常态的世界
16 | 函数对象和lambda:进入函数式编程
现代C++实战30讲
登录|注册

13 | 编译期能做些什么?一个完整的计算世界

吴咏炜 2019-12-25
你好,我是吴咏炜。
上一讲我们简单介绍了模板的基本用法及其在泛型编程中的应用。这一讲我们来看一下模板的另外一种重要用途——编译期计算,也称作“模板元编程”。

编译期计算

首先,我们给出一个已经被证明的结论:C++ 模板是图灵完全的 [1]。这句话的意思是,使用 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/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《现代C++实战30讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(12)

  • 吃一个芒果
    template <int num1, int num2>
    struct Add_
    {
        const static int res = num1 + num2;
    };

    template <int num1, int num2>
    struct Sub_
    {
        const static int res = num1 - num2;
    };

    template <bool Condition>
    struct If_;

    template <>
    struct If_ <true>
    {
        template<int num1, int num2>
        using type = Add_<num1, num2>;
    };

    template <>
    struct If_ <false>
    {
        template<int num1, int num2>
        using type = Sub_<num1, num2>;
    };

    template<int num1, int num2>
    template<bool Condition>
    using If = typename If_<Condition>::template type<num1, num2>;

    template<int num1, int num2>
    using True = If<true>;

    template<int num1, int num2>
    using False = If<false>;

    老师你好,我想问一个语法方面可能比较钻牛角尖的问题
    我定义了If_,用来在true和false的时候返回不同的模板。又定义了True和False,这样就可以通过True<a, b>::res或者False<a, b>::res来获取不同模板的计算结果。但是如果我想用类似If<condition><a, b>::res这样的调用(不知道我表达清楚没有)来获取不同的结果(在不改If_定义的情况下),应该怎么写呢?谢谢!
    2020-01-02
  • 三味
    这个课后思考题真不是盖得。。。还看到了5分钟编译期堆排序的段子。。。看得我心惊胆战。。。
    不过还是一堆百度写出了一个,针对int型,写出从[0, N)的编译期生成数组的例子。。。兼容其他类型还要再额外写好多代码。。偷懒直接写了int型。。。
    我在msvc下测试了,应该没问题。。。用到了模板不定参数,其他不知道什么技巧的方法。。。
    想要让int N转换成从0,1,2,3,4,5 。。。卡在了如何把这堆参数展开。。写得可能复杂一些。。不知道怎么更简单。。 下面代码吧:

    template<int... values>
    struct IntegerSequence {};

    template<typename T, T v, typename INTEGER_SEQUENCE>
    struct PushBack;

    template<int v, int... values>
    struct PushBack<int, v, IntegerSequence<values...>> {
    using type = IntegerSequence<values..., v>;
    };

    template<int N>
    struct IntegerRange {
    using type = typename PushBack<int, N-1, typename IntegerRange<N-1>::type>::type;
    };

    template<>
    struct IntegerRange<1> {
    using type = IntegerSequence<0>;
    };

    template<int N, typename INTEGER_SEQUENCE>
    struct RangeArray;

    template<int N, int... values>
    struct RangeArray<N, IntegerSequence<values...>> {
    static constexpr std::array<int, N> value = {values...};
    };

    template<int N> using Range = RangeArray<N, typename IntegerRange<N>::type>;

    测试:
    auto A = Range<5>::value;
    不出意外,会生成std::array<int, 5>{0,1,2,3,4};

    作者回复: 很好!第 18 讲你会学得很轻松。😉

    2019-12-30
  • 总统老唐
    吴老师,关于最后这个例子,有两个小问题:
    1,我们平时定义一个 vector 的时候,一般并不会写成 vector<int, allocator<int>> vec 这种形式,为什么模板函数里面定义返回值 result 时,需要多一个 allocator?
    2,fmap函数的入参和for循环,全都用的右值引用,有什么特殊考量么?

    作者回复: 1. 因为模板的定义就是这个样子,虽然我们平时第二个参数用的都是默认模板参数。

    2. 不是右值引用,是转发引用。复习一下第 3 讲结尾部分吧。

    2019-12-27
  • 总统老唐
    吴老师,看了你的While模板,试着想把这个计算累加的功能扩展一下,输入任意两个数,可以求他们之间的数的累加和,代码如下:
    template <int from, int to, int sum>
    struct SumAnyTwo_A
    {
        static const bool cond_value = from != to;
        static const int res_value = sum;
        typedef integral_constant<int, res_value> res_type;
        typedef SumAnyTwo_A<from + 1, to, sum + from> next_type;
    };

    template <int from, int to, int sum>
    struct SumAnyTwo_B
    {
        static const bool cond_value = from != to;
        static const int res_value = sum;
        typedef integral_constant<int, res_value> res_type;
        typedef SumAnyTwo_B<from - 1, to, sum + from> next_type;
    };

    template <bool valueCompare, int from, int to>
    struct SumAnyTwo;

    template <int from, int to>
    struct SumAnyTwo<true, from, to>
    {
        typedef SumAnyTwo_A<from, to, 0> addType;
    };

    template <int from, int to>
    struct SumAnyTwo<false, from, to>
    {
        typedef SumAnyTwo_B<from, to, 0> addType;
    };

    template <int from, int to>
    struct SumTwo
    {
        typedef SumAnyTwo<(from > to), from, to> type;
    };

    遇到了两个问题:
    1,这段代码看起来不够优雅,在C++ 98 的范畴内,有更好的模板元编程实现方式么?
    2,当我试图调用这个While模板时,出现如下状况,不明白为什么第一个会报错
            While<SumTwo<8, 3>::type::addType>::type::value // 报错,template instantiation depth exceeds maximum of 900
            While<SumAnyTwo_B<8, 3, 0>>::type::value // OK
           While<SumAnyTwo<(8 - 3 < 0), 8, 3>::addType>::type::value //OK

    作者回复: 我真是自作自受,得看这样的代码。😜

    1. 我给的这些模板只是说明能力的,肯定不是让你真的这么写代码的。比如你这种累加,可以考虑这样写(只考虑了正向):

    template <int from, int to, int sum, bool ending>
    struct sum_two_op;

    template <int from, int to, int sum>
    struct sum_two_op<from, to, sum, false> {
        static const int value = sum;
    };

    template <int from, int to, int sum>
    struct sum_two_op<from, to, sum, true> {
        static const int value =
            sum_two_op<from + 1, to, sum + from, (from < to)>::value;
    };

    template <int from, int to>
    struct sum_two {
        static const int value = sum_two_op<from, to, 0, (from <= to)>::value;
    };

    2. 你已经很靠近了,只犯了一个小错误,SumTwo 里的方向。应该是:

    template <int from, int to>
    struct SumTwo {
        typedef SumAnyTwo<(from < to), from, to> type;
    };

    另外,你目前的处理对于 from==to 的情况有点问题。可参考我上面的写法,那是可以正确处理的。

    2019-12-27
    3
  • zhang
    您好,我想问一个mutex相关的问题,虽然这部分内容以后会讲,但我现在工作中有一个疑问,麻烦您看一下,谢谢。
    代码简写如下:
    class Mutex {
    public:
        pthread_mutex_t mutex;
        Mutex():mutex(PTHREAD_MUTEX_INITIALIZER) {}
        void lock() {
            pthread_mutex_lock(&mutex);
        }
        void unlock() {
            pthread_mutex_unlock(&mutex);
        }
    };
    class Cond {
    public:
        pthread_cond_t cond;
        Cond():cond(PTHREAD_COND_INITIALIZER) {}
        void signal() {
            pthread_cond_signal(&cond);
        }
        void broadcast() {
            pthread_cond_broadcast(&cond);
        }
        void wait(Mutex &mutex) {
            pthread_cond_wait(&cond, &mutex.mutex);
        }
    };
    class ScopeLock {
        Mutex &mutex;
    public:
        ScopeLock(CanMutex &_mutex):mutex(_mutex) {
            mutex.lock();
        };
        ~ScopeLock() {
            mutex.unlock();
        };
    };

    class Client
    {
    public:
        Mutex inter_mutex;
        Mutex mutex;
        Cond cond;
        bool pending;
        Client():pending(false){}
        ~Client(){}
        void Lock() {
            mutex.lock();
        }
        void Unlock() {
            mutex.unlock();
        }
        void sendData() {
            const ScopeLock inter_protect(inter_mutex);
            const ScopeLock protect(mutex);

            //send_to_server();

            while (!pending) {
                cond.wait(mutex);
            }
            pending = false;
        }
        void recvData() {
            const ScopeLock protect(mutex);
            pending = true;
            cond.signal();
        }
    };
    我有几个线程会执行同一个Client对象的sendData函数,有一个线程执行Client对象的recvData函数。我主要想问我几个sendData线程需要同步执行,执行完一个sendData发送后,再执行另一个sendData。那么我在sendData函数最开始加整个函数范围的锁const ScopeLock inter_protect(inter_mutex);,是否可以这样做?谢谢!

    作者回复: 对你的业务场景不熟悉,随便评论几句。

    ・C++11 里有现成的 mutex、condition_variable 和 unique_lock。
    ・Client::Lock 和 Client::Unlock 似乎没有用处。
    ・变量 pending 的命名让人困惑:收到数据了,“挂起”标志被设为真,然后发送数据就能继续往下执行了?连续两次 sendData 中间必须有一次 recvData 才行,而且 sendData 里的等待是在发送之后?这块感觉有问题。
    ・inter_mutex 和 inter_protect 本身目前没有看出问题。

    2019-12-26
    2
  • 安静的雨
    模版编程很有趣,期待老师的更新。

    作者回复: 觉得有趣就好,这个我们要讲上好几讲的。

    2019-12-25
  • 总统老唐
    记得吴老师之前预告过,这一节可能会比较难,确实被难住了。在第一个 If 模板这里就被卡住了,老师能给个简单的例子来说明这个 If 模板该如何使用么?

    作者回复: 下面的函数和模板是基本等价的:

    int foo(int n)
    {
      if (n == 2 || n == 3 || n == 5) {
        return 1;
      } else {
        return 2;
      }
    }

    template <int n>
    struct Foo {
      typedef typename If<
        (n == 2 || n == 3 || n == 5),
        integral_constant<int, 1>,
        integral_constant<int, 2>>::type
        type;
    };

    你可以输出 foo(3),也可以输出 Foo<3>::type::value。

    2019-12-25
  • 禾桃
    脑壳儿疼的兄弟姐妹们,我这有个小偏方, 哈哈

    While< Sum<2>::type >::type::value 实例化(instantiation)过程
    --> While< SumLoop<0, 2> >::type::value
    --> WhileLoop<SumLoop<0, 2>::cond_value, SumLoop<0, 2>>::type::value
    --> WhileLoop<true, SumLoop<0, 2>>::type::value

    --> WhileLoop<SumLoop<0, 2>::cond_value, SumLoop<0, 2>::next_type>::type::value
    --> WhileLoop<true, SumLoop<2, 1>>::type::value

    --> WhileLoop<SumLoop<2, 1>::cond_value, SumLoop<2, 1>::next_type>::type::value
    --> WhileLoop<true, SumLoop<3, 0>>::type::value

    --> WhileLoop<SumLoop<3, 0>::cond_value, SumLoop<3, 0>::next_type>::type::value
    --> WhileLoop<false, SumLoop<3, -1>>::type::value

    --> SumLoop<3, -1>::res_type::value

    -->integral_constant<int, 3>::value
    -->3

    作者回复: 对,对于模板,就是要在脑子里或纸上、电脑上把它展开……☺️

    2019-12-25
  • 小一日一
    #include <iostream>
    #include <vector>
    #include <type_traits>

    using namespace std;

    template< class T >
    using decay_t = typename decay<T>::type;

    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;
    }

    int add_1(int x)
    {
        return x + 1;
    }

    int main()
    {
        vector<int> v{1, 2, 3, 4, 5};

        auto result = fmap(add_1, v);

        for (auto &&v : result) {
            cout << v << endl;
        }
    }

    用g++ 4.8.5 带std=c++11参数编译能通过并正确运行,但是有warning:
    13_5.cc:12:28: warning: ‘fmap’ function uses ‘auto’ type specifier without trailing return type [enabled by default] auto fmap(F&& f, R&& inputs)

    请问老师如何加尾置返回类型消除warning?

    作者回复: 试试 c++1y、c++14 等标准选项了。这个 GCC 太老了……我要求 C++17、GCC 7 的。

    2019-12-25
    2
  • 李义盛
    一到模板就处于看不懂状态了。

    作者回复: 拿纸笔来展开试试?实际上就是一种展开而已。

    2019-12-25
  • 禾桃
    “常用的一个技巧就是用 is_trivially_destructible 模板来判断类是否是可平凡析构的——也就是说,不调用析构函数,不会造成任何资源泄漏问题。”

    麻烦解释一下,
    #1 这个类模版是如何识别“,不调用析构函数,不会造成任何资源泄漏问题”? 这的资源包括new的堆内存吗?
    #2 trivially这个词总是觉得很难理解,C++里,使用这个词的目的,到底是什么?

    作者回复: 1 是有点编译器魔法的。如果你有析构函数,或者你没有析构函数但有个非 POD 数据成员,is_trivially_destructible 就不成立了。

    2 trivial 是很常见的数学术语,没什么特别的。见:

    https://baike.baidu.com/item/%E5%B9%B3%E5%87%A1/16739977
    https://zh.wikipedia.org/wiki/%E5%B9%B3%E5%87%A1_(%E6%95%B8%E5%AD%B8)
    https://en.wikipedia.org/wiki/Triviality_(mathematics)

    2019-12-25
  • hello world
    一直对模板元编程感兴趣,但总是搞不明白,今天学习很有收获,特别是最后的fmap,感谢老师,记得模板编程还有policy之类的东西,老师之后在编译期这方面还会更详细讲解吗

    作者回复: 编译期要连续讲到第 18 讲,甚至之后还会有提到的机会。你喜欢那是最好了。我是怕很多人会被编译期编程吓退呢。😅

    policy 这个概念不单独讲,但我觉得在讨论了使用常数来对模板进行特化之后,这个概念应该没有特别之处。我们的例子倒是会有标准库提供的 policy。😁

    2019-12-25
收起评论
12
返回
顶部