表驱动法（Table-Driven ）在程序中应用
Singleton 的C++实现

小窥模板元编程

皮贝贝 posted @ 2008年7月27日 01:12 in 模式之灾 , 2905 阅读

1.追溯历史的脚步 
         1994年的C++标准委员会的会议期间,Erwin Unruh 发现模板可以在编译期间就可以执行计算一些东西。他还写了一个计算素数的程序来演示。同年夏，Todd Veldhuizen受其启发，发表了一份技术报告，次年又在C++ Report上发标了一份关于模板元编程的文章，从此TMP（templete metaprogramming）开始受人关注了。
        至于当年那第一个描述模板元编程的求素数的例子，我们仍然可以找到它，可以一探究竟。尽管是以错误信息的形式报告给我们，不过却说明了编译器的强大功能，也同样的预示我们，编译器也是我们工作的团队一部分，我们已经很久没有协同工作了。不管怎么说，编译期间我们错过了不少可值得利用的东西。


2.关于元编程
     我们听说过太多的元编程技术，各述不一。事实上，元编程是一个比较宽泛的术语，泛指编写能够生成和处理自身的部分代码或其他程序的程序，狭义一些的定义是在运行时而非编译时改变程序行为的编程技术。因此，许多语言的反射机制，代码生成程序，C++等语言的模板元编程和泛型等都可视为元编程。代码和数据的分离也是一种元编程技术，之前所述的表驱动法编程模式就是此类。
     C++中的模板机制本来就是编译期间的活动，在运行期间，这些模板已经变化成为特定的实例。因此C++模板的大多技术都属元编程范畴。像延迟计算，类型检测等。


