########################################
自定义类型的迭代器
########################################

.. admonition:: 附注

   本文转自 `C++ 中如何实现自定义类型的迭代器 <https://blog.csdn.net/XiaoHeiBlack/article/details/77014626>`_

动机
****************************************

我们知道 STL 实现了很多算法( ``#include<algorithm>`` )，如果项目是基于 STL 构建那么能够最大化使用现有代码当然是最好的。在 STL 中 **容器** 和 **算法** 之间的桥梁是 **迭代器** 。所以在定义好自定义类型的容器后，接下来就是迭代器的实现。

STL 中的迭代器
****************************************

迭代器模式是一种经典的设计模式，而 STL 的迭代器实现用到了模板的一些特性和技能，其中的细节可以去参考《STL 源码剖析》里面的内容，在这里稍微介绍一下

下面是 STL 中结构体 iterator 的定义，这么定义是给后面的算法多态和萃取时 (具体见书中介绍) 使用的。其中的 _Category 和 _Ty 没有默认值，需要自己给参数的。_Ty 就是元素的类型

.. code-block:: cpp

   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 是迭代器的类型，主要有以下几种

.. code-block:: cpp

   //  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 都用到哪些操作符吧

.. code-block:: cpp

   // TEMPLATE FUNCTION count_if
   template<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);
      }

可以看到用到了 ++,!=,\*。所以我们的迭代器需要把这些都给实现了。代码很简单：

.. code-block:: cpp

   #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;// 实际的内容指针，通过该指针跟容器连接
   };

自定义容器
****************************************

下面给出个简单的数组容器，实现了数组的基本操作。并把刚刚定义的迭代器内置了

.. code-block:: cpp

   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 函数，可以看到用法完全一样

.. code-block:: cpp

   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)：

.. code-block:: cpp

   //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;
   }

迭代器赋予了容器更多的功能和通用性