旷野的呼声

路漫漫其修远兮 吾将上下而求索

常用链接

统计

最新评论

【原创】boost.compressed_pair源码剖析

boost.compressed_pair源码剖析

意义

compressed_pair的某一个模板参数为一个空类的时候将对其进行“空基类优化”,这样可以使得compressed_pair占用的空间比std::pair的更小。

参考如下代码:

#include <iostream>

using namespace std;

 

#include <boost/compressed_pair.hpp>

 

class A{};

class B{};

 

int main()

{

   cout<< sizeof( std::pair< A, B > ) << endl;

 

   cout<< sizeof( boost::compressed_pair< A, B > ) << endl;

 

   return 0;

}

在我的机器上,VC2008 SP1输出21

 

std::pair参考

std::pair被实现为一个结构体,其中VC2008 SP1pair被实现为如下:

template<class _Ty1, class _Ty2>

   struct pair

   {  // store a pair of values

   typedef pair<_Ty1, _Ty2> _Myt;

   typedef _Ty1 first_type;

   typedef _Ty2 second_type;

 

   pair()

      : first(_Ty1()), second(_Ty2())

      {  // construct from defaults

      }

 

   pair(const _Ty1& _Val1, const _Ty2& _Val2)

      : first(_Val1), second(_Val2)

      {  // construct from specified values

      }

 

   template<class _Other1,

      class _Other2>

      pair(const pair<_Other1, _Other2>& _Right)

      : first(_Right.first), second(_Right.second)

      {  // construct from compatible pair

      }

 

   // 删除了一些不重要的代码

 

   _Ty1 first; // the first stored value

   _Ty2 second; // the second stored value

};

通过直接访问firstsecond对数据进行访问。

 

boost.compressed_pair参考

boost.compressed_pair大概的实现如下:

 

class compressed_pair

{

public:

   typedef T                                                  first_type;

   typedef T                                                  second_type;

   typedef typename call_traits<first_type>::param_type       first_param_type;

   typedef typename call_traits<second_type>::param_type      second_param_type;

   typedef typename call_traits<first_type>::reference        first_reference;

   typedef typename call_traits<second_type>::reference       second_reference;

   typedef typename call_traits<first_type>::const_reference  first_const_reference;

   typedef typename call_traits<second_type>::const_reference second_const_reference;

 

   first_reference       first()       {return base::first();}

   first_const_reference first() const {return base::first();}

 

   second_reference       second()       {return base::second();}

   second_const_reference second() const {return base::second();}

 

   void swap(::boost::compressed_pair<T,T>& y) { base::swap(y); }

};

 

注意这不是完整的代码,它只是对其实现的一个简单描述。从中我们可以看出boost.compressed_pair使用成员函数来访问数据而不是如std::pair一样直接访问firstsecond

 

boost.compressed_pair剖析

    boost.compressed_pair的实现依赖于boost.type_traitsboost.call_traitsboost.type_traitsboost提供的一个特征类库,这是一个强大的库,可以应用于很多地方。boost的大量组件都依赖于它。boost.call_traits也是一个类似于type_traits的库,它主要提供的是一些类型调整,通过编译器演绎我们可以在编译时得到最好的type,它可以使我们的传递的参数等等相关内容总是以最恰当(根据经验)的方式来进行调用,而且还能在新的C++标准发布之前绕过“引用的引用”问题。

接下来我将剖析支持偏特化版本的compressed_pair的实现,它位于boost\detail\compressed_pair.hpp

 

compressed_pair_switch

这是一个开关工具,用于在后面对各种情况进行开关控制,它的基本实现如下:

template <class T1, class T2, bool IsSame, bool FirstEmpty, bool SecondEmpty>

   struct compressed_pair_switch;

注意,它只是定义而非实现,因此我们无法构造未特化过的compressed_pair_switch。通过查看它的模板参数可以知道后面三个bool代表了三个概念:

l  pair的两个模板参数是否是相同类型。(去掉cv限定符之后)。

l  第一个模板参数是空的吗?

l  第二个模板参数是空的吗?

因此对这三个bool进行有限组合可以得到6种组合,也就出现了接下来我们所看到的6个特化(偏特化)。

template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, false, false>

      {static const int value = 0;};

 

   template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, true, true>

      {static const int value = 3;};

 

   template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, true, false>

      {static const int value = 1;};

 

   template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, false, true>

      {static const int value = 2;};

 

   template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, true, true, true>

      {static const int value = 4;};

 

   template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, true, false, false>

      {static const int value = 5;};

