李老师群课之再谈元编程

只看该作者 · 2013-8-20 11:28

主讲：李老师（John Lee)

先看一段代码：

#include <cstdint>

#include <iostream>

#include <iomanip>

#include <type_traits>

namespace crc32 {

template <uint32_t CRC, uint8_t BIT = 0>

struct byte

: byte <

std::conditional <

(CRC & 1) != 0,

std::integral_constant <uint32_t, (CRC >> 1) ^ 0xedb88320>,

std::integral_constant <uint32_t, (CRC >> 1)>

>::type::value,

BIT + 1

> { };

template <uint32_t CRC>

struct byte <CRC, 8> { uint32_t value{ CRC }; };

template <uint16_t I = 0>

struct table : byte <I>, table <I + 1> { };

template <>

struct table <256> { };

}

crc32::table <> data;

int main()

{

using namespace std;

uint_fast16_t n = sizeof (data) / sizeof (uint32_t);

auto p = reinterpret_cast<uint32_t*>(&data);

uint_fast8_t l = 8;

do {

cout << "0x" << setfill('0') << setw(8) << hex << *p++ << ',';

if (--l == 0) {

cout << endl;

l = 8;

}

} while (--n);

}

namespace 里有2个类模板，

1、

template <uint32_t CRC, uint8_t BIT = 0>

struct byte;

2、

template <uint16_t I = 0>

struct table;

先说第1个：byte，

template <uint32_t CRC, uint8_t BIT = 0>

struct byte

: byte <

std::conditional <

(CRC & 1) != 0,

std::integral_constant <uint32_t, (CRC >> 1) ^ 0xedb88320>,

std::integral_constant <uint32_t, (CRC >> 1)>

>::type::value,

BIT + 1

> { };

byte类模板有两个非类型模板参数：

1、uint32_t CRC

2、uint8_t BIT

这个CRC参数，是8次计算循环的初值，相当于这个：

参数BIT，是8次循环的次数，初值是0，计算使用了元编程。

计算一次crc的语句：

std::conditional <

(CRC & 1) != 0,

std::integral_constant <uint32_t, (CRC >> 1) ^ 0xedb88320>,

std::integral_constant <uint32_t, (CRC >> 1)>

>::type::value,

逻辑等价于：

if (crc & 1)

crc = (crc >> 1) ^ 0xEDB88320;

else

crc >>= 1;

conditional是C++标准头文件<type_traits>中的一个模板。

（此时有人捣乱…）算了，晚上再讲。

下午的例子，简化一下：

#include <cstdint>

#include <iostream>

#include <iomanip>

namespace crc32 {

template <uint32_t CRC, uint8_t BIT = 0>

struct byte : byte <(CRC >> 1) ^ (-int32_t (CRC & 1) & 0xedb88320), BIT + 1> { };

template <uint32_t CRC>

struct byte <CRC, 8> { uint32_t value{ CRC }; };

template <uint16_t I = 0>

struct array : byte <I>, array <I + 1> { };

template <>

struct array <256> { };

struct table : private array <> {

const uint32_t& operator [] (int i) const

{

return reinterpret_cast<const uint32_t*>(this);

}

};

}

const crc32::table data;

int main ()

{

using namespace std;

uint_fast16_t n = sizeof (data) / sizeof (data[0]);

uint_fast16_t i = 0;

uint_fast8_t l = 8;

do {

cout << "0x" << setfill('0') << setw(8) << hex << data << ',';

if (--l == 0) {

cout << endl;

l = 8;

}

} while (++i < n);

}

下午写的，用了两个type_traits的模板，复杂了一些，刚才简化掉了，应该好看些了。但还是有一个C++11的语法不能去掉。这里：

456.jpg (14.5 KB )

下载附件

2013-8-20 11:25 上传

这个C++11语法叫做：Non-static data member initializers，可以在定义数据成员的同时，给出初始值。以前是不允许这种语法的。

比如像C：

struct A {

int data0;

int data1;

};

定义只能类似这样，成员的初始化，要在结构体变量定义时，才能进行。struct A a = { 1, 2 };

C++11做了改进，允许在定义数据成员时，立即给出初始值。而在实例化对象时，就可以不再初始化了。

