boost::mpl::list 源码分析

来源:互联网 时间:1970-01-01

使用 list 的方法如下:

[c-sharp] view plaincopy
  1. #include <iostream>  
  2. #include <boost/mpl/list/list10.hpp>  
  3. #include <boost/mpl/size.hpp>  
  4. using namespace boost;  
  5. using namespace std;  
  6. int _tmain(int argc, _TCHAR* argv[])  
  7. {     
  8.     typedef mpl::list3<int,double,int>::type r;  
  9.     cout<<mpl::size<r>::type::value<<endl;  
  10. }  

list3只能存放3个元素,如果要存放12(list12<...>)元素,那么头文件需要变成list20.hpp。

小于10等于10个元素都可以用头文件list10.hpp。

同时无需指定一个明确的值。比如:list<int,float,double...>等。同时相应的头文件也必须做出改变。

size函数求存放元素的个数。

 

这儿有两个版本的list(按生成方式的不同)。
一个是手工写成,另外一个依靠宏扩展而成。先讨论手工写成的list10.hpp。

[c-sharp] view plaincopy
  1. #include <boost/mpl/list/list10.hpp>   
包含的源码为:


[c-sharp] view plaincopy
  1. #if !defined(BOOST_MPL_PREPROCESSING_MODE)//如果没有定义这个宏,就包括下面这个文件。  
  2. #   include <boost/mpl/list/list0.hpp>//放在后面讨论  
  3. #endif  
  4. #include <boost/mpl/aux_/config/use_preprocessed.hpp>  
  5. 这个文件包括的源代码对宏BOOST_MPL_PREPROCESSING进行了定义,源码拷贝如下:  
  6. #ifndef BOOST_MPL_AUX_CONFIG_USE_PREPROCESSED_HPP_INCLUDED  
  7. #define BOOST_MPL_AUX_CONFIG_USE_PREPROCESSED_HPP_INCLUDED  
  8. // Copyright Aleksey Gurtovoy 2000-2004  
  9. //  
  10. // Distributed under the Boost Software License, Version 1.0.   
  11. // (See accompanying file LICENSE_1_0.txt or copy at   
  12. // http://www.boost.org/LICENSE_1_0.txt)  
  13. //  
  14. // See http://www.boost.org/libs/mpl for documentation.  
  15. // $Id: use_preprocessed.hpp 49267 2008-10-11 06:19:02Z agurtovoy $  
  16. // $Date: 2008-10-11 02:19:02 -0400 (Sat, 11 Oct 2008) $  
  17. // $Revision: 49267 $  
  18. #define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS //这句就是上面头文件的内容。  
  19. #endif // BOOST_MPL_AUX_CONFIG_USE_PREPROCESSED_HPP_INCLUDED  
  20. 这儿我们先讨论手工写成的代码,而不是依靠宏扩展而成的代码,因此可以把  
  21. 这个宏注释掉  
  22. #if !defined(BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS) /  
  23.     && !defined(BOOST_MPL_PREPROCESSING_MODE) //由于我们注释了这个宏,所以  
  24.                                               //包括下面两个文件。  
  25. #   define BOOST_MPL_PREPROCESSED_HEADER list10.hpp  
  26. #   include <boost/mpl/list/aux_/include_preprocessed.hpp>  
  27. //下面这个版本是宏生成版本,暂时不考虑。先考虑手工代码。   
  28. #else  
  29. #   include <boost/preprocessor/iterate.hpp>  
  30. namespace boost { namespace mpl {  
  31. #   define BOOST_PP_ITERATION_PARAMS_1 /  
  32.     (3,(1, 10, <boost/mpl/list/aux_/numbered.hpp>))  
  33. #   include BOOST_PP_ITERATE()  
  34. }}  
  35. #endif // BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS  
  36. #endif // BOOST_MPL_LIST_LIST10_HPP_INCLUDED  

这儿我们先讨论手工写成的代码,而不是依靠宏扩展而成的代码,因此可以把
上面那个BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS宏注释掉。

上面的include_preprocessed.hpp包含的源文件精简为:

