注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

一路

To find the final symmetry & beauty

 
 
 

日志

 
 
 
 

SGI STL源码阅读笔记7 类型萃取[原创]  

2011-02-16 20:06:05|  分类: c++学习笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

在前面的日志中我已经简单介绍了traits的实现方法。但是并没有详细介绍为什么要使用这个技术,多了其中一个间接层有什么好处。

考虑这样的一个应用,我们要交换两个迭代器所指的变量,那么很容器我们可以写出下面的代码

但是这份代码要求我的输入的迭代器必有一个内嵌类型value_type,这个要求对于以类的方式表示的迭代器是没有问题的,但是系统的原生指针也是迭代器,它们做为原始类型根本没有这个内嵌类型定义,我们可以在个问题上再引入一个间接层。关于这个问题我已经在我以前的日志中有介绍,这里不再详细介绍。我直接给出代码

Traits模版类有如下定义

它利用模板类的偏特化特性对所有的原生指针进行了包装,这样我们调用上面的使用traits的代码就没有问题了。但是我们可能有这样的需求,如果我们要求换的类型,也就是迭代器所指的类型如果是类类型,而且这个类很大,比如它是一个装满很多元素的容器,我们通过这个交换函数中的复制一个临时容器的方法进行交换代价就太大了。我们知道容器类与自己相同类型的容器类型有着十分快速的交换方法,这种交换只是交换容器内部的指针而已,如果我们可以让函数识别出这类的类型,自己调用高效的交换函数将是一个十分有成就的工作。这里我们就可以用到traits的偏特化了,考虑如下的完整例子。

 

//filename: traits_example.cpp

//written by saturnman

#include<iostream>

#include<vector> //for vector

#include<algorithm>//for copy

#include<iterator>//for ostream_iterator

#include<deque>

#include<memory>

#include"tracer.h"

using namespace std;

//utility classes

class __normal_category

{

    public:

};

class __vector_category

{

    public:

};

template<typename T>

class Iterator_Traits

{

    public:

    typedef __normal_category iterator_type;

};

template<typename T>

class Iterator_Traits<vector<T,allocator<T> > >

{

    public:

    typedef __vector_category iterator_type;

};

template<typename Iterator>

inline void swap1(Iterator iter1,Iterator iter2)

{

    //slow swap technique

    typename Iterator::value_type tmp = *iter1;

    *iter1 = *iter2;

    *iter2 = tmp;

}

template<typename Iterator>

inline void swap2(Iterator iter1,Iterator iter2)

{

    typedef typename Iterator_Traits<typename Iterator::value_type>::iterator_type iterator_type;

    _swap(iter1,iter2,iterator_type());

}

template<typename Iterator>

inline void _swap(Iterator iter1,Iterator iter2,__normal_category)

{

    //slow swap technique

    typename Iterator::value_type tmp = *iter1;

    *iter1 = *iter2;

    *iter2 = tmp;

}

template<typename Iterator>

inline void _swap(Iterator iter1,Iterator iter2,__vector_category)

{

    iter1->swap(*iter2);

    //use fast swap technique;

}

template<typename T>

void print_vector_vector(vector<T> &input)

{

    for(typename vector<T>::iterator itor = input.begin();itor!=input.end();++itor)

    {

        copy(itor->begin(),itor->end(),ostream_iterator<typename T::value_type>(cout," "));

        cout<<endl;

    }

}

int main()

{

    Tracer::set_noise(false);

    //don't print extra information

    vector<Tracer> arr1;

    vector<Tracer> arr2;

    deque<Tracer> que1;

    deque<Tracer> que2;

    for(int i=0;i<10;++i)

    {

        arr1.push_back(Tracer(2*i));

        arr2.push_back(Tracer(2*i-1));

        que1.push_back(Tracer(2*i));

        que1.push_back(Tracer(2*i-1));

    }

    vector<vector<Tracer> > arr_arr1;

    vector<deque<Tracer> > arr_arr2;

    arr_arr1.push_back(arr1);

    arr_arr1.push_back(arr2);

    arr_arr2.push_back(que1);

    arr_arr2.push_back(que2);

    //cout<<"before swap."<<endl;

    //print_vector_vector(arr_arr1);

    cout<<"before swap1 on vector iterator."<<endl;

    Tracer::report();

    swap1(arr_arr1.begin(),arr_arr1.begin()+1);

    cout<<"after swap1 on vector iterator."<<endl;

    Tracer::report();

    cout<<"before swap2 on vector iterator."<<endl;

    Tracer::report();

    swap2(arr_arr1.begin(),arr_arr1.begin()+1);

    cout<<"after swap2 on vector iterator."<<endl;

    Tracer::report();

    cout<<"before swap1 on deque iterator."<<endl;

    Tracer::report();

    swap1(arr_arr2.begin(),arr_arr2.begin()+1);

    cout<<"after swap1 on deque iterator."<<endl;

    Tracer::report();

    cout<<"before swap2 on deque iterator."<<endl;

    Tracer::report();

    swap2(arr_arr2.begin(),arr_arr2.begin()+1);

    cout<<"after swap2 on deque Iterator."<<endl;

    Tracer::report();

    print_vector_vector(arr_arr2);

    return 0;  

}

 