struct A {

int data0 = 1;

int data1 = 2;

};

A a; // a 初始化为 { 1, 2 }

成员初始化，= 和 { } 都可以，但推荐用 { }，

struct A {

int data0 { 1 };

int data1 { 2 };

};

用 {} 来初始化，称为：Uniform initialization，建议大家以后写C++11程序时，都用 {}来初始化赋值。

好，来看看namespace crc32，这个namespace里定义了4个类模板，其中两个是primary模板，另外两个是偏特化模板。

第1个primary模板：

template <uint32_t CRC, uint8_t BIT = 0>

struct byte;

这个模板有两个参数：CRC，BIT。CRC用做每次循环的crc初始值，BIT用做循环计数。我们先从C的算法来看：

uint32_t crc = i;

uint8_t j;

for (j = 0; j < 8; j++) {

if (crc & 1)

crc = (crc >> 1) ^ 0xEDB88320;

else

crc >>= 1;

}

第1次循环之前，crc被外层循环赋了初值，0,1,2,3,4。。。。内层循环固定8次，crc用做每次循环计算的初值和结果，循环的常量计算，用C++来写必须用递归，我们先把这个迭代循环改成递归：

我先贴一下迭代的方法：

uint32_t crc32tbl[256];

int main ()

{

int i;

for (i = 0; i < 256; i++) {

uint32_t crc = i;

uint8_t j;

for (j = 0; j < 8; j++) {

if (crc & 1)

crc = (crc >> 1) ^ 0xEDB88320;

else

crc >>= 1;

}

crc32tbl = crc;

}

....

}

这段迭代可以简化一下：

uint32_t crc32tbl[256];

int main ()

{

int i;

for (i = 0; i < 256; i++) {

uint32_t crc = i;

uint8_t j;

for (j = 0; j < 8; j++) {

crc = (crc >> 1) ^ (-int32_t (crc & 1) & 0xEDB88320);

}

crc32tbl = crc;

}

....

}

crc = (crc >> 1) ^ (-int32_t (crc & 1) & 0xEDB88320);

等于

crc = (crc >> 1) ^ ((0 - int32_t (crc & 1)) & 0xEDB88320);

crc & 1的结果，不是1就是0，先变成有符号数，然后取负数，就是 0 - 1，或者 0 – 0，得 0xffffffff, 或 0。

crc = (crc >> 1) ^ (0xffffffff & 0xEDB88320);

或者

crc = (crc >> 1) ^ (0 & 0xEDB88320);

crc = (crc >> 1) ^ (0xffffffff & 0xEDB88320);

等于

crc = (crc >> 1) ^ 0xEDB88320;

----------------

crc = (crc >> 1) ^ (0 & 0xEDB88320);

等于

crc = (crc >> 1);

跟：

if (crc & 1)

crc = (crc >> 1) ^ 0xEDB88320;

else

crc >>= 1;

是不是一样啊？

好了，公布答案：

uint32_t crc32tbl[256];

uint32_t byte(uint32_t crc, uint_fast8_t bit)

{

if (bit == 8)

return crc;

crc = (crc >> 1) ^ (-int32_t (crc & 1) & 0xEDB88320);

return byte (crc, bit + 1);

}

int main ()