[c-sharp] view plaincopy
  1. #   define AUX778076_HEADER /  
  2.     aux_/preprocessed/plain/BOOST_MPL_PREPROCESSED_HEADER /  
  3.     /**/  
  4.     #   include BOOST_PP_STRINGIZE(boost/mpl/list/AUX778076_HEADER)  

 

BOOST_PP_STRINGIZE 宏定义在文件
#include <boost/preprocessor/stringize.hpp>中(当前编译器MSVC9.0)

代码精简为:

[c-sharp] view plaincopy
  1. #    define BOOST_PP_STRINGIZE(text) BOOST_PP_STRINGIZE_A((text))  
  2. #    define BOOST_PP_STRINGIZE_A(arg) BOOST_PP_STRINGIZE_I arg  
  3. # define BOOST_PP_STRINGIZE_I(text) #text //#text扩展成"text"  

综上所述,

#include BOOST_PP_STRINGIZE(boost/mpl/list/AUX778076_HEADER)

全部展开为:
#include "boost/mpl/list/aux_/preprocessed/plain/list10.hpp"

下面分别举能存放一个元素,两个元素,三个元素的序列,其余的与此相似,不予讨论。
分别是list1、list2、list3。

[c-sharp] view plaincopy
  1. template<  
  2. typename T0  
  3. >  
  4. struct list1  
  5.     : l_item<  
  6.     long_<1>  //这个参数代表size,指示能存放一个元素。下面定义  
  7.     , T0      //这就是存放的那个元素。  
  8.     , l_end  
  9.     >  
  10. {  
  11.     typedef list1 type;   
  12. };  
  13. template<  
  14. typename T0, typename T1  
  15. >  
  16. struct list2  
  17.     : l_item<  
  18.     long_<2>//在下面定义。  
  19.     , T0  
  20.     , list1<T1>  
  21.     >  
  22. {  
  23.     typedef list2 type;  
  24. };  
  25. template<  
  26. typename T0, typename T1, typename T2  
  27. >  
  28. struct list3  
  29.     : l_item<  
  30.     long_<3>  
  31.     , T0  
  32.     , list2< T1,T2 >  
  33.     >  
  34. {  
  35.     typedef list3 type;  
  36. };  

上面的long_定义如下:

[c-sharp] view plaincopy
  1. //上面的long_定义如下:  
  2. template<long   N>  
  3. struct long_  
  4. {  
  5.     static   long value = N ; //当前的值  
  6.     typedef  long   type;       
  7.     typedef  long_  value_type;  
  8.     typedef integral_c_tag tag; //标记作用,在其他地方定义或是声明。  
  9.     typedef long_<static_cast<long>(value+1)> next; //假如当前为:long_<1>,下一个就是long_<2>  
  10.     typedef long_<static_cast<long>(value-1)> prior;//假如当前内容为:long_<1>,上一个就是long_<0>  
  11.     // enables uniform function call syntax for families of overloaded   
  12.     // functions that return objects of both arithmetic ('int', 'long',  
  13.     // 'double', etc.) and wrapped integral types (for an example, see   
  14.     // "mpl/example/power.cpp")  
  15.     //对“()”进行重载返回当前的值,用法为:long_<5>(),这个值就是5,同上面的vaule 代表一个意思。  
  16.     operator long() const { return static_cast<long>(this->value); }   
  17. };  
  18. //static要在类外面定义。enum就不需要。  
  19. template<long N>  
  20. long long_<N>::value;  

基类l_item如下:

[c-sharp] view plaincopy
  1. struct list_tag; //作为标记  
  2. //l_item的定义如下:  
  3. template<  
  4.   typename Size //如果存放一个元素,从上面看来应该是long_<1>,两个是long_<2>  
  5. , typename T      
  6. , typename Next  
  7. >  
  8. struct l_item  
  9. {  
  10.     // agurt, 17/jul/03: to facilitate the deficient 'is_sequence' implementation   
  11. #if BOOST_WORKAROUND(BOOST_MSVC, <= 1300)//vc7.0 版本   
  12.     typedef int begin;  //vc7才用这个版本  
  13. #endif  
  14.     typedef aux::list_tag tag;//aux是名词空间,list_tag在aux里面.  
  15.     typedef l_item type;  
  16.     typedef Size size;//list3对应long_<3>,list2对应long_<2>,list1对应long_<1>  
  17.     typedef T item;  //当前的元素  
  18.     typedef Next next; //下一个节点.list3的下一个节点是list2, list2 的下一个节点是list1.  
  19. };  