3.数值计算
     模板元编程是从数值计算堆里爬出来的，也是应用最广的一个领域。一些计算的库中也很多用此实现，速度也很快。下面演示一个求从1到某个数的和：

  1.  
  2. //////////////////////////////////////////////////类似递归版本
  3. //主要接口模板
  4. template< int N >
  5. class Sub
  6. {
  7. public:
  8.      enum { Result = N + Sub<N-1>::Result };
  9. };
  10.  
  11. // 递归终结条件
  12. template<>
  13. class Sub<1>
  14. {
  15. public:
  16.      enum { Result = 1 };
  17. };
  18.  
  19. /////////////////////////////////////////////////////另一个版本
  20.  
  21. //主要接口模板
  22. template< int N >
  23. class Sub2
  24. {
  25. public:
  26.      enum { Result = ( N == 1 ? 1 :  N + Sub<N-1>::Result ) };
  27. };
  28.  
  29. //调用
  30. int main()
  31. {
  32.      cout << "--------------------------" << endl;
  33.      cout << " Sub (12 ) = " << Sub<12>::Result << endl;
  34.      cout << " Sub2 (12 ) = " << Sub2<12>::Result << endl;
  35.      cout << "--------------------------" << endl;
  36. }
  37.  
  38.           
  39.  

     无论那种形式，总会有一个出口。
     在对12进行求值时候，会以下列方式进行：
     

  1.  
  2.            12 + Sub<11>::Result
  3.       12 + 11 + Sub<10>::result
  4.  12 + 11 + 10 + Sub< 9>::Result
  5.  ......
  6.  12 + 11 + 10 + ... + 2 + 1
  7.          

     然后在执行前，代码中已经将 12 ＋ 11 ＋ 10  + ... ＋ 2  + 1 的值作为一个常数进入执行期。所以这样复杂的代码，并不会降低程序的执行效率，相反效率倒有了飞速的提高，许多数学计算库就是得此因才速度快。
   
     实现小要领：有两种形式作为编译期间的存储变量，一是enum，二是新C++标准中的static int  const变量。为了实现纯的模板元编程，使用enum，因为第二种是一个左值，在传递参数时候会有变量地址，而enum绝不会在内存占有位置(变量）。


 模板元编程可包含：  ◎状态变量：模板的参数
                                        ◎循环创建：通过递归，C++标准推荐使用低于17层的递归，有些编译器支持几百层
                                        ◎路径选择：通过使用条件表达式或实例化
                                        ◎整形计算
     
4.效率之争
     在进行编译期间，会对所有模板元进行展开，直至彻底。这在条件选择计算的时候尤其费时，因为要计算可能不会用到的表达式。为此可以创建编译期间的条件表达式IfThenElse（？：的作用），达到与运行期间&& 和 || 的点到为止的效果。 

  1.  
  2. #ifndef IFTHENELSE_H_
  3. #define IFTHENELSE_H_
  4.  
  5. /***************************************************
  6.                 一个让模板元编程的算法效率提高的运算符
  7. 一般情况下，若存在选择子，即?:的运算符号来在编译期间来选择运算对象，
  8. 且选择的运算对象中存在模板元，则一般情况下，会将所有的模板元全部展开，
  9. 即全部运算。这样，无论有无选择它，都会计算，效率会是O(N2),而自我
  10. 定义一个编译时期的?:运算符，则让编译器在编译期间就和运行期间的&&
  11. 或||运算符一样，优化到点到为止，找到适合的就不再运算剩余的内容了，
  12. 这样将编译效率提高到了O(logN).
  13. ****************************************************/
  14.  
  15. template<bool QuestionMark,
  16.          typename Arg1st,
  17.          typename Arg2nd>
  18. class TIfThenElse;
  19.  
  20. //----------------------------实例化
  21. template<typename Arg1st,
  22.          typename Arg2nd>
  23. class TIfThenElse<true, Arg1st, Arg2nd>
  24. {
  25. public:
  26.      typedef Arg1st ResultT;
  27. };
  28.  
  29. template<typename Arg1st,
  30.          typename Arg2nd>
  31. class TIfThenElse<false, Arg1st, Arg2nd>
  32. {
  33. public:
  34.      typedef Arg2nd ResultT;
  35. };
  36.  

     定义这个运算符的好处是，优化编译效率。像下面的情况：
 

  1. // 计算sqrt(N) 的主模板
  2. template <int N, int I=1>
  3. class Sqrt {
  4.   public:
  5.     enum { result = (I*I<N) ? Sqrt<N,I+1>::result
  6.                             : I };
  7. };
  8.  
  9. // 部分专门化 ， 递归出口
  10. template<int N>
  11. class Sqrt<N,N> {
  12.   public:
  13.     enum { result = N };
  14. };
  15.  

    这是取自 《C++ Template 》上例子的一段，是求平方根的。从下面的解析步骤中，我们可以看见一些缺点。
     

  1. // Step 1:
  2.  
  3. result = (1*1<4) ? Sqrt<4,2>::result
  4.                  : 1
  5.  
  6. // Step 2:
  7.  
  8. result = (1*1<4) ? (2*2<4) ? Sqrt<4,3>::result
  9.                            : 2
  10.                  : 1
  11.  
  12. // Step 3:
  13.  
  14. result = (1*1<4) ? (2*2<4) ? (3*3<4) ? Sqrt<4,4>::result
  15.                                      : 3
  16.                            : 2
  17.                  : 1
  18.  
  19. // Step 4:
  20.  
  21. result = (1*1<4) ? (2*2<4) ? (3*3<4) ? 4
  22.                                      : 3
  23.                            : 2
  24.                  : 1
  25.  
  26.  

     尽管我们已经在第2步中，算出了结构，但是编译器还在不停的展开计算后面的没有用的模板式。这无疑是一种资源的浪费。无论有无选择它，都会计算，效率会是O(N2),而自我定义一个编译时期的IfThenElse，则让编译器在编译期间就和运行期间的&&或||运算符一样，优化到点到为止，找到适合的就不再运算剩余的内容了，这样将编译效率提高到了O(logN).下面是一个改进版本：
 

  1. // template to yield template argument as result
  2. template<int N>
  3. class Value {
  4.   public:
  5.     enum { result = N };
  6. };
  7.  
  8. // 计算sqrt(N) 的主模板 
  9. template <int N, int I=1>
  10. class Sqrt {
  11.   public:
  12.  
  13.     // instantiate next step or result type as branch
  14.     typedef typename IfThenElse<(I*I<N),
  15.                                 Sqrt<N,I+1>,
  16.                                 Value<I>
  17.                                >::ResultT
  18.             SubT;
  19.  
  20.     // use the result of branch type
  21.     enum { result = SubT::result };
  22. };
  23.  

 

  • 无匹配
Small_feed 评论 (1)
1
[回复]
Avatar_small
jnanabhumiap. in 说:
2024年1月09日 20:11

The primary idea or goal of this website has been to offer comprehensive resources with information on any subject that can be accessed online. To make sure that every reader finds out what they should know about the subject they are interested in and jnanabhumiap.in links to our content.Jnanabhumi AP is a startup founded by enthusiastic bloggers and webmasters who are driven to produce interesting, factual, and well-written content. We are similar to an online community where you can find a variety of resources, information, and topics about newsworthy events or daily occurrences.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter