C++语言中的元类编程(八)

这篇的重点内容是讲解算法,但是在正式开始之前,我强烈建议你再回顾一下上一篇的内容,因为要理解这个算法,就需要意识到协议的具体细节不重要,重要的是这种协议是否可以用一种树形结构来表达,而且在这个结构中,每一个节点(即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++语言中的元类编程(八)

上一篇:上一帖的汇编语言


下一篇:技巧:在 C/C++中如何构造通用的对象链表[转]