iterator adaptor介绍

时间：2021-04-12 01:15:19

STL中适配器包括容器适配器、迭代器适配器和仿函数适配器，本文结合源码介绍STL中常见的迭代器适配器（iterator adaptor），以及如何自定义一个iterator adaptor；涉及到的知识点包括adaptor 设计模式，Facade设计模式，CRTP等设计范式；

adaptor & Facade 设计模式介绍

既然是iterator adaptor，那首先简单介绍下adaptor设计模式，Facade设计由于在“自定义迭代器适配器实现”一节中会进行应用，所以在此一并进行介绍，已经熟知的同学可跳过；

adaptor设计模式

适配器模式是将一个类进行封装转换成业务兼容的接口，例如生活中的电源适配器，代码实现通常有继承和委托方式；

iterator adaptor介绍

adaptor实现接口类，同时继承被适配类Adaptee（被适配者），将NewMethod 转换成 Method方法；

iterator adaptor介绍

对象委托方式的主要变化为adaptor与Adaptee为聚合关系，即adaptor持有Adaptee的指针或者引用，相比继承方式耦合更小，下文中介绍的iterator adaptor即为委托方式实现；

补充：继承虽然耦合更紧密，但在某些场景下能起到更好的设计效果，如EBO优化和Mixins模式，所以还是需要根据具体的业务场景选择合适的实现方式，并非绝对；

facade设计模式

iterator adaptor介绍

上图中用户依赖子系统内部各模块的接口，当模块接口发生变化时可能需要多个客户进行修改；同时带来系统构建时依赖关系的复杂；门面模式用于为子系统提供一个统一的门面，将依赖简化；client不直接依赖各个Module；

详细的设计模式读者可以参阅【1】

STL库常见iterator adaptor及实现

iterator adaptor介绍

STL中提供迭代器适配器如上所示【6】，本文中取常用的两个适配器结合源码进行说明原理；

std::back_insert_iterator

std::vector<int> src {1, 2, 3, 4, 5};
    std::vector<int> dst;
    std::copy(src.begin(), src.end(), std::back_insert_iterator(dst));

以上代码实现的功能为将src拷贝到dst中，结合源码分析如下：

iterator adaptor介绍

其中back_insert_iterator 删除了部分实现，保留了相关部分，相信不难理解；front_inserter_iterator实现类似；

std::ostream_iterator

std::vector<int> v {1, 2, 3, 4, 5};
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ", "));

    // output: 1, 2, 3, 4, 5,

以上代码实现对vector的遍历输出，同样源码展开如下：

iterator adaptor介绍

上述代码中将将所有元素拷贝到std::cout，利用cout进行输出；类似istream_iterator拷贝到std::cin，其他迭代器适配器实现类似。

自定义迭代器及适配器实现

上文中提到不同iterator_adaptor的iterator_category 有所不同，也意味这他们 所适配的迭代器也有所区别，本文先对迭代器及其分类进行介绍；

迭代器及其分类介绍

在使用STL进行业务编码时，常使用的容器和迭代器其实不多，所以对iterator_category 开发者通一般不会涉及，就像std::allocator，但在开发一些基础模板库并且配合STL时对其中原理有所理解能更好的进行开发；

不同的容器具有不同的迭代器类型，可以通过iterator_traits来获取对应的iterator_category：

template<typename C>
typename std::iterator_traits<decltype(std::declval<C>().begin())>::iterator_category
GetCategoryType(C&& c) { return {}; }
void Print(std::random_access_iterator_tag)
{ std::cout << "random_access_iterator_tag" << std::endl; }
void Print(std::bidirectional_iterator_tag)
{ std::cout << "bidirectional_iterator_tag" << std::endl; }
void Print(std::output_iterator_tag)
{ std::cout << "output_iterator_tag" << std::endl; }
void Print(std::forward_iterator_tag)
{ std::cout << "forward_iterator_tag" << std::endl; }

通过调用即可打印不同container的iterator_category如下：

iterator adaptor介绍

上图中不包含容器适配器，由于容器不是本文的重点，在此不做展开介绍；而不同iterator_category存在继承关系且对应支持的迭代器操作有所不同，源码如下：

struct input_iterator_tag { };  
struct output_iterator_tag { };

struct forward_iterator_tag : public input_iterator_tag { };

struct bidirectional_iterator_tag : public forward_iterator_tag { };

struct random_access_iterator_tag : public bidirectional_iterator_tag { };
  1. 输入迭代器：即读取迭代器值作为输入(只读，解引用返回const引用)，支持operator*，operator->，operator++，operator==，operator !=；
input_iterator (C++20)
std::istream_iterator
  1. 输出迭代器：可迭代器进行赋值(只写)，支持operator*，operator++；