{

int i;

for (i = 0; i < 256; i++) {

crc32tbl = byte (i, 0);

}

......

继续简化一下:

uint32_t byte(uint32_t crc, uint_fast8_t bit)

{

if (bit == 8)

return crc;

return byte ((crc >> 1) ^ (-int32_t (crc & 1) & 0xEDB88320), bit + 1);

}

到这步，就离C++很近了。

我们来看第1个原始模板：

template <uint32_t CRC, uint8_t BIT = 0>

struct byte : byte <(CRC >> 1) ^ (-int32_t (CRC & 1) & 0xedb88320), BIT + 1> { };

除了 if (bit == 8) return crc 之外，很相似吧？

C的递归调用是，byte函数调用了byte函数（自己），参数是经过计算之后的新数据。

好了，我们继续说那个if (bit == 8) return crc;

原始模板：

template <uint32_t CRC, uint8_t BIT = 0>

struct byte : byte <(CRC >> 1) ^ (-int32_t (CRC & 1) & 0xedb88320), BIT + 1> { };

可以看到，其中并没有结束递归的条件。

模板递归的结束条件，需要特殊的手法，就是所谓的“偏特化”模板。

我们来看看byte原始模板的偏特化模板：

template <uint32_t CRC>

struct byte <CRC, 8> { uint32_t value{ CRC }; };

偏特化，是指模板参数，有部分是固定值。而原始模板的参数，都是传入的。比如byte的原始模板，你可以这样实例化：

byte <0, 0>

也可以这样：

byte <1234, 56>

总之参数由你定，而byte的偏特化模板，第2个参数BIT固定为8，C++的匹配规则是，如果参数符合偏特化条件，就优先匹配偏特化模板。

比如你这样写：

byte <10000, 8>

那么就会匹配到偏特化的byte模板了。

好了，我们来联系一下实际：

template <uint32_t CRC, uint8_t BIT = 0>

struct byte : byte <(CRC >> 1) ^ (-int32_t (CRC & 1) & 0xedb88320), BIT + 1> { };

template <uint32_t CRC>

struct byte <CRC, 8> { uint32_t value{ CRC }; };

byte 模板第1次实例化时，CRC会给0，BIT会给0（这是由上层模板定义的，稍后来说），我们就按CRC = 0, BIT = 0开始推演：

原始模板 byte <CRC = 0, BIT = 0> 继承了

原始模板 byte <CRC = ?, BIT = 1> 继承了

原始模板 byte <CRC = ?, BIT = 2> 继承了

.....

原始模板 byte <CRC = ?, BIT = 7> 继承了

偏特化模板 byte <CRC = ?, BIT = 8>

？我就不具体算了，每次继承，BIT 参数会 + 1，当继承到 byte <CRC = ?, BIT = 8> 时，编译器发现 BIT 参数符合偏特化模板的条件。byte 的偏特化模板定义：

template <uint32_t CRC>

struct byte <CRC, 8> { uint32_t value{ CRC }; };

可以看见，它没有再继承任何基类了。而是定义了一个数据成员：value。使用了C++11的非静态数据成员初始化语法，value的值初始化为模板参数:CRC，而模板参数CRC正是第8次递归计算的结果，与 if (bit == 8) return crc; 中的crc 值，是一样的。只不过C的crc值，是函数参数传递进来的，而C++的CRC值，是模板参数传递进来的。

一次讲多了可能消化不好，你们先仔细理解一下模板递归，联系一下byte的原始模板和偏特化模板来看。

（模板里的常数计算，完全是由编译器来做，我只是让编译器把计算好的结果，放在struct 的数据成员里。）

（下课……）

只看该作者 · 2013-8-20 11:40

顶起

只看该作者 · 2013-8-20 16:41

mark了再看

只看该作者 · 2013-8-20 17:18

花了一天时间,总算看明白了.吐血一升啊

只看该作者 · 2013-8-20 20:45

尚未入门，

只看该作者 · 2013-8-21 09:46

顶起来，让更多人上C++的船

只看该作者 · 2013-8-21 10:17

复制

template <bool _Cond,typename _Iftrue,typename _Iffalse>

struct conditional

{typedef _Iftrue type;};

template <typename _Iftrue,typename _Iffalse>

struct conditional<false,_Iftrue,_Iffalse>

{

typedef _Iffalse type;

};

这个是什么意思?

只看该作者 · 2013-8-21 15:27

参见李老师群课之元编程：

在C++系统头文件中，有一个名为type_traits的文件里面有一个模板：conditional

前置定义是：
template<bool, typename, typename>

struct conditional;

根据说明，conditional模板是根据第1个参数bool的值（true或false），来确定conditional中的type的类型。

如果bool 为 true，则type为第2个参数的类型，如果为false，则type为第3个参数的类型。

我们先说使用，比如，我们需要根据一个bool常量来定义一个数组，如果常量值为true，我们定义这个数组为uint8_t，否则定义为uint16_t：

typename std::conditional<COND, uint8_t, uint16_t>::type array[20];

这个就是定义array数组。cond为真，则是uint8_t array[20]。

实际使用远比这个复杂，太简单的情况也用不着mixin crtp等等。

这里要理解conditional的type，是怎么跟随bool参数变化的。

template<bool _Cond, typename _Iftrue, typename _Iffalse>
struct conditional
{ typedef _Iftrue type; };

// Partial specialization for false.
template<typename _Iftrue, typename _Iffalse>
struct conditional<false, _Iftrue, _Iffalse>
{ typedef _Iffalse type; };

就这么几行。这里定义了“两个”conditional类模板。

第1个是普通的

template<bool _Cond, typename _Iftrue, typename _Iffalse>

struct conditional

{ typedef _Iftrue type; };

第1个在struct里直接定义了 type是_Iftrue。如果没有第2个conditional，那么我们永远只能得到一个固定的类型。

第2个conditional类模板定义，术语称为partial specialization，一般翻译为“偏特化”，就是部分特别处理。

// Partial specialization for false.

template<typename _Iftrue, typename _Iffalse>

struct conditional<false, _Iftrue, _Iffalse>

{ typedef _Iffalse type; };

这个偏特化的类模板，固定了第1个参数bool为false，其余两个参数不变。

编译器就知道，如果程序里使用了conditional类模板，并且第1个参数为false的，就去匹配那个偏特化的版本。在这个版本的struct 里，定义了 type 类型为 _Iffalse，就是第3个参数的类型。

回到最开始的话题。C++可以根据一些条件（可以说就是类模板参数），来定义某类型。这离不开偏特化或全特化。

实际上，你看到的不同的类型，是分别属于不同特化版本的类模板。然而，对程序的使用来说，可以认为是透明的。就比如conditional类模板，如果你不去看type_traits文件，那么你可能根本不知道它具体是怎么实现的，你可能认为它就是“一个”类模板。

元编程就是通过提供了各种特化的类模板，每个模板中都有一个结果，来让程序不断地匹配，从而得到想要的结果。就是让编译器自己去选择合适的模板。这就是编译时计算。

只看该作者 · 2013-8-22 16:26

路过学习的

1万 · 2013-8-23 01:58

xukaiming 发表于 2013-8-20 17:18
花了一天时间,总算看明白了.吐血一升啊

:handshake

只看该作者 · 2013-8-23 16:29

谢谢分享

只看该作者 · 2013-8-23 22:19

我抛的砖头引出了一片美玉啊.好啊

只看该作者 · 2013-8-26 11:24

曾经有个书中说： C++语言是人们投入最多精力去研究它本身的语言。望而却步。

只看该作者 · 2013-8-27 09:57

我表示看不懂

只看该作者 · 2013-8-28 22:20

这种垃圾代码不要拿出来讲~

只看该作者 · 2013-8-29 10:20

楼上戾气挺重

只看该作者 · 2013-8-29 15:37

haiyuan254 发表于 2013-8-28 22:20
这种垃圾代码不要拿出来讲~

哥们，贴点不是垃圾的代码出来讲讲

只看该作者 · 2013-8-29 15:40

同样是玉有人认为是石头有认为是玉。这并不出奇。这是人的鉴赏水平和能力有关。当然也有小孩会老实的说出来“but he is nothing on!”

只看该作者 · 2013-8-29 15:45

haiyuan254 发表于 2013-8-28 22:20
这种垃圾代码不要拿出来讲~

如果你认为是垃圾请指出垃圾之处，如果大家都认为你说得有理，那才是真正的交流，而不是无理放纵，如果客官只是在这里意淫，就不必大放厥词！

只看该作者 · 2013-8-29 15:46

古董也一样，有人把赝品当宝贝，有人把宝贝当垃圾，慧眼识珠，也不是人人都能做到的

李老师群课之 再谈元编程

相关下载

相关帖子

技术导师奖章

缘定三生

精英会员奖章

沉静之湖泊

涓涓之细流

伴坛终老

技术奇才奖章

精华达人奖章

无冕之王奖章

十世金身

技术新星奖章

湍急之河流

社区建设奖章

经常做客

核心会员奖章

坚毅之洋流

七世轮回

偶尔光临

李老师群课之再谈元编程