自己动手写C++迭代器

2023-05-16

综述

关于STL iterator和 iterator adapter 的部分我已在先前的博客 stl源码剖析笔记之iterator 中有所提及，下面我们可以试着自己动手写一个简单的迭代器工具 step_iterator，以深入对iterator的理解。

step_iterator 可以接受两个模板参数，一个是迭代器 Iter，一个是步进距离 Step，相较于普通的迭代器，它可以以 Step 的距离前进或者后退。

我们将通过 std::iterator 和 boost::iterator_adaptor 两种方式来实现上述功能的迭代器。

继承 std::iterator

STL源码中定义了 std::iterator，以对 iterator 的型别做出规范。

//stl_iterator.h
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
          class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
  typedef _Category  iterator_category;
  typedef _Tp        value_type;
  typedef _Distance  difference_type;
  typedef _Pointer   pointer;
  typedef _Reference reference;
};

《STL源码剖析》一书中提到，我们可以用模板继承的方式构建迭代器，可以省去一些代码书写。这样我们就可以这样定义step_iterator ：

template <class _Iter, std::ptrdiff_t _Step=2>
class step_iterator2 : public std::iterator<typename std::iterator_traits<_Iter>::iterator_category, typename std::iterator_traits<_Iter>::value_type>{
    private:
            _Iter m_iter;
            typedef  step_iterator2<_Iter, _Step> Self;
            typedef std::iterator<typename std::iterator_traits<_Iter>::iterator_category, typename std::iterator_traits<_Iter>::value_type> BaseIter;
    public:
            using typename BaseIter::reference;
            using typename BaseIter::pointer;
            using typename BaseIter::difference_type;
}

这里我们定义了一个 BaseIter 简化基类 iterator 的书写。以及 using 是必须的，否则虽然基类模板中定义了reference,pointer等类型，但是派生模板并不能直接使用。

使用 iterator_traits

如果不用继承的方式，就应该像下面这么写，使用 iterator_traits 萃取出各个特性。

template <class _Iter, std::ptrdiff_t _Step=2>
class step_iterator2{
    private:
            _Iter m_iter;
            typedef  step_iterator2<_Iter, _Step> Self;
    public:
            typedef typename std::iterator_traits<_Iter>::iterator_category iterator_category;
            typedef typename std::iterator_traits<_Iter>::value_type value_type;
            typedef typename std::iterator_traits<_Iter>::pointer pointer;
            typedef typename std::iterator_traits<_Iter>::reference reference;
            typedef typename std::iterator_traits<_Iter>::difference_type difference_type;

}

这里多提一句，似乎 typedef typename _Iter::iterator_category iterator_category 也可以萃取出特性，写法还更简略些，那么为什么不这么写呢？因为还要考虑到模板参数是指针的情况，而 iterator_traits 有特化版本，可以考虑到各种情况。

虽然说可以用模板继承方式构建迭代器，但实际上，一些常用的迭代器工具，如 std::ostream_iterator , std::reverse_iterator 等，并没有用模板继承。

实现与测试

接下来我们需要实现 iterator 的几个必须实现的接口

template <class _Iter, std::ptrdiff_t _Step=2>
class step_iterator2 : public std::iterator<typename std::iterator_traits<_Iter>::iterator_category, typename std::iterator_traits<_Iter>::value_type>{
    private:
            _Iter m_iter;
            typedef  step_iterator2<_Iter, _Step> Self;
            typedef std::iterator<typename std::iterator_traits<_Iter>::iterator_category, typename std::iterator_traits<_Iter>::value_type> BaseIter;
    public:
            using typename BaseIter::iterator_category;
            using typename BaseIter::value_type;
            using typename BaseIter::reference;
            using typename BaseIter::pointer;
            using typename BaseIter::difference_type;
    public:
            step_iterator2(_Iter i):m_iter(i){}

            reference operator*(){ return *m_iter; }
            pointer operator->(){ return m_iter; }
            Self& operator++(){
                std::advance(m_iter, _Step);
                return *this;
            }
            Self operator++(int){
                Self temp=this;
                std::advance(m_iter, _Step);
                return temp;
            }

            Self& operator--(){
                std::advance(m_iter,-_Step);
                return *this;
            }
            Self operator--(int){
                Self temp=this;
                std::advance(m_iter, -_Step);
                return temp;
            }
            bool operator!=(const Self& other) const{
                return m_iter!=other.m_iter;
            }
            difference_type operator-(const Self& other){
                return std::distance(other.m_iter,m_iter);
            }

};

写一个测试文件，测试一下效果。

//test.cpp
#include "step_iterator.h"
#include <vector>
#include <iostream>