对应的部分迭代器适配器的category type
std::ostream_iterator
std::ostreambuf_iterator
std::insert_iterator
std::back_insert_iterator
std::front_insert_iterator
  1. 前向迭代器：支持读写；
  2. 双向迭代器：在前向迭代器的基础上增加了operator--;
  3. 随机访问迭代器：在双向迭代器的基础上增加了operator[]，opeator+，operator-，operator+=，operator-=和比较运算等；

iterator facade

实现一个迭代器，每个category的迭代器各自实现一套则显然违反了DRY原则，因此需要提取公共的接口实现并且不引入额外的开销，此处引入facade门面模式提供迭代器归一的接口，目标利用iterator facade 方便的实现迭代器和迭代器适配器；

那么如何设计iterator facade？除了上文中介绍的facade基础，观察现有迭代器需要支持的操作：

iterator adaptor介绍

根据上文当前容器的iterator_category的种类，将forward_iterator_tag的迭代器接口提取作为公共部分，通过bidirectional和random两个bool变量的组合来构成不同的iterator_facade；【4】

如此便可以实现不同iterator包括forward_iterator_tag，bidirectional_iterator_tag，random_iterator_tag；

其中output_iterator_tag 和 input_iterator 用于迭代器适配器，如ostream_iterator和istream_iterator；

参考【3】实现代码如下：

class IteratorFacadeAccess {
    template<typename Derived, typename Value, typename Category,
         typename VauleReference, typename Distance, bool IsBidirectional, bool IsRandom>
    friend class IteratorFacade;

    template<typename VauleReference, typename Iterator, typename Distance = std::ptrdiff_t>
    static VauleReference dereference(const Iterator& i, Distance n = 0)
    {
        return i.dereference(n);
    }

    template<typename Iterator>
    static void increment(Iterator& i)
    {
        i.increment();
    }

    template<typename Iterator>
    static void decrement(Iterator& i)
    {
        return i.decrement();
    }

    template<typename Iterator, typename Distance>
    static void advance(Iterator& i, Distance n)
    {
        return i.advance(n);
    }

public:
    template<typename Iterator>
    static bool equals(const Iterator& il, const Iterator& ir)
    {   
        return il.equals(ir);
    }
};


template<typename Derived, typename Value, typename Category,
         typename Reference, typename Distance, bool IsBidirectional, bool IsRandom>
class IteratorFacade;

template<typename Derived,typename Value, typename Category,
         typename VauleReference, typename Distance>
class IteratorFacade<Derived, Value, Category, VauleReference, Distance, false, false> {
public:
    // 命名兼容stl库中的实现
    using value_type = typename std::remove_const<Value>::type;
    using reference = VauleReference;
    using pointer = Value*;
    using difference_type = Distance;
    using iterator_category= Category;

public:
    Derived& operator++()
    {
        IteratorFacadeAccess::increment(this->asDerived());
        return this->asDerived();
    }

    Derived operator++(int)
    {
        Derived result(this->asDerived());
        IteratorFacadeAccess::increment(this->asDerived());
        return result;
    }

    reference operator*() const
    {
        return IteratorFacadeAccess::dereference<reference>(this->asDerived());
    }

    pointer operator->() const
    {
        return &(IteratorFacadeAccess::dereference<reference>(this->asDerived()));
    }

    // The Barton-Nackman Trick
    friend bool operator == (const IteratorFacade& left, const IteratorFacade& right)
    {
        return IteratorFacadeAccess::equals(left.asDerived(), right.asDerived());
    }

    friend bool operator != (const IteratorFacade& left, const IteratorFacade& right)
    {
        return !(left == right);
    }

protected:
    Derived& asDerived()
    {
        return *static_cast<Derived*>(this);
    }

    Derived const& asDerived() const
    {
        return *static_cast<Derived const*>(this);
    }
};

template<typename Derived,typename Value, typename Category, typename VauleReference, typename Distance>
class IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, false>
    : public IteratorFacade <Derived, Value, Category, VauleReference, Distance, false, false> {
public:
    Derived& operator--()
    {
        IteratorFacadeAccess::decrement(this->asDerived());
        return this->asDerived();
    }

    Derived operator--(int)
    {
        Derived tmp(this->asDerived());
        --*this;
        return tmp;
    }
};

