意图
提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。
动机
提到迭代器模式,就不得不提 STL
中的 iterator
,要访问顺序容器和关联容器中的元素,需要通过 迭代器(iterator)
进行。迭代器是一个变量,相当于容器和操作容器的算法之间的中介。迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素
现在已经有现成的实现,但是还是要学习它封装的思路
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 版本
github 地址 https://github.com/gcc-mirror/gcc - SGI 版本 : 《STL源码剖析》书中使用的版本
github 地址,https://github.com/steveLauwh/SGI-STL
这二者在实现方面是有一点出入的,在看迭代器模式的时候,我主要看的是 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
文件中父类定义好的迭代器,这里先留个伏笔,以后有机会也会逐步形成一个新的系列~
总结
迭代器的核心就是 创建一个迭代器对象,利用它来封装遍历集合内的每个对象的过程
设计模式总结的系列也完结撒花了,之后会再整理一个类似导读或者说助记的总结性的文章,将所有设计模式串联起来~
这篇文章在介绍迭代器的同时,也对 STL
中 list
部分的源码进行了剖析,为我接下来一段时间学习和总结的方向开了一个头,结合 《STL源码剖析》 和 《Effective STL》 这 2 本书,系统的学习 STL
使用和实现中的技巧,所以要个赞,不过分吧~