int main(){
        using namespace std;
        vector<int> a={1,2,3,4,5,6};
        copy(a.begin(),a.end(),ostream_iterator<int>(cout," ")); //1 2 3 4 5 6
        cout<<endl;
        step_iterator2<typename vector<int>::iterator> s3(a.begin()), s4(a.end());
        copy(s3, s4, ostream_iterator<int>(cout," "));  //1 3 5 0 0
        cout<<endl;
        return 0;
}

然而，打印并不是 1 3 5，细究一下，原因出在 copy() 这个全局模板函数上面。我们看 copy() 的源码核心部分如下：

//stl_algo.h
for(Distance n=last- first; n>0; --n, ++result, ++first)
  *result=*first;

for循环次数是由 last-first 决定的，然而对于 step_iterator 来说， operator- 是计算 m_iter 迭代器之间的距离，显然就不对了。所以我们应该再改进一下。

difference_type operator-(const Self& other){
    return std::distance(other.m_iter,m_iter)/_Step;
}

对于此测试例来说， step_iterator 已经初步成型了。然而这样的 step_iterator 并不完美，还有很多成员函数没有实现，例如 operator+= , operator-=，实际上这些操作符都有很多共通的地方，一个个去写会很麻烦，有没有更好的解决办法呢？Boost库提供了一些好的思路。

boost::iterator_adaptor

首先有个小小的地方想吐槽一下，就是这个 adaptor 的写法，《STL源码剖析》中用的一直都是adapter，到了boost这里突然变成了 adaptor，总之，不要在意这些细节吧。

罗剑锋的《Boost程序库探秘》第三章探究了迭代器基类模板 iterator_facade 和 iterator_adaptor 的一些用法。iterator_facade 顾名思义，用了设计模式中外观模式的思想，给 iterator 重新披上一层外衣（它并不是提供新的功能，而是将原有的操作符和成员函数封装成另一个接口）

摘抄Boost文档中关于 iterator_facase 的说明如下：

Although it is easy to create iterators that almost conform to the standard, the iterator requirements contain subtleties which can make creating an iterator which actually conforms quite difficult. Further, the iterator interface is rich, containing many operators that are technically redundant and tedious to implement. To automate the repetitive work of constructing iterators, we propose iterator_facade, an iterator base class template which provides the rich interface of standard iterators and delegates its implementation to member functions of the derived class.

大意是， iterator_facade 提供了丰富的标准迭代器接口，并且将它们的实现委托到派生类的成员函数中。例如之前说的， operator++ 和 operator+= 中共通的代码，就可以放到 increment() 成员函数中让派生类自己去实现。

派生的迭代器类要实现以下成员函数：

dereference()
equal()
increment()
decrement()
advance()
distance_to()

而标准 iterator 的一些成员函数和操作符，都转换为对以上核心成员函数的调用。

iterator_adaptor 继承自 iterator_facade ，接受一个 Adaptee 成员，通常是一个迭代器对象，可以借助它来完成核心成员函数的缺省实现。

被适配的迭代器称为 Adaptee ，iterator_adaptor 有一个Adaptee类型的私有成员 m_iterator ，派生类可以用 base_reference() 或者 base() 访问它。

iterator_adaptor 的模板参数如下

template<
    class Derived,                              //迭代器子类名
    class Adaptee,                              //被适配的迭代器
    class Value                 = use_default,  //值类型
    class CategoryOrTraversal   = use_default,  //迭代器分类标志
    class Reference             = use_default,  //迭代器值引用类型
    class Difference            = use_default,  //迭代器距离类型
>

我们可以以继承 iterator_adaptor的方式实现 step_iterator：

template <class _Iter, std::ptrdiff_t _Step=2>
class step_iterator1 : public boost::iterator_adaptor<step_iterator1<_Iter,_Step>, _Iter>{
    private:
            typedef  step_iterator1<_Iter, _Step> Self;
            using typename step_iterator1::iterator_adaptor_::difference_type; 

    public:
            step_iterator1(_Iter i):step_iterator1::iterator_adaptor_(i){}
            void increment(){
                this->base_reference()+=_Step;
            }   
            void decrement(){
                this->base_reference()-=_Step;
            }   
            difference_type distance_to(const  Self& other) {
                return distance_to(this->base_reference(), other.base_reference())/_Step;
            }   

};

相较继承 std::iterator 的方式，是不是简明了很多呢？事实上，Boost库常用的迭代器工具，都继承自 iterator_adaptor 。

参考

stackoverflow-How to correctly implement custom iterators and const_iterators?

stackoverflow-I inherit from std::iterator, but compiler does not recognise ‘pointer’ or ‘reference’

Boost文档-iterator_facade
Boost文档-Iterator Facade and Adaptor

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)