网站建设全包哪家便宜,flashfxp上传了网站,长沙网站开发 58,江阴做网站的地方本文从三方面总结迭代器 迭代器的思想迭代器相应型别及traits思想__type_traits思想一 迭代器思想 迭代器的主要思想源于迭代器模式#xff0c;其定义如下#xff1a;提供一种方法#xff0c;使之能够依序巡防某个聚合物#xff08;容 器#xff09;所含的元素#xff0c… 本文从三方面总结迭代器 迭代器的思想 迭代器相应型别及traits思想 __type_traits思想 一 迭代器思想 迭代器的主要思想源于迭代器模式其定义如下提供一种方法使之能够依序巡防某个聚合物容 器所含的元素而又无需暴露该聚合物的内部表达式。可见她的主要作用便是能够降低耦合提高代码的 模块性。 STL的的中心思想在于将数据容器和算法分开彼此独立设计最后再以一贴胶着剂将它们撮合 在一起这贴胶着剂便是迭代器。迭代器的行为类似智能指针例如标准库的auto_ptr和boost库的shared _ptr换句话说它重载了* 和 – 运算符由于设计一个适用于所有容器的迭代器是非常困难的每个 迭代器都必须很了解容器所以STL的每一种容器都提供了相应的专属迭代器。 STL在广义上有5种迭代器类型不限于这5种还可以是原生指针等具体的容器定义自己的迭代器但 是类型是这几种之一或者是原生指针等 input iterator : 这种迭代器所指对象不允许外界改变即是只读的 output iterator : 唯写 forward iterator : 允许写入型算法 bidirectional iterator : 可双向移动的迭代器 random access iterator : 涵盖所有指针运算能力可随机访问任何位 它们在STL中的定义如下 template class T, class Distance struct input_iterator {typedef input_iterator_tag iterator_category;typedef T value_type;typedef Distance difference_type;typedef T* pointer;typedef T reference;
};
struct output_iterator {typedef output_iterator_tag iterator_category;typedef void value_type;typedef void difference_type;typedef void pointer;typedef void reference;
};
template class T, class Distance struct forward_iterator {typedef forward_iterator_tag iterator_category;typedef T value_type;typedef Distance difference_type;typedef T* pointer;typedef T reference;
};
template class T, class Distance struct bidirectional_iterator {typedef bidirectional_iterator_tag iterator_category;typedef T value_type;typedef Distance difference_type;typedef T* pointer;typedef T reference;
};
template class T, class Distance struct random_access_iterator {typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef Distance difference_type;typedef T* pointer;typedef T reference;
}; 二 迭代器相应型别及traits思想 书中把traits技法称为STL源代码的门钥可见其十分重要。先介绍迭代器相应型别从字面上意义来 说便是和迭代器相关的类型信息实际上有5种常用的迭代器类型 value type : 迭代器所指对象的型别 difference type : 迭代器之间的距离型别 reference type : 迭代器引用型别 pointer type : 迭代器指针型别 iterator_category : 迭代器本身的型别 STL内部需要知道当前的迭代器的这些型别信息其所使用的方法主要是模板的参数推导、模板内嵌型 别以及模板偏特化。这里介绍下模板偏特化的概念。 模板的偏特化是指任何template参数更进一步的条件限制所设计出来的一个特化版本例如 templatetypename T class C{…} //这个版本允许T为任何类型 templatetypename T class CT*{…} //这个特化版本仅适用于“T为原生指针的”的情况它比上面的更特殊 有了模板偏特化就可以让traits萃取出原生指针譬如vector的迭代器就是原生指针型别的以及指 向常量的原生指针型别而不仅仅是类类型的而负责萃取的便是 iterator_traits: template class Iterator
struct iterator_traits {typedef typename Iterator::iterator_category iterator_category;typedef typename Iterator::value_type value_type;typedef typename Iterator::difference_type difference_type;typedef typename Iterator::pointer pointer;typedef typename Iterator::reference reference;
}; 如果是类类型的性别用上面这个就可以获得其5个相应型别当然这些型别必须都在相应iterator类 里面定义好见第一节的5种迭代器的定义那么如果不是上面5种而是原生指针等其他型别呢这时候 就用到了模板偏特化: //原生指针用这个
template class T
struct iterator_traitsT* {typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef ptrdiff_t difference_type;typedef T* pointer;typedef T reference;
};
//指向常量的原生指针用这个
template class T
struct iterator_traitsconst T* {typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef ptrdiff_t difference_type;typedef const T* pointer;typedef const T reference;
}; 通过这个traits我们就可以获得任何一种iterator的相应型别通过以下表达式即可 iterator_traits…::… 说到这里有一个很重要是设计思想不得不提就是通过函数重载在编译时决策正确的函数调用。这个问 题源于5种迭代器的类型它们的巡防能力是不同的例如random acess iterator是巡防能力最强的可以 在O(1)时间巡防指定位置而这个用其他的迭代器可能需要O(n)。所以为了提高效率我们应该用和迭代器 类型最匹配的算法函数去调用能用random access iterator的就不要用其他的。那么怎么做呢 首先通过traits获得iterator_category这样我们能够知道当前迭代器的类型。实际上iterator_category就是用来提供这种服务的。 在函数调用时生成相应迭代器类型的临时对象作为实参传递编译器就会调用相应的重载函数。 为了重载函数识别我们有对应的5种迭代器标识类 struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 继承是为了可以使用传递调用当不存在某种迭代器类型匹配时编译器会依据继承层次向上查找进行传递。 以distance为例 //这里category就是为了产生临时对象
template class InputIterator
inline iterator_traitsInputIterator::difference_type
distance(InputIterator first, InputIterator last) {typedef typename iterator_traitsInputIterator::iterator_category category;return __distance(first, last, category());
}
//input iterator 版注意函数形参最后的类型
template class InputIterator
inline iterator_traitsInputIterator::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag) {iterator_traitsInputIterator::difference_type n 0;while (first ! last) {first; n;}return n;
}
//random access iterator 版
template class RandomAccessIterator
inline iterator_traitsRandomAccessIterator::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last,random_access_iterator_tag) {return last - first;
} 三 __type_traits思想 有了前面的基础我们理解到STL是非常重视效率的而SGI STL又在其基础上实现了一个 __type_traits根据前面的经验我们知道它是一个萃取剂只不过它萃取的型别是 是否具备non-trivial default ctor? 是否具备non-trivial copy ctor? 是否具备non-trivial assignment operator? 是否具备non-trivial dtor? 这里的non-trivial意指非默认的相应函数我们知道编译器会为每个类构造以上四种默认的函数如 果没有定义自己的就会用编译器默认函数如果使用默认的函数本来就是按位拷贝我们可以使用memcpy 等函数来加快速度提高效率。 为了使用函数重载决议我们使用类类型来定义两种类型__true_type和__false_type struct __true_type {
};
struct __false_type {
};
template class type
struct __type_traits { typedef __true_type this_dummy_member_must_be_first;typedef __false_type has_trivial_default_constructor;typedef __false_type has_trivial_copy_constructor;typedef __false_type has_trivial_assignment_operator;typedef __false_type has_trivial_destructor;typedef __false_type is_POD_type;
}; 这个是泛化版STL对几乎每种内置类型都定义了相应的特化版本来制定它们的类型整体实现不难。 后记 通过迭代器的设计我们能够看到很多非常有价值的思想也对模板的强大有了更加深刻的认识这些也是 继续阅读STL源码的基础。转载地址http://www.cnblogs.com/HappyAngel/archive/2011/04/19/2021413.html转载于:https://www.cnblogs.com/HXloveLL/p/3698533.html
