这篇的重点内容是讲解算法，但是在正式开始之前，我强烈建议你再回顾一下上一篇的内容，因为要理解这个算法，就需要意识到协议的具体细节不重要，重要的是这种协议是否可以用一种树形结构来表达，而且在这个结构中，每一个节点（即field）要么是一个必要节点，要么是一个可选节点，且它最多只依赖于一个之前的（如果我们以文件目录树来想像这棵树的话，一个节点更靠前就意味着这个节点更靠近上方的位置）节点，即，不能出现一个节点依赖于之前的多个节点——除非这些节点可以合并为一个复合节点（即子协议field）——或之后的某个节点，但是多个节点都依赖于之前的同一个节点的情况是允许的（通常，我们也可以把这些节点合并为一个复合节点）。通俗的讲，就是我们接下来要讨论的这个算法，与这棵协议树长得什么样子无关（对于同一个协议，不同的人可能将它描述成不同的样子，这种情况是可能的，也是允许的），而只与每个节点的性质有关。正是这个特性，使得这个算法具有极强的通用性。这样，我们只要保证我们描述出的协议树与协议文档是一致的（检查其正确性也要比分析一堆的if
else和位运算容易得多），那么就可以期待我们能够得到一个正确的结果。
听起来，这个算法好像很复杂，其实不然，它意外的非常简单，但需要你有较好的想像力。是不是有点迫不及待了呢？好，现在我们先从一个特例开始：所有节点都是必要的节点，没有任何两个节点有依赖关系（即所有节点都是独立的）。对于这种情况，我们想像一下把这棵树“拍平”，只留下叶子节点（但先后顺序不变），那么这个叶子节点组成的节点序列，不就是我们要的field序列了吗？而要得到一个“拍平”的树，我们只需要执行一个深度优先的遍历算法就可以，是不是很简单呢？（事实上这个特例有更简单的处理方法，就是按协议写一个大大的嵌套式的struct，然后直接对buffer指针做一个强制类型转换即可，这个例子提醒我们，程序设计是一门非常灵活的艺术，我们不能教条的去看待它，这也是我本人不欣赏《设计模式》一书的原因，特别是现在满天下都是些抄书的呆子，还自以为是的显摆自己）
那么当我们引入了可选节点（即依赖于之前的某个节点的节点）后，是否情况就不一样了呢？其实是一样的，还是想像我们把一棵树“拍平”，只不过现在，有些叶子节点我们需要删除，删除的原则就是，先一个一个的检查这个叶子是否是必要节点，如果是，就保留这个节点，同时修正bit流的访问偏移量（即指向下一个field的起始位置）；而如果不是，就向（已生成的）序列的前方找到它的条件节点，然后看看它的条件节点的内容是不是允许这个可选节点出现（或者计算出这个可选节点的个数），如果允许，就保留（并修正bit流的访问偏移量），否则，就删除。看到了吗？差别只有一点点，是不是也很简单？（现在你应该明白，为什么上一篇文章中，我们的协议描述接口要设计成那样了吧？）
具体的代码实现不妨自己来写一写，毕竟我这里只是写博客，不是写论文。如果实在懒得写，又想获得源代码，可以给我留言或发邮件。好，我们的讨论就到这……“等等”，那里有位朋友站起来说，“你只解释了从bit流产生field序列的算法，可还没讨论它的逆向算法呢！”，其实……这里我故意卖了一个关子，呵呵……正所谓“好戏还在后头”，现在，我将向各位展示最神奇的部分：同样的算法，也可以用于产生一个bit流，是的，你没有听错！不过，首先你需要转变观念，不要用一个函数的眼光去看待这个算法（即一个bit流进去了，出来一个field序列），而要用流的观念去看待这个算法（即一个bit流进去以后，每次出来一个field，通过不断的获取下一个field来产生一个序列），前者bit流只能是输入，而后者bit流既可以是输入，也可以是输出。
当我们需要产生一个bit流时，因为任何协议的第一个叶子节点理所当然的是一个必要节点，所以我们仅仅根据它的field描述就可以产生一个field，而我们需要做的就是让这个field记住它在bit流中的偏移量（field的大小可以通过其元函数求得，参见上一篇文章），然后我们就可以在得到了这个field之后，再往bit流的buffer中填入合适的数据，然后再来处理下一个节点。而第二个如果是一个可选节点，那么它的条件节点必然是第一个节点，而我们这时已经产生了第一个节点，可以判断我们是否需要产生第二个节点，如果需要，没什么好说的，产生之；而如果不需要，那么再看第三个节点。如果第三个节点也依赖于第一个节点，那么就和第二个节点的情况一样；如果它依赖的是第二个节点，那么我们在构建协议树时，可以把它和第二个节点划归到同一个复合节点中（即使协议中并没有这种明确的划分），这样当我们跳过第二个节点的同时，我们就可以跳过它的所有相关节点，直到下一个不相关节点，而此时这个节点的条件节点也必然是第一个节点，否则说明我们的协议描述是错的（多么神奇，这算法还有检错功能）！利用数学归纳法，我们可以证明（具体证明过程略），其后的每一个节点都是如此，也就是说，当我们得到了前面的节点序列后，我们就可以判断当前需要产生哪种（叶子）节点，然后再往bit流的buffer中填入合适的数据。
看到上面的结论，你是否会大吃一惊呢？这个算法由于引入了元类和流的编程思想，它的通用性居然会有如此大的飞跃，而算法却又是如此的简单，我们甚至不用写代码就可以把它解释清楚（really？）！这是否是你曾经考虑到了的呢？写到这里，这次的话题就快要结束了（如果是一部戏剧，以这样的一种戏剧性的方式结束是再好不过的了！），最后再做一点总结，希望通过上面的这个例子，能够让各位领悟到元类编程思想的巨大魅力。然而凡事都有两面，不可一味追求技术的巧妙（或正相反，我见过的许多程序员都是懒得追求这种东西的，这也是为什么我们的软件质量参差不齐的原因之一！一个再好的设计，和一堆垃圾程序捆绑在一起，也会变成一堆垃圾，甚至是垃圾的平方，以此警示新人朋友！），而忽视了它对解决具体问题的适用性，从而让我们的思想变得僵化。
最后，感谢大家关注此文，有任何错误或疏漏还请批评指正！祝各位工作顺利，学习进步！
C++语言中的元类编程（八）,布布扣,bubuko.com
C++语言中的元类编程（八）