设计模式之迭代器模式
迭代器模式就是一种在不暴露集合底层结构形式（数组、队列、栈、链表、树等）的情况下提供的获取、遍历集合元素的方法，比如我们需要遍历一个树可以采用深度优先(DFS)或广度优先 (BFS)搜索算法，如下图：
这样我们在遍历时就需要考虑算法的实现，所以如果我们在容器类中提供一些简单访问接口，并提供不同迭代器去调用接口实现不同的遍历，这样对于迭代器的使用这就会显得非常简单，因为他不用去考虑底层结构，只需要使用迭代器统一接口就可以完成不同的遍历。
下面是传统迭代器模式的UML图：
常见的迭代器实现使用可参考C++的STL中各种容器类中迭代器的实现或者Qt中容器迭代器模式(Qt里既有STL风格的迭代器实现也有Java风格的迭代器实现)。下面就是Qt中QListIterator和QMapIterator迭代器类的使用例子截图：
这是Qt中提供的Java风格的迭代器，我们可以发现我们遍历不同的数据结构使用的方法确大同小异，使用起来就方便多了（因为无需考虑底层算法的实现了），有更好的封装性，但随之产生的缺点就是当与某些简单集合(数组、有序列表等)，使用迭代器的方式就没直接遍历来得简单同时效率也因为结构的复杂而降低，这也就印证了人们常说的一个人的优点可能就是他的缺点，而他的缺点也可能正是他的优点。
我们可以参考上面迭代器类的使用为C++中list实现一个Java风格的迭代器类使用，这种实现方式与使用较为简单，下面是具体代码操作：
1. 抽象迭代器接口类定义（传统迭代器模式实现需要定义）
template<typename T>
class Iterator
{
public:
virtual const T &next() = 0;
virtual bool hasNext() = 0;
};
2. 具体迭代器类定义：ListIterator
#include "iterator.h"
#include <list>
template<typename T>
class ListIterator : public Iterator<T>
{
public:
//这里是直接利用stl中的迭代器进行容器元素定位的，注意这里与平时使用typedef不同，这必须添加关键字typename，否则编译会出错
typedef typename std::list<T>::const_iterator iter_t;
//由于当前迭代器是专为对应的list容器设计的，所以这里需要提供一个可以通过list构造的接口，用于初始化迭代器相关成员
ListIterator(const std::list<T> &lst)
{
m_plst = &lst;
m_it = m_plst->begin();
}
//用于返回当前迭代器位置容器里的元素，并使迭代器定位到下一个元素位置
inline const T &next()
{
const T &node = *m_it;
m_it++;
return node;
}
//用于遍历判断是否结束
inline bool hasNext()
{
if(m_it != m_plst->end()) {
return true;
}
return false;
}
protected:
const std::list<T> *m_plst;
iter_t m_it;
};
这里实现ListIterator中使用了stl中list自带的iterator的原因是基于C++中list提供的操作接口决定，因为我们是直接为它另外实现一个迭代器遍历模型，这里面不可避免会访问其任意位置的元素，而C++中list提供的可以访问到任意元素位置的就是它自带的迭代器。
3. 主函数功能测试代码
#include <iostream>
//#include <list>
#include "listIterator.h"
using namespace std;
int main()
{
list<int> ilist;
ilist.push_back(10);
ilist.push_back(20);
ilist.push_back(30);
ListIterator<int> listIter(ilist);
while(listIter.hasNext())
{
cout << "memb " << listIter.next();
cout << endl;
}
return 0;
}
程序运行结果：
上面代码我们选用的泛型编程，细心的朋友会发现这里写的跟UML图中的迭代器模式结构有些不一样(没有实现集合类Collection)，这是因为为了结构简单具体集合类我在这里是直接使用的C++里的list，所以集合类Collection就没有去单独实现了；另外这里其实也可以不用定义Iterator这个抽象类，直接编写一个模板类ListIterator即可；我们实现不同迭代器的目的就是灵活实现不同的容器遍历方式，如果按传统的实现通过抽象类提供统一接口调用，这样就会涉及到多态中虚函数调用，带来性能成本的增加，这里写上的原因是为了与前面迭代器模式的UML图结构对应。下面再给大家提供一个STL中list的简单实现来看看C++中list自带的iterator的实现，这里需重新实现了list所以代码相对较多，list实现就主要参考双向循环链表的写法，这里配合上模板使用即可，具体代码如下：
#include <iostream>
#include <string>
using namespace std;
//用于构建双向循环链表的模板节点定义
template <class T>
struct list_node //这里也可以用class，只需注意权限即可
{
T memb;
list_node *next = this;
list_node *prev = this;
};
//用模板实现的一个针对list遍历的迭代器类，这里只实现部分接口，仅供参考
template <typename T> class mylist; //声明mylist模板类
template <typename T>
class list_iterator
{
public:
typedef list_node<T> * node_pointer;
typedef list_iterator<T> iterator;
//迭代器重载* 、->、!=、++等操作符的定义
T &operator *()
{
return ptr->memb; //返回节点中存放的元素成员
}
T *operator ->()
{
return &ptr->memb; //返回节点中存放的元素成员的地址
}
// !=重载用于迭代器遍历时退出条件的判断
bool operator !=(const iterator &it)
{
if(ptr == it.ptr)
return false;
return true;
}
// ++操作符的重载用于实现迭代器遍历定位链表的下一个节点位置
const iterator operator++(int)
{
iterator it(*this);
++(*this);
return it;
}
iterator &operator++()
{
ptr = ptr->next;
return *this;
}
private:
node_pointer ptr; //指向链表节点的指针，用于定位节点使用
friend class mylist<T>; //将mylist类声明为友元类，方便下面mylist类调用iterator的私有及受保护成员
};
//模板类mylist，用于提供用户利用list_node构建双向循环链表操作的接口
template <typename T> class mylist
{
public:
typedef list_node<T> node;
typedef list_iterator<T> iterator;
//构造时就初始化链表
mylist()
{
list_size = 0;
head = new node;
}
//析构时销毁链表
~mylist()
{
node *t = head;
node *del;
while(t->next != nullptr) {
del = t;
t = del->next;
del->prev->next = del->next;
del->next->prev = del->prev;
del->next = nullptr;
del->prev = nullptr;
// cout << "delete node " << del->memb << endl;
free(del);
del = nullptr;
}
}
//链表尾插操作接口
void push_back(const T &t)
{
insert(end(), t);
}
//链表头插操作接口
void push_front(const T &t)
{
insert(begin(), t);
}
//在迭代器指定位置前插入新的节点操作
void insert(iterator pos, const T &value)
{
node *n = new node;
node *t = pos.ptr;
n->memb = value;
t->prev->next = n;
n->prev = t->prev;
n->next = t;
t->prev = n;
list_size++;
}
//begin()和end()用于返回链表第一个节点和尾节点下一个节点(头节点)定位的迭代器，即开始位置及结束位置
iterator begin()
{
iterator it;
it.ptr = head->next;
return it;
}
iterator end()
{
iterator it;
it.ptr = head;
return it;
}
//用于获取链表节点个数
inline int size()
{
return list_size;
}
private:
node *head; //指向双向循环链表头节点的指针
size_t list_size;
};
//主函数测试代码
int main()
{
mylist <string> lt;
lt.push_back("three");
lt.push_back("four");
lt.push_front("two");
lt.push_front("one");
//模拟STL中迭代器使用遍历mylist
mylist <string>::iterator it;
for(it = lt.begin(); it != lt.end(); it++) {
cout << *it << endl;
}
return 0;
}
程序运行结果：
上面就是参考C++及Qt容器中迭代器使用而实现的迭代器模式，仅供学习参考。