比较 mpl::vector和mpl::list的结构就可以看出:

因为这是元编程,运行都是O(1)时间,区别在于编译时间的不同。

这儿的编译时间和运行时时间的复杂度还是有区别的。只是用类似于运行时的时间复杂度来

衡量。在编译的时候,vector可以很随便的访问类中的任何一个元素,因为其中一种vector

的实现方式,实际是把每一个元素都写在了结构里面:item0,item1,item2,item3.....

而list则不同,list在访问首元素和尾元素倒是很快的。但是如果是中间的元素呢?只能通过迭代器来遍历,

这就像链表一样,一个节点一个节点的遍历。当然就是线性时间复杂度了:O(n)

迭代器 :

[c-sharp] view plaincopy
  1. struct l_end  //这个类起一个结束的标记作用。  
  2. {  
  3. #if BOOST_WORKAROUND(BOOST_MSVC, <= 1300)//vc7.0 版本  
  4.     typedef int begin;  
  5. #endif  
  6.     typedef aux::list_tag tag;  
  7.     typedef l_end type;  
  8.     typedef long_<0> size;  
  9. };  
  10. struct l_iter_tag;//迭代器的标记  
  11. //迭代器标志。int_同long_一样。只是在long的地方用int来替换。  
  12. struct forward_iterator_tag   : int_<0> { typedef forward_iterator_tag type; };  

以上就是list的内容。下面讨论begin 和end 这两个迭代器对list是怎样实现的:

[c-sharp] view plaincopy
  1. /* 
  2.   
  3.  begin<l>::type 
  4. 下面讨论begin算法怎样实习取元素的。 
  5. */  
  6. template<  
  7. typename BOOST_MPL_AUX_NA_PARAM(Sequence)  
  8. >  
  9. struct begin  
  10. {                    //sequence_tag这是一个标记.  
  11.     typedef typename sequence_tag<Sequence>::type tag_;  
  12.     typedef typename begin_impl< tag_ > //在下面定义。  
  13.         ::template apply< Sequence >::type type;  
  14.     BOOST_MPL_AUX_LAMBDA_SUPPORT(1,begin,(Sequence))  
  15. };  
  16. template<>  
  17. struct begin_impl< aux::list_tag >  
  18. {  
  19.     template< typename List > struct apply //模板参数是list  
  20.     {           //从下面可以看出l_iter定义里面并没有什么,关键信息是:List::type  
  21.         typedef l_iter<typename List::type> type;   
  22.     };  
  23. };  
  24. /* 
  25.  end<l>::type 指向 list 尾部的迭代器 
  26. */  
  27. template<  
  28. typename BOOST_MPL_AUX_NA_PARAM(Sequence) // typename Sequence  
  29. >  
  30. struct end  
  31. {  
  32.     typedef typename sequence_tag<Sequence>::type tag_; //   
  33.     typedef typename end_impl< tag_ >         //end_impl全特化代码在下面。  
  34.         ::template apply< Sequence >::type type;  
  35.     BOOST_MPL_AUX_LAMBDA_SUPPORT(1,end,(Sequence))  
  36. };  
  37. template<>  
  38. struct end_impl< aux::list_tag >  
  39. {  
  40.     template< typename > struct apply  
  41.     {  
  42.         typedef l_iter<l_end> type; //最后还是以l_end作为迭代器的参数。  
  43.     };  
  44. };  
  45. //l_iter迭代调用如下, 最后 end<l>::type返回 l_iter<l_end>迭代器。  
  46. template< typename Node >  
  47. struct l_iter  
  48. {  
  49.     typedef aux::l_iter_tag tag;  
  50.     typedef forward_iterator_tag category;  
  51. };  

