迭代器模式

意图

提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。

动机

提到迭代器模式,就不得不提 STL 中的 iterator,要访问顺序容器和关联容器中的元素,需要通过 迭代器(iterator) 进行。迭代器是一个变量,相当于容器和操作容器的算法之间的中介。迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素

现在已经有现成的实现,但是还是要学习它封装的思路

UML 图

uml

  • Iterator (迭代器)
    迭代器定义访问和遍历元素的接口
  • ConcreteIterator (具体迭代器)
    具体迭代器实现迭代器接口,并对该聚合遍历时跟踪当前位置
  • Aggregate (聚合)
    聚合定义创建相应迭代器对象的接口
  • ConcreteAggregate (具体聚合)
    具体聚合实现创建相应迭代器的接口,该操作返回 ConcreteIterator 的一个适当的实例

UML 中可以看出一个最明显的点,ConcreteIterator 是由 ConcreteAggregate 来对应创建的,那么意味着一个 ConcreteAggregate 聚合可以提供创建不同 ConcreteIterator 的接口,从而实现不同的方式的遍历,正序,倒序等等,并且每个迭代器可以保持它自己的遍历状态,因此也可以同时进行多个遍历。

接着看一下 Iterator 提供的4个接口的意义

  • First()
    使本 Iterator 指向顺序集合中的第一个对象。
  • Next()
    使本 Iterator 指向对象序列的下一个元素。
  • isDone()
    当序列中不再有未到达的对象时返回真。
  • CurrentItem()
    返回序列中当前位置的对象。

C++STL 中的 Iterator 是通过重载了各种运算符来实现类似功能,例如 ++-- 来切换位置,*-> 来获取当前位置的元素, ==!= 来判断元素相等,也可以判断是否到了对象系列的队尾,整体使用起来更加简洁

应用场景

迭代器模式可用来:

  • 访问一个聚合对象的内容而无需暴露它的内部表示。
  • 支持对聚合对象的多种遍历。
  • 为遍历不同的聚合结构提供一个统一的接口 (即, 支持多态迭代)。

实现

STL 中已经封装好 Iterator,避免自己造轮子,这篇文章我选择对 STL 中的 list 中封装的 Iterator 简单分析一下它的源码实现细节

STL 的实际的版本有点多,我查阅的主要有 2 个版本

这二者在实现方面是有一点出入的,在看迭代器模式的时候,我主要看的是 GCC 4.9 版本,接下来我主要介绍一些 GCC 4.9 版本下 list 中的 Iterator 的实现细节

基础

list 是一个环形的双向链表,它在实现上将链表的结构管理和数据信息拆分开

  • _List_node_base 来管理一个节点的前驱和后继,并且提供掺入删除等接口
  • _List_node 继承 _List_node_base,并保存节点的真实数据
struct _List_node_base
{
  _List_node_base* _M_next;
  _List_node_base* _M_prev;

  ...
}

template<typename _Tp>
  struct _List_node : public __detail::_List_node_base
  {
    _Tp _M_data;

    template<typename... _Args>
      _List_node(_Args&&... __args)
      : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) 
        { }

  };

list 的实现也是分为 2 部分, 将节点内存分配的管理都封装在基类 _List_base 中包括头结点,而 list 则封装对外的接口,比如 push_back()pop_front 等等
头结点部分代码如下

struct _List_impl
: public _Node_alloc_type
{
  _List_node<size_t> _M_node;

  ...
};

// 成员变量
_List_impl _M_impl;

_M_impl 的数据区的 _M_node 是一个 _List_node 节点,其中保存数据是链表长度,而它的 _M_next 也就是 list 真正的第一个元素,它的 _M_prev 是链表的最后一个元素,当然第一个元素的前驱指向它,最后一个元素的后继指向它,在补充一点, 迭代器 end() 实际指向的就是这个节点
这样有个好处,一般情况下链表想要知道总长度,需要遍历链表,时间复杂度是 O(n),这也是 SGI 版本实现的list 用的方法,而 GCC 这样实现的复杂度是 O(1),需要维护的无非在插入,删除的时候,同步更新这个节点信息即可

此外 _List_impl 这个类因为继承 _Node_alloc_type, 它也实现了为 _List_node<_Tp> 分配对象内存的功能,这一块暂时不展开了

typedef typename _Alloc::template rebind<_List_node<_Tp> >::other _Node_alloc_type;

头结点初始化的函数如下,使节点的前驱和后继都指向自己,并设置总长度为 0

void _M_init() 
{
  this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
  this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
  _M_set_size(0);
}

void _M_set_size(size_t __n) { _M_impl._M_node._M_data = __n; }

