SGI-STL 迭代器实现

2019-11-06 08:32:38

字体：大中小

来源：转载

供稿：网友

SGI-STL 迭代器实现

迭代器模式：该模式能够提供一种方法，使之能够依序寻访某个聚合物（容器）所含的每个元素，而又无需暴露该聚合物的内部表达方式。 ———————————————————————————————————————— 《STL源码剖析》

它是什么？

它其实就是算法与容器的一种粘胶剂。

它像什么？

迭代器的行为非常类似智能指针（SmartPointer），所以对他来说最重要的便是deference（内容提领）和member access（成员访问）。那就是*操作符和->操作符的重载了。关于这两个操作符的重载可以参考STL中auto_ptr的实现。

迭代器五种型别

tralts就像是“原味特性萃取机”，萃取相应型别的特性。利用“内嵌型别”编程技巧和编译器的“template参数推导功能”增强了C++型别认证方面的能力。

// 用于traits出迭代其所指对象的型别template <class iterator="">struct iterator_traits{ typedef typename Iterator::iterator_category iterator_category; // 迭代器类型, STL提供五种迭代器 typedef typename Iterator::value_type value_type; // 迭代器所指对象的型别， //如果想与STL算法兼容, 那么在类内需要提供value_type定义 typedef typename Iterator::difference_type difference_type; // 这个是用于处理两个迭代器间距离的类型 typedef typename Iterator::pointer pointer; // 直接指向对象的原生指针类型 typedef typename Iterator::reference reference; // 这个是对象的引用类型};

内嵌型别机制

//内嵌型别机制（以value_type 为例）template <class T>struct MyIter { typedef T value_type; // 内嵌型别声明, 相当于是在本迭代器内部有了一个已经推导好的型别 T* ptr; MyIter(T* p = 0) :ptr(p) {} T& Operator*() const { return *ptr; }};template <class I>typename I::value_type // func返回值型别func(I iter) { return *iter;}void TestIteratorSTLValueType(){ MyIter<int> iter(new int(8)); cout << func(iter) << endl;}

template参数推导功能

关于模板推导详见

value_type

value type 是指迭代器所指对象的型别。

difference_type

difference type用来表示两个迭代器之间的距离的类型，例如容器的容量。

reference_type

在c++中，函数如果要传回左值，都是以by reference 的方式进行，所以如果p是一个迭代器，他的value type 是T，那么*p 应该是T&（即reference type）。Item& 就是reference_type。

Item& operator*()const {return *ptr;}pointer_type 即指针类型，也就是说我们可以返回一个指针，指向迭代器所指之物应该是T*（即pointer_typetype）。Item* 就是pointer_type。 Item* operator->()const {return ptr;}iterator_category

用来产生tag标识，通过激活编译器的重载机制，来抉择调用正确函数。

迭代器的分类： 1、Input Interator ：只允许作为输入，也就是只读（Read Only） 2、Output Interator ：只允许作为输出，也就是只写（Write Only） 3、Forward Interator ：允许读写，但只能做前向移动 4、Bidirectional Interator ：允许读写，可以做双向移动 5、Random Access Interator ：允许读写，可以任意移动

iterator_category的实现

实际上这个函数是被重载成六个函数的，如下：

inline output_iterator_tag iterator_category(const output_iterator&);template <class T, class Distance> inline input_iterator_tag iterator_category(const input_iterator<T, Distance>&);template <class T, class Distance> inline forward_iterator_tag iterator_category(const forward_iterator<T, Distance>&);template <class T, class Distance> inline bidirectional_iterator_tag iterator_category(const bidirectional_iterator<T, Distance>&);template <class T, class Distance> inline random_access_iterator_tag iterator_category(const random_access_iterator<T, Distance>&);template <class T>inline random_access_iterator_tag iterator_category(const T*);

调用过程，如下：

template <class BidirectionalIterator>void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) { while (true) if (first == last || first == --last) return; else iter_swap(first++, last);}template <class RandomAccessIterator>void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) { while (first < last) iter_swap(first++, --last);}template <class BidirectionalIterator>inline void reverse(BidirectionalIterator first, BidirectionalIterator last) { __reverse(first, last, iterator_category(first));}

原理：它就像是我们调用int()会产生什么？对会产生一个临时变量。参见

实现过程：

template <class Iterator>inline typename iterator_traits::iterator_categoryiterator_category(const Iterator&) { typedef typename iterator_traits::iterator_category category; // 其实就是返回Iterator的iterator_category类型 return category();}

SGI-STL中的保证：

//自定义的迭代器必须定义的五种型别template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>struct iterator{ typedef T value_type; typedef Distance difference_type; typedef Reference reference; typedef Pointer pointer; typedef Category iterator_category;};//把之前的五种合并在一个traits中template <class Iterator>struct iterator_traits { typedef typename Iterator::value_type value_type; typedef typename Iterator::difference_type difference_type; typedef typename::Iterator::reference reference; typedef typename::Iterator::pointer pointer; typedef typename::Iterator::iterator_category iterator_category;};//原生指针偏特化版template <class Iterator>struct iterator_traits<T*> { typedef T value_type; typedef ptrdiff_t difference_type; typedef T& reference; typedef T* pointer; typedef random_access_iterator_tag iterator_category;};//const原生指针偏特化版template <class Iterator>struct iterator_traits<const T*> { typedef T value_type; typedef ptrdiff_t difference_type; typedef const T& reference; typedef const T* pointer; typedef random_access_iterator_tag iterator_category;};

上一篇：转

下一篇：deeplearning 打卡第三天