size(list) 算法:

size类源代码为:

[c-sharp] view plaincopy
  1. template<  
  2.     typename BOOST_MPL_AUX_NA_PARAM(Sequence)  
  3. >  
  4. struct size  
  5.     : aux::msvc_eti_base<  
  6.     typename size_impl< typename sequence_tag<Sequence>::type >  
  7.     ::template apply< Sequence >::type  
  8.     >::type  
  9. {  
  10.   
  11. };  

size 继承 msvc_eti_base 类模板,

msvc_eti_base的源代码为:

[c-sharp] view plaincopy
  1. template< typename T > struct msvc_eti_base  
  2.         : T  
  3.     {  
  4.         typedef T type;  
  5.     };  

它继承模板参数,并以模板参数为type.

因此现在来看模板参数是什么:

[c-sharp] view plaincopy
  1. template<>  
  2. struct size_impl< aux::list_tag >  
  3. {  
  4.     template< typename List > struct apply  
  5.         : List::size  
  6.     {  
  7.     };  
  8. };  

size_impl的内嵌模板类apply,并没有type,但是上面的代码:

[c-sharp] view plaincopy
  1. ::template apply< Sequence >::type  

表明有type.这就是apply为什么要继承模板参数的原因,它可以访问基类的成员type。

这个type实际就是list。而获得了list这个类型就很容易的访问类里面的成员了。如果是

list3, 那么就可以访问size,而这儿的size就是long_<3>,对它求值long_<3>() = 3。

下面来看看list的tag(上面用到了):

[c-sharp] view plaincopy
  1. template<  
  2. typename BOOST_MPL_AUX_NA_PARAM(Sequence)  
  3. >  
  4. struct sequence_tag  
  5.     : aux::sequence_tag_impl<  
  6.     ::boost::mpl::aux::has_tag<Sequence>::value  
  7.     , ::boost::mpl::aux::has_begin<Sequence>::value  
  8.         >::template result2_<Sequence>  
  9. {  
  10. };  

 它是继承sequence_tag_impl

[c-sharp] view plaincopy
  1. template< bool has_tag_, bool has_begin_ >  
  2. struct sequence_tag_impl  
  3. {  
  4.     // agurt 24/nov/02: MSVC 6.5 gets confused in 'sequence_tag_impl<true>'   
  5.     // specialization below, if we name it 'result_' here  
  6.     template< typename Sequence > struct result2_;  
  7. };  
  8. #   define AUX_CLASS_SEQUENCE_TAG_SPEC(has_tag, has_begin, result_type) /  
  9.     template<> struct sequence_tag_impl<has_tag,has_begin> /  
  10. { /  
  11.     template< typename Sequence > struct result2_ /  
  12. { /  
  13.     typedef result_type type; /  
  14. }; /  
  15. }; /  
  16.     /**/  
  17. AUX_CLASS_SEQUENCE_TAG_SPEC(true, true, typename Sequence::tag)  
  18. 这个宏推出以下的代码:  
  19. template<> struct sequence_tag_impl<true,true>  
  20. {  
  21.     template<typename Sequence> struct result2_  
  22.     {  
  23.      typedef Sequence::tag type;  
  24.     };  
  25. };  
  26. AUX_CLASS_SEQUENCE_TAG_SPEC(true, false, typename Sequence::tag)  
  27. 上面的宏推出:  
  28. template<> struct sequence_tag_impl<true,false>  
  29. {  
  30.     template<typename Sequence> struct result2_  
  31.     {  
  32.         typedef Sequence::tag type;  
  33.     };  
  34. };  

has_tag必须成功,才能得到正确的类型。它获得标记就是list的tag。

has_tag是由一个宏来实现的:

[c-sharp] view plaincopy
  1. #define BOOST_MPL_HAS_XXX_TRAIT_DEF(name) /  
  2.     BOOST_MPL_HAS_XXX_TRAIT_NAMED_DEF(BOOST_PP_CAT(has_,name), name, false) /  

