【STL源码剖析读书笔记】【第3章】迭代器概念与traits编程技法

本文主要是介绍【STL源码剖析读书笔记】【第3章】迭代器概念与traits编程技法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、迭代器模式：提供一种方法，使之能够依序寻访某个容器所含的各个元素，而又无需暴露该聚合物的内部表达式。

2、STL的中心思想：将数据容器和算法分开，彼此独立设计，最后用迭代器将它们撮合在一起。

3、迭代器是一种智能指针，最终要的编程工作就是对operator*和operator->进行重载工作。

4、迭代器例子

#include<iostream>
#include<algorithm>
using namespace std;template<typename T>
struct ListItem{  //链表节点数据结构ListItem() :m_next(nullptr){}//默认构造函数ListItem(T value, ListItem* p = nullptr) { m_value = value; m_next = p; } //构造函数ListItem* Next() const { return m_next; }  //返回m_next指针T Value() const { return m_value; } //返回值T m_value;  //存储的数据ListItem* m_next; //指向下一个ListItem的指针
};template<typename T>
class List{ //链表数据结构
public:List() :m_begin(nullptr), m_befend(nullptr), m_end(nullptr){} //默认构造函数void Push_back(T value){  //从链表尾部插入元素ListItem<T>* temp = new ListItem<T>(value, nullptr);if (m_begin == nullptr){m_begin = m_befend = temp;}else{m_befend->m_next = temp;m_befend = temp;}}void Push_front(T value){  //从链表头部插入元素ListItem<T>* temp = new ListItem<T>(value);if (m_begin == nullptr){m_begin = m_befend = temp;}else{temp->m_next = m_begin;m_begin = temp;}}ListItem<T>* Begin() const { return m_begin; }  //返回链表头部指针ListItem<T>* End() const { return m_end; }      //返回链表尾部指针void Print(ostream& os = cout) const{        //打印链表元素for (ListItem<T>* p = Begin(); p != End(); p = p->Next())os << p->Value() << " ";os << endl;}
private:ListItem<T>* m_begin; //指向List头部的指针ListItem<T>* m_befend; //指向List最后一个元素的指针ListItem<T>* m_end; //指向List尾部的指针long m_size; //List的长度
};
// ListIter继承STL提供的iterator，保证符合STL所需之规范
template<typename T>
class ListIter :public iterator<forward_iterator_tag, T>{
public:ListIter(T* p = nullptr) :m_ptr(p){}   //默认构造函数T& operator*() const { return *m_ptr; }; //dereference,解引用T* operator->() const { return m_ptr; } //member access,成员访问ListIter& operator++(){ m_ptr = m_ptr->Next(); return *this; } //前置++操作,暴露了ListItem的Next()ListIter operator++(int){ ListIter temp = *this; ++*this; return temp; }//后置++操作bool operator==(const ListIter& i)const{ return m_ptr == i.m_ptr; }//判断两个ListIter是否指向相同的地址bool operator!=(const ListIter& i)const{ return m_ptr != i.m_ptr; }//判断两个ListIter是否指向不同的地址
private:T* m_ptr;  //保持与容器之间的一个联系
};template<typename T>  //本例中value的型别是int，iter的型别是ListItem<int>,必须写operator==重载函数
bool operator==(const ListItem<T>& item, const T& n){return item.Value() == n;
}//template<typename T>  //STL源码剖析中说是要写operator!=重载函数，但是我这边不成功，需要写的是operator==重载函数
//bool operator!=(const ListItem<T>& item, const T& n){
//	return item.Value() != n;
//}int main(){List<int> mylist;for (int i = 0; i < 5; ++i){mylist.Push_front(i);mylist.Push_back(i + 2);}mylist.Print();ListIter<ListItem<int>> begin(mylist.Begin()); //暴露了ListItemListIter<ListItem<int>> end(mylist.End()); //暴露了ListItemListIter<ListItem<int>> iter;iter = find(begin, end, 1);//从链表中查找3if (iter == end)cout << "not found" << endl;elsecout << "found" << endl;     //输出founditer = find(begin, end, 7);//从链表中查找3if (iter == end)cout << "not found" << endl;  //输出not foundelsecout << "found" << endl;system("pause");return 0;
}

上面的例子在main函数中暴露了ListItem，在ListItem暴露了ListItem的Next()。如果不是为了迭代器，ListItem应该完全隐藏起来。所以把迭代器的开发工作交给List的设计者，这样实现细节得以封装不被使用者看到，这也是每一种STL容器有专属迭代器的原因。

5、迭代器分为五类：

Input Iterator：这种迭代器所指的对象，不允许外界改变。只读(read only)。

Output Iterator：只写(write only)。

Forward Iterator：在此种迭代器所形成的区间上进行读写操作。

Bidirectional Iterator：可双向移动。

RandomAccess Iterator ：前四种迭代器都只供应一部分指针算术能力（前三种支持operator++，第四种再加上operator--），第五种则涵盖所有指针算术能力，包换p+n，p-n，p[n]，p1-p2，p1<p2。

6、“特性萃取机”traits：榨取各个迭代器的特性

template<class I>
struct iterator_traits{typedef typename I::value_type  value_type;
};

这个所谓的traits的意义是如果I定义有自己的valuetype，那么通过这个traits的作用，萃取出来的value type就是I::value type。

template<class I>
struct iterator_traits<I*>{typedef I value_type; //偏特化版——迭代器是原生指针
};
template<class I>
struct iterator_traits<const I*>{typedef I value_type; //偏特化版——迭代器是pointer-to-const时，萃取出来的型别是I而非const I
};

template<class I>
struct iterator_traits{typedef typename I::iterator_category  iterator_category;typedef typename I::value_type  value_type;typedef typename I::difference_type difference_type;typedef typename I::pointer pointer;typedef typename I::reference reference;
};

7、迭代器相应型别：

1) valuetype：value type是指迭代器所指对象的类型。

2) difference type：difference type用来表示两个迭代器之间的距离。

3) reference type：reference type是指迭代器所指对象的类型的引用。

4) pointer type: pointer type是指迭代器所指对象的指针。

5) 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 :forward_iterator_tag{};
struct random_access_iterator_tag : public bidirectional_iteratir_tag{};

8、 STL 提供了一个iterator类，每个新设计的迭代器都继承自它，这样就能保证这些自定义的迭代器符合STL所需的规范，iterator类具体定义如下：

template<typename Category,typename T,typename Distance = ptrdiff_t,typename Pointer = T*,typename Reference = T&>
struct iterator
{typedef Category iterator_category;typedef T value_type;typedef Distance difference_type;typedef Pointer pointer;typedef Reference reference;
};