现在我们已经偏特化了6个不同的开关,它们将在最终实现compressed_pair的过程中发挥巨大的作用。注意每个类中的value,这个常量值代表了它的版本。

 

compressed_pair_imp

它作为最终compressed_pair的基类存在,它的声明如下:

template <class T1, class T2, int Version> class compressed_pair_imp;

注意第三个参数Version,在最终的实现中它将被以compressed_pair_switch::value来具现化。

接下来按照compressed_pair_switch6种版本所说明的6中组合情况分别实现其对应的compressed_pair_imp。在文章最开始的时候我们的简单程序发现std::pair由于直接采用组合T1T2而无法使之成功的应用“空基类优化”,使得其占用空间的大小是2.如果compressed_pair_imp也直接按照这种组合来实现的话,那么所谓“压缩”便不会有任何意义。所以compressed_pair_imp对应不同组合情况有不同的实现,比如说对于版本1

template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, true, false>

      {static const int value = 1;};

这种情况便是指T1T2在去cv限定符之后为不同类型,且第一种类型为空,第二种不为空,那么这时候在实现compressed_pair_imp的时候便取消了T1的数据,源码如下:

template <class T1, class T2>

   class compressed_pair_imp<T1, T2, 1>

      : protected ::boost::remove_cv<T1>::type

   {

   public:

      typedef T1                                                 first_type;

      typedef T2                                                 second_type;

      typedef typename call_traits<first_type>::param_type       first_param_type;

      typedef typename call_traits<second_type>::param_type      second_param_type;

      typedef typename call_traits<first_type>::reference        first_reference;

      typedef typename call_traits<second_type>::reference       second_reference;

      typedef typename call_traits<first_type>::const_reference  first_const_reference;

      typedef typename call_traits<second_type>::const_reference second_const_reference;

 

      compressed_pair_imp() {}

 

      compressed_pair_imp(first_param_type x, second_param_type y)

         : first_type(x), second_(y) {}

 

      compressed_pair_imp(first_param_type x)

         : first_type(x) {}

 

      compressed_pair_imp(second_param_type y)

         : second_(y) {}

 

      first_reference       first()       {return *this;}

      first_const_reference first() const {return *this;}

 

      second_reference       second()       {return second_;}

      second_const_reference second() const {return second_;}

   private:

      second_type second_;

};

 

      现在回过头去,对于版本0

template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, false, false>

      {static const int value = 0;};

     由于T1t2为不同类型,同时都不为空,因此这种情况下compressed_pairstd::pair是一样的。

 

     对于版本2

template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, false, true>

      {static const int value = 2;};

      T1T2不相同,且T1不为空,T2为空,那么这和版本1的差别就在于t2的数据成员被取消,T1的数据成员存在。

template <class T1, class T2>

   class compressed_pair_imp<T1, T2, 2>

      : protected ::boost::remove_cv<T2>::type

   {

      first_reference       first()       {return first_;}

      first_const_reference first() const {return first_;}

 

      second_reference       second()       {return *this;}

      second_const_reference second() const {return *this;}

 

   private:

      first_type first_;

   };  // 删除了某系无关紧要的代码

     

      版本3

template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, true, true>

      {static const int value = 3;};

     T1t2不相同,且两者均为空。这种时候compressd_pair_imp不再需要任何数据成员,因此其精简版的定义如下:

template <class T1, class T2>

   class compressed_pair_imp<T1, T2, 3>

      : protected ::boost::remove_cv<T1>::type,

        protected ::boost::remove_cv<T2>::type

   {

      first_reference       first()       {return *this;}

      first_const_reference first() const {return *this;}

 

      second_reference       second()       {return *this;}

      second_const_reference second() const {return *this;}

      //

      // no need to swap empty bases:

      void swap(::boost::compressed_pair<T1,T2>&) {}

   };

     在这里面我们可以看到它的交换动作根本什么也没做。而且也没有数据成员,但是其占用空间大小依然是1.

 

版本4定义了T1T2相同,且均为空的特殊情况:

template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, true, true, true>

      {static const int value = 4;};

   template <class T1, class T2>

   class compressed_pair_imp<T1, T2, 4>

      : protected ::boost::remove_cv<T1>::type

   {

      first_reference       first()       {return *this;}

      first_const_reference first() const {return *this;}

 

      second_reference       second()       {return m_second;}

      second_const_reference second() const {return m_second;}

 

      void swap(::boost::compressed_pair<T1,T2>&) {}

   private:

      T2 m_second;

   };

     既然T1T2均为空,那么为何还要保存一个T2的数据呢?这是为了防止first()second()所返回的对象的地址相同,这是很郁闷的一件事情。

