##动机
我们知道STL实现了很多算法(#include<algorithm>)，如果项目是基于STL构建那么能够最大化使用现有代码当然是最好的。在STL中容器和算法之间的桥梁是迭代器。所以在定义好自定义类型的容器后，接下来就是迭代器的实现。
STL中的迭代器
迭代器模式是一种经典的设计模式，而STL的迭代器实现用到了模板的一些特性和技能，在这里稍微介绍一下
下面是STL中结构体iterator的定义，这么定义是给后面的算法多态和萃取时(具体见书中介绍)使用的。
其中的_Category 和_Ty 没有默认值，需要自己给参数的。
_Ty就是元素的类型
template<class _Category, class _Ty, class _Diff = ptrdiff_t, class _Pointer = _Ty *, class _Reference = _Ty&> struct iterator { // base type for iterator classes typedef _Category iterator_category; typedef _Ty value_type; typedef _Diff difference_type; typedef _Diff distance_type; // retained typedef _Pointer pointer; typedef _Reference reference; };
而_Category是迭代器的类型，主要有以下几种
// ITERATOR STUFF (from <iterator>)// ITERATOR TAGS (from <iterator>)struct input_iterator_tag //只读 { // identifying tag for input iterators };struct _Mutable_iterator_tag //只写 { // identifying tag for mutable iterators };struct output_iterator_tag //只写 : _Mutable_iterator_tag { // identifying tag for output iterators };struct forward_iterator_tag //前向移动 : input_iterator_tag, _Mutable_iterator_tag { // identifying tag for forward iterators };struct bidirectional_iterator_tag //可双向移动 : forward_iterator_tag { // identifying tag for bidirectional iterators };struct random_access_iterator_tag //随机读写 : bidirectional_iterator_tag { // identifying tag for random-access iterators };//...
自定义迭代器
我希望迭代器有以下操作:*,++。另外还想要通过迭代器调用count_if函数。那看一下count_if都用到哪些操作符吧
// TEMPLATE FUNCTION count_iftemplate<class _InIt, class _Pr> inline typename iterator_traits<_InIt>::difference_type _Count_if(_InIt _First, _InIt _Last, _Pr _Pred) { // count elements satisfying _Pred typename iterator_traits<_InIt>::difference_type _Count = 0; for (; _First != _Last; ++_First) if (_Pred(*_First)) ++_Count; return (_Count); }
可以看到用到了++,!=,*。所以我们的迭代器需要把这些都给实现了。代码很简单：
#include<iterator>template<class T>class MyIterator : public iterator<input_iterator_tag, T>{ public: MyIterator(T* p){ _ptr = p; } //赋值 MyIterator& operator = (const MyIterator &iter) { _ptr = iter._ptr; } //不等于 bool operator != (const MyIterator &iter) { return _ptr!= iter._ptr; } //等于 bool operator == (const MyIterator &iter) { return _ptr == iter._ptr; } //前缀自加 MyIterator& operator ++ () { _ptr++; return *this; } //后缀自加 MyIterator operator ++ (int) { MyIterator tmp= *this; _ptr++; return tmp; } //取值 T& operator * () { return *_ptr; } private: T* _ptr;//实际的内容指针，通过该指针跟容器连接};
自定义容器
下面给出个简单的数组容器，实现了数组的基本操作。并把刚刚定义的迭代器内置了
template<class T>class myVector{public: typedef MyIterator<T> iterator;//所有类型迭代器用同一个名字，便于写出更通用的代码 myVector(){ _selfElems = new T[32]; _count = 32; init(); } myVector(int n){ _selfElems = new T[n]; _count = n; init(); } void init(){ memset(_selfElems, 0, sizeof(T)* _count); } //常用接口 T& operator[](int i){ return _selfElems[i]; } iterator begin(){ return iterator(_selfElems); } iterator end(){ return iterator(_selfElems + _count); } int size() const { return _count; }private: T* _selfElems; int _count;};
##测试
定义一个vector和自定容器myVector,用迭代器去访问，并通过迭代器使用conunt_if函数，可以看到用法完全一样
bool eq_10(int k){ return k == 10;}int main(){ //自定义类型 myVector<int> mv(10); mv[3] = 10; mv[9] = 10; myVector<int>::iterator it = mv.begin(); cout <<"mv:"<<endl; while (it != mv.end()){ cout << *(it++) << " "; } cout << endl; cout << count_if(mv.begin(), mv.end(), eq_10) << endl; //STL 容器 vector<int> v(10,0); v[3] = 10; v[9] = 10; vector<int>::iterator it1 = v.begin(); cout << "v:" << endl; while (it1 != v.end()){ cout << *(it1++) << " "; } cout << endl; cout << count_if(mv.begin(), mv.end(), eq_10) << endl; getchar(); return 0;
总结和思考
所以简单来说，如果想要定义自己容器的迭代器并想通过迭代器调用STL的算法函数的话。首先继承iteroter，然后实现必要的操作符即可。不过具体的算法函数对迭代器类型是有要求的，这个需要自己把握。
在这个简单的示例里面，直接用myVector的指针(mv._ptr)也是可以调用count_if的，因为STL通过模板偏特化技术使得迭代器也支持原生指针。不过既然把访问元素都放到迭代器中了，我们就可以对所有的容器用统一的方式访问了，而不用暴露每个容器的细节(myVector：：_ptr)：
//T为某种迭代器template<class T>void display(T it, T end){ T it1 = it; while (it1 != end){ cout << *(it1++) << " "; } cout << endl; cout << count_if(it,end, eq_10) << endl;}int main(){ //自定义类型 myVector<int> mv(10); mv[3] = 10; mv[9] = 10; //STL 容器 vector<int> v(10, 0); v[3] = 10; v[9] = 10; //vector 和 myVector底层实现有很大区别，但是可用同一个函数做遍历等操作 display(mv.begin(), mv.end()); display(v.begin(), v.end()); getchar(); return 0;}
迭代器赋予了容器更多的功能和通用性
补充知识：C++ 自定义迭代器(实现++递增两格)
//效果每次迭代器加移动两格
#pragma once//MyIterator.h#include <iterator>#include <exception>template<typename Container>class MyIterator :public std::iterator<std::random_access_iterator_tag, typename Container::value_type>{protected: Container& container; typename Container::iterator pos;public: explicit MyIterator(Container& c) :container(c), pos(c.begin()){} MyIterator(const MyIterator& rhs) :container(rhs.container),pos(rhs.pos) {} MyIterator& operator =(const MyIterator& rhs) { throw_ex(rhs.container); pos = rhs.pos; return *this; } //--等就省略了... MyIterator& operator ++() { auto tmp = container.end() - 1; if (pos == tmp) ++pos; else pos += 2; return *this; } bool operator ==(const MyIterator& rhs)const { try { if (&rhs.container == &container) return pos == rhs.pos; else { throw exception("对象错误"); } } catch (exception &e) { cout << e.what(); exit(EXIT_FAILURE); } }bool operator !=(const MyIterator& rhs)const{ return !(*this == rhs);}typename Container::value_type & operator *(){ return *pos;}void begin(){ pos = container.begin();}void end(){ pos = container.end();}private: void throw_ex(const Container& c) { try { if (&c == &container) return; else throw exception("Copy 构造失败"); } catch (exception &e) { cout << e.what(); exit(EXIT_FAILURE); } }};//无法使用或添加vector<T> vec 成员函数vec.begin()或全局函数begin(vec)//我们做个假冒的全局函数 start(vec) over(vec)template<typename Container>MyIterator<Container> start(Container& c){ MyIterator<Container> mi(c); mi.begin(); return mi;}template<typename Container>MyIterator<Container> over(Container & c){ MyIterator<Container> mi(c); mi.end(); return mi;}
//main.cpp
#include <iostream>#include <vector>#include "MyIterator.h"#include <list>using namespace std;//因继承了iterator<std::random_access_iterator_tag,Container::value_type>才拥有此特性template<typename Iterator>void printIterator(const Iterator &It){ cout << typeid(typename iterator_traits<Iterator>::iterator_category).name() << endl;}int main(){ vector<int> coll{ 1,2,3,4,5,6,7,8,9,10 }; MyIterator<decltype(coll)> myit(coll); printIterator(myit); for (; myit != over(coll); ++myit) { cout << *myit << ends; } system("pause"); return 0;}
效果：
以上为个人经验，希望能给大家一个参考，也希望大家多多支持。如有错误或未考虑完全的地方欢迎留言讨论，望不吝赐教。
黄色蓝色或者砖红色，犹如童话世界。