宏定义代码:

[c-sharp] view plaincopy
  1. #   elif BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1400)) /  
  2.     || BOOST_WORKAROUND(__IBMCPP__, <= 700)  
  3. // MSVC 7.1+ & VACPP  
  4. // agurt, 15/jun/05: replace overload-based SFINAE implementation with SFINAE  
  5. // applied to partial specialization to fix some apparently random failures   
  6. // (thanks to Daniel Wallin for researching this!)  
  7. #   define BOOST_MPL_HAS_XXX_TRAIT_NAMED_DEF(trait, name, default_) /  
  8.     template< typename T > /  
  9. struct BOOST_PP_CAT(trait, _msvc_sfinae_helper) /  
  10. { /  
  11.     typedef void type; /  
  12. };/  
  13.     /  
  14.     template< typename T, typename U = void > /  
  15. struct BOOST_PP_CAT(trait,_impl_) /  
  16. { /  
  17.     BOOST_STATIC_CONSTANT(bool, value = false); /  
  18.     typedef boost::mpl::bool_<value> type; /  
  19. }; /  
  20.     /  
  21.     template< typename T > /  
  22. struct BOOST_PP_CAT(trait,_impl_)< /  
  23.     T /  
  24.     , typename BOOST_PP_CAT(trait, _msvc_sfinae_helper)< typename T::name >::type /  
  25. > /  
  26. { /  
  27.     BOOST_STATIC_CONSTANT(bool, value = true); /  
  28.     typedef boost::mpl::bool_<value> type; /  
  29. }; /  
  30.     /  
  31.     template< typename T, typename fallback_ = boost::mpl::bool_<default_> > /  
  32. struct trait /  
  33.     : BOOST_PP_CAT(trait,_impl_)<T> /  
  34. { /  
  35. }; /  
  36.     /**/  

经过推导以后为:

[c-sharp] view plaincopy
  1. template<typename T>  
  2. struct has_tag__msvc_sfinae_helper  
  3. {  
  4.    typedef void type;  
  5. };  
  6. template< typename T, typename U = void >   
  7. struct has_tag_impl_  
  8. {   
  9.   BOOST_STATIC_CONSTANT(bool, value = false); //bool static value = false;  
  10.   typedef boost::mpl::bool_<value> type;   
  11. };  
  12. template< typename T >   
  13. struct has_tag_impl_<   
  14.     T   
  15.     , typename has_tag__msvc_sfinae_helper< typename T::name >::type  
  16. >   
  17. {   
  18. BOOST_STATIC_CONSTANT(bool, value = true);   
  19. typedef boost::mpl::bool_<value> type;   
  20. };   
  21. template< typename T, typename fallback_ = boost::mpl::bool_<default_> >   
  22. struct trait   
  23.     : has_tag_impl_<T>   
  24. {   
  25. };   

上面的mpl::bool_的代码为:

[c-sharp] view plaincopy
  1. template< bool C_ > struct bool_  
  2. {  
  3.     BOOST_STATIC_CONSTANT(bool, value = C_);  
  4.     typedef integral_c_tag tag;  
  5.     typedef bool_ type;  
  6.     typedef bool value_type;  
  7.     operator bool() const { return this->value; }  
  8. };  

实际上就是指如果这个序列有tag标记就返回true,即使这个序列没有元素值仍然返回正确的

值:

[c-sharp] view plaincopy
  1. AUX_CLASS_SEQUENCE_TAG_SPEC(true, true, typename Sequence::tag)//list在这种情况下,正确  
  2. AUX_CLASS_SEQUENCE_TAG_SPEC(true, false, typename Sequence::tag)//list, true  
  3. AUX_CLASS_SEQUENCE_TAG_SPEC(false, true, nested_begin_end_tag)//list, false  
  4. AUX_CLASS_SEQUENCE_TAG_SPEC(false, false, non_sequence_tag)//list, false  

上面已经讨论了这些代码。


上面来自:http://blog.csdn.net/yshuise/article/details/4285337


相关阅读:
Top