版本5定义了T1T2相同,且均不为空的情况:

template <class T1, class T2>

   class compressed_pair_imp<T1, T2, 5>

   {

      first_reference       first()       {return first_;}

      first_const_reference first() const {return first_;}

 

      second_reference       second()       {return second_;}

      second_const_reference second() const {return second_;}

 

      void swap(::boost::compressed_pair<T1, T2>& y)

      {

         cp_swap(first_, y.first());

         cp_swap(second_, y.second());

      }

   private:

      first_type first_;

      second_type second_;

};

     这个版本并没有什么特殊之处。

 

compressed_pair

     最终的实现通过继承compressed_pair_imp来实现,而上述的compressed_pair_imp都有一个Version模板参数,通过编译时推断出的compressed_pair_switch的数据value则可得到与其对应的基类。

template <class T1, class T2>

class compressed_pair

   : private ::boost::details::compressed_pair_imp<T1, T2,

             ::boost::details::compressed_pair_switch<

                    T1,

                    T2,

                    ::boost::is_same<typename remove_cv<T1>::type, typename remove_cv<T2>::type>::value,

                    ::boost::is_empty<T1>::value,

                    ::boost::is_empty<T2>::value>::value>

 

template <class T>

class compressed_pair<T, T>

   : private details::compressed_pair_imp<T, T,

             ::boost::details::compressed_pair_switch<

                    T,

                    T,

                    ::boost::is_same<typename remove_cv<T>::type, typename remove_cv<T>::type>::value,

                    ::boost::is_empty<T>::value,

                    ::boost::is_empty<T>::value>::value>

 

      这是按照T1T2是否相同所不同的实现。它们的区别主要在构造函数的实现上:

explicit compressed_pair(first_param_type x) : base(x) {}

    explicit compressed_pair(second_param_type y) : base(y) {}

    对于T1T2相同的情况,上面的这段代码不是合法的重载。

 

    ::boost::is_same将对T1T2cv限定符之后的类型进行比较,结果value是一个bool值常量,对应于compressed_pair_switch第三个模板参数。::boost::is_empty可以判断类型是否是空类型,其值value也是一个bool值常量。这样便可推断出该继承哪一个版本的compressed_pair_imp

 

其它重点

     这里将继续探讨一些有意义的技巧。

 

继承

     在这里我们将聚焦compressed_pair_imp的实现,其中除了第0版本和第5版本之外,其它的实现均不同程度的使用了继承,比如第1版:

template <class T1, class T2>

   class compressed_pair_imp<T1, T2, 1>

      : protected ::boost::remove_cv<T1>::type

这个版本是:

template <class T1, class T2>

   struct compressed_pair_switch<T1, T2, false, true, false>

      {static const int value = 1;};

T1T2不同,且只有T1为空,那么它继承去cv限定符之后的T1类型。它的意义何在呢?

参考第1版本的compressed_pair_imp的实现可以看到:

first_reference       first()       {return *this;}

      first_const_reference first() const {return *this;}

当需求要T1的类型对象的时候,直接返回的是compressed_pair_imp对象自己,如果不继承的话这个动作将是非法的。这就是为什么有这样一个继承的原因。

对于版本3

template <class T1, class T2>

   class compressed_pair_imp<T1, T2, 3>

      : protected ::boost::remove_cv<T1>::type,

        protected ::boost::remove_cv<T2>::type

还可以看到:

first_reference       first()       {return *this;}

      first_const_reference first() const {return *this;}

 

      second_reference       second()       {return *this;}

      second_const_reference second() const {return *this;}

实际上道理是一样的。同时它还解决了构造函数中的这个问题:

compressed_pair_imp(first_param_type x, second_param_type y)

         : first_type(x), second_type(y) {}

因为first_typesecond_type为其基类,这样的调用才合法。

还有一个猜想就是如果T1是内置类型的话,比如说int,那么继承int会是合法的代码吗?实际上我们并不需要担心这个,因为int不会通过::boost::is_empty测试。boost::is_empty<int>::value将得到false,因此不会被编译器演绎到这一步。

 

 

        [本文原创]相关连接:
1. 本文的Word工整版:http://ishare.iask.sina.com.cn/f/5144299.html
2. 关于空基类优化:http://user.qzone.qq.com/84638372/blog/1242484131

posted on 2009-05-18 11:09 董波 阅读(1120) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理