template<typename Derived, typename Value, typename Category, typename VauleReference, typename Distance>
class IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, true>
    : public IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, false> {
public:
    using BaseType = IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, false>;
    using reference = typename BaseType::reference;
    using difference_type = typename BaseType::difference_type;

    reference operator[](difference_type n)
    {
        return IteratorFacadeAccess::dereference<reference>(this->asDerived(), n);
    }

    Derived& operator+=(difference_type n)
    {
        IteratorFacadeAccess::advance(this->asDerived(), n);
        return this->asDerived();
    }

    Derived& operator+(difference_type n)
    {
        IteratorFacadeAccess::advance(this->asDerived(), n);
        return this->asDerived();
    }

    Derived& operator-=(difference_type n)
    {
        IteratorFacadeAccess::advance(this->asDerived(), -n);
        return this->asDerived();
    }

    Derived& operator-(difference_type n)
    {
        IteratorFacadeAccess::advance(this->asDerived(), -n);
        return this->asDerived();
    }
};

代码注释中提及的The Barton-Nackman Trick，请参见笔者之前的《The Barton-Nackman Trick介绍》；而IteratorFacadeAccess的存在为了继承类的接口暴露；

指针改造为指针迭代器

这里借助上述实现的iterator_facade将指针转换为指针迭代器：

template<typename T>
class PtrIterator
    : public IteratorFacade<PtrIterator<T>, T, std::random_access_iterator_tag, T&, std::ptrdiff_t, true, true> {
    friend class IteratorFacadeAccess;
public:
    PtrIterator(T* ptr = nullptr) : m_ptr(ptr) {}
private:  // IteratorFacadeAccess的存在时为了以下接口不会设置为public，不用对外暴露
    T* m_ptr = nullptr;

    T& dereference(std::ptrdiff_t n) const
    {
        return *(m_ptr + n);
    }
    void increment()
    {
        m_ptr += 1;
    }
    void decrement()
    {
        m_ptr -= 1;
    }
    void advance(std::ptrdiff_t n)
    {
        m_ptr += n;
    }
    bool equals(const PtrIterator& others) const
    {
        return m_ptr == others.m_ptr;
    }
};
PersonalInfo *ptr = new PersonalInfo[10];
    PtrIterator<PersonalInfo> iterBegin(ptr);
    PtrIterator<PersonalInfo> iterEnd(ptr + 10);
    iterBegin->name = "小龙总";
    iterBegin->discription = "秀儿";
    std::cout << (*iterBegin).name << ":" << (*iterBegin).discription << std::endl;
    // 输出 小龙总：如此优秀

实现PtrIterator用户需要知道定义的iterator的类型，由于这里指定random_access_iterator_tag，因此需要实现advance，否则如果使用forward_iterator_tag，则不需要实现advance；

自定义迭代器适配实现

更进一步基于PtrIterator，实现一个迭代器适配器，将PersonalInfo中的两个string进行拼接输出；

template<typename Iterator, typename T>
class PtrIteratorAdaptor 
    : public IteratorFacade<PtrIteratorAdaptor<Iterator, T>, T, std::output_iterator_tag, T&, 
                            typename std::iterator_traits<Iterator>::difference_type, false, false> {
    friend class IteratorFacadeAccess;
public:
    PtrIteratorAdaptor(Iterator iterAdaptee): m_iter(iterAdaptee)
    {   
    }   

    const T& operator*()
    {   
        m_string = (*m_iter).name + "~~~" + (*m_iter).discription;
        return m_string;
    }   

private:
    void increment()
    {   
        ++m_iter;
    }   

    bool equals(const PtrIteratorAdaptor& others) const
    {   
        return m_iter == others.m_iter;
    }   

    std::string m_string;
    Iterator m_iter;
};
int main()
{
    PersonalInfo *ptr = new PersonalInfo[5];
    PtrIterator<PersonalInfo> iterBegin(ptr);
    PtrIterator<PersonalInfo> iterEnd(ptr + 5);
    std::for_each(iterBegin, iterEnd, [](auto &Info){
        Info.discription = "✿✿ヽ(°▽°)ノ✿";
    });
    iterBegin[2].name = "小龙总";
    iterBegin[2].discription = "秀儿";

    PtrIteratorAdaptor<PtrIterator<PersonalInfo>, std::string> adapterBegin(iterBegin);
    PtrIteratorAdaptor<PtrIterator<PersonalInfo>, std::string> adapterEnd(iterEnd);
    std::copy(adapterBegin, adapterEnd, std::ostream_iterator<std::string>(std::cout, ", "));
    return 0;
}
~~~✿✿ヽ(°▽°)ノ✿, ~~~✿✿ヽ(°▽°)ノ✿, 小龙总~~~秀儿, ~~~✿✿ヽ(°▽°)ノ✿, ~~~✿✿ヽ(°▽°)ノ✿,

总结：上次实现总体的思想还是分离变化的过程，抽取公共稳定的部分，依赖于稳定

参考资料

【1】《设计模式- 可复用面向对象软件的基础 》

【2】《STL源码剖析》

【3】C++ templates

【4】boost库

【5】The Barton-Nackman Trick介绍

【6】https://en.cppreference.com/w/cpp/iterator


标签：

相关文章