关于 list 基础部分做个简单的总结

  • list 中的数据节点是 _List_node<_Tp> 类型的指针
  • _List_node 保存实际数据,其父类 _List_node_base 保存了节点的前驱和后继节点信息,并且实现了插入和删除等接口
  • list 的头结点是 _List_impl 对象,它的数据区是 _List_node<size_t> 对象,用来保存链表的长度,它的 next 是的 list.begin() 执行的节点,而它自己是 list.end() 指向的节点

list 有个大致的了解了,接下来主要看他迭代器部分的实现

实现细节

list 是链式结构,所以迭代器中并不能通过保存位置信息知道具体的元素,所以直接保存了元素指针

template<typename _Tp>
struct _List_iterator
{
    _List_iterator() 
    : _M_node() { }

    explicit _List_iterator(__detail::_List_node_base* __x) 
    : _M_node(__x) { }

    ...

    __detail::_List_node_base* _M_node;
};

接下来介绍迭代器提供一些类似 First()Next() 等接口的实现

元素间切换

++-- 来分别实现元素间的切换,同时需要区分前置和后置 2 种方式

// 前置,返回的是引用
_List_iterator<_Tp>& operator++() 
{
    _M_node = _M_node->_M_next;
    return *this;
}

// 后置,多了一个形参,只是为了区分前置
_List_iterator<_Tp> operator++(int) 
{
    _Self __tmp = *this;
    _M_node = _M_node->_M_next;
    return __tmp;
}

提供 ++, -- 接口,将控制迭代的行为,交给客户来决定,更灵活,这种形式的也被称为 外部迭代器

元素间判断

==!= 来实现迭代器中的元素是否相等

typedef _List_iterator<_Tp> _Self;

bool operator==(const _Self& __x) const 
{ return _M_node == __x._M_node; }

bool operator!=(const _Self& __x) const 
{ return _M_node != __x._M_node; }

获取元素对象

*-> 来实现获取迭代器当前的元素

typedef _List_node<_Tp>  _Node;

_Tp& operator*() const 
{ return static_cast<_Node*>(_M_node)->_M_data; }

_Tp* operator->() const 
{ return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); }

因为迭代器中实际保存的是 _List_node_base 这个基类的指针,需要先转换成 _List_node 对象,然后从中取出真正的数据 _M_data

这里有 2 个值得注意的点

  • * 返回的是引用,这意味可以对数据直接进行操作
  • -> 返回的是指针,使用了 std::__addressof() 来获取指针真正的地址

我顺便也查阅了一下 SGI 版本这一块的实现,SGI 的版本重载 -> 直接使用的就是 &

_Tp& operator*() const { return ((_List_node<_Tp>*) _M_node)->_M_data; }
_Tp* operator->() const { return &(operator*()); }

接下来看一下 &std::__addressof() 二者的区别,先看一下下面这个例子

struct A {
    A* operator &() { return nullptr; }
};

int main()
{
    A a;
    std::cout << &a << endl;                
    std::cout << std::__addressof(a) << endl; 
    return 0;
}

我的运行结果

0
0x61fe8f

很显然,如果用户传入的类型重载了取地址运算符,那么使用 & 来获取地址是不安全的
std::__addressof 可以保证在重载取地址运算符后仍然可以返回真正的地址

使用

list 迭代器实现的部分算是解释完了,还需要简单说一下 list 是如何提供类似 CreateIterator() 这样接口的

list 提供了 begin()end() 等接口,可以返回一个迭代器对象

_List_iterator<_Tp> begin() { return iterator(this->_M_impl._M_node._M_next); }
_List_iterator<_Tp> end() { return iterator(&this->_M_impl._M_node); }

begin() 返回头结点中指向的下一个结点, end() 返回头结点, 之后获取值或者元素切换都是基于迭代器对象提供的接口

也是因为 list 结构比较特殊,所以需要实现适配自己的 Iterator,而 vector 等部分的数据结构使用的迭代器就是 stl_itreator.h 文件中父类定义好的迭代器,这里先留个伏笔,以后有机会也会逐步形成一个新的系列~

总结

迭代器的核心就是 创建一个迭代器对象,利用它来封装遍历集合内的每个对象的过程

设计模式总结的系列也完结撒花了,之后会再整理一个类似导读或者说助记的总结性的文章,将所有设计模式串联起来~

这篇文章在介绍迭代器的同时,也对 STLlist 部分的源码进行了剖析,为我接下来一段时间学习和总结的方向开了一个头,结合 《STL源码剖析》 和 《Effective STL》 这 2 本书,系统的学习 STL 使用和实现中的技巧,所以要个赞,不过分吧~