代码有些乱,我们来看一下做了什么。我用到了前面提到的Tracer类,这里它的代码我加了改进,我会把代码附在本文最后,使用它可以检测函数的行为。我定义了两个swap函数,swap1和swap2,它们的参数是一样的,其中swap1是直接使用没有任何条件判断的交换方式对迭代器指向的内容进行交换。而swap2则使用了traits技术,如果发现迭代器是指向一个vector容器类型,则就会调用高效的容器成员函数来完成交换工作,这个工作写在_swap工具函数中。如果发现不是vector容器就用原始的复制容器的方式进行交换,这里它对deque的交换方式就是这样的(注:deque当然也有高效的交换成员函数,我们这里只是为了说明traits技术特点,就当它没有这个高效函数好了。)

Arr_arr1内装的是vector 容器,arr_arr2内装的是deque容器,其中所有容器的内部类型都是Tracer类。注意我上面用到两个工个工具类,__normal_category和__vector_category,它们是空类。只是为了用来触发重载函数的调用,_swap是重载函数,如果第三个参数是__normal_category类型就调用常规交换函数,如果是__vector_category就调用快速交换的成员函数。对于Iterator_Traits类,一般情况我设定它的内部类型iterator_type是__normal_category,但是我后面做了一个偏特化,如果以vector类为参数来声名这个类就把它的iterator_type类部类型设定为__vector_category,经过这一番工作后我们只要在swap2中直接用Iterator_Traits萃取出类型,放入工具函数的第三个参数,编译器会自己调用正确的函数,如果是迭代器指向vector容器,就会调用快速交换的_swap函数。如上所述就实现了所谓的traits技术,但是注意,萃取技术不单可以萃取一个类型,它是可以萃取多个类型的,比如标准库中就有pointer_type,value_type等等。

下面是程序的运行结果:

before swap1 on vector iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 180 instances created.

*****end*****

after swap1 on vector iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 190 instances created. 可以看出慢速的交换生成了十个临时对象

*****end*****

before swap2 on vector iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 190 instances created.

*****end*****

after swap2 on vector iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 190 instances created. 快速交换没有生成任何临时对象

*****end*****

before swap1 on deque iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 190 instances created.

*****end*****

after swap1 on deque iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 230 instances created. 不是vector类型,只能慢速交换,使用了40个临时对象

*****end*****

before swap2 on deque iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 230 instances created.

*****end*****

after swap2 on deque Iterator.

*****start*****

Now there are 80 instances exist.

There are maximum 100 instances exist.

Totally 250 instances created. 慢速交换,使用了20个临时对象,

*****end*****
(注:为什么同是慢速交换,而使用的容器也相同,交换方法也相同,有什么前一个用的临时对象比后一个多呢,这是因为deque在两部分的容量扩增引起的)

下面是Tracer类全部源码

//filename: tracer.h

//written by saturnman

#include<iostream>

using namespace std;

#ifndef _TRACER_H_

#define _TRACER_H_

class Tracer

{

    public:

        Tracer(int value)

        {

            this->value = value;

            ++s_NoOfInstances;

            ++s_TotalInstancesCreated;

            if(s_MaxNoOfInstances<s_NoOfInstances)

            {

                s_MaxNoOfInstances = s_NoOfInstances;

            }

            m_instanceID = s_TotalInstancesCreated;

            if(s_Noise==true)

            {

            cout<<"Constructor called to create instance "<<m_instanceID<<endl;

            }

        }

        Tracer(Tracer const& rhs)

        {

            //not really copy it

            ++s_NoOfInstances;

            ++s_TotalInstancesCreated;

            if(s_MaxNoOfInstances<s_NoOfInstances)

            {

                s_MaxNoOfInstances = s_NoOfInstances;

            }

            m_instanceID = s_TotalInstancesCreated;

            this->value = rhs.value;

            if(s_Noise==true)

            {

            cout<<"Copy Constructor called to create instance "<<m_instanceID<<endl;

            }

        }

        static void report()

        {

            cout<<"*****start*****"<<endl;

            cout<<"Now there are "<<s_NoOfInstances<<" instances exist."<<endl;

            cout<<"There are maximum "<<s_MaxNoOfInstances<<" instances exist."<<endl;

            cout<<"Totally "<<s_TotalInstancesCreated<<" instances created."<<endl;

            cout<<"*****end*****"<<endl;

        }

        static void set_noise(bool input)

        {

            s_Noise = input;

        }

        friend ostream& operator<<(ostream& out,const Tracer& input)

        {

            out<<input.value;

            return out;

        }

        Tracer& operator=(Tracer const& rhs)

        {

            if(s_Noise==true)

            {

            cout<<"Assignment operator called."<<endl;

            }

            this->value = rhs.value;

        }

        void Info()

        {

            cout<<"This is instance ID:"<<m_instanceID<<endl;

        }

        ~Tracer()

        {

            --s_NoOfInstances;

            if(s_Noise==true)

            {

            cout<<"dtor called to destruct "<<m_instanceID<<endl;

            }

        }

    private:

        int value;

        int m_instanceID;

        static int s_NoOfInstances;

        static int s_MaxNoOfInstances;

        static int s_TotalInstancesCreated;

        static bool s_Noise;

};

int Tracer::s_NoOfInstances = 0;

int Tracer::s_MaxNoOfInstances = 0;

int Tracer::s_TotalInstancesCreated = 0;

bool Tracer::s_Noise = true;

#endif /*_TRACER_H_*/

 


Ref:

[1]. 侯捷<<STL源码剖析>>

[2]. <<C++ Template Metaprogramming: Concepts,Tools, and Techniques from Boost and Beyond>>By David Abrahams, Aleksey Gurtovoy.

  评论这张
 
阅读(1240)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017