Iterator

一、概述Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。由于Iterator模式的以上特性：与聚合对象耦合，在一定程度上限制了它的广泛运用，一般仅用于底层聚合支持类，如STL的list、vector、stack等容器类及ostream_iterator等扩展iterator。根据STL中的分类，iterator包括：Input Iterator：只能单步向前迭代元素，不允许修改由该类迭代器引用的元素。Output Iterator：该类迭代器和Input Iterator极其相似，也只能单步向前迭代元素，不同的是该类迭代器对元素只有写的权力。Forward Iterator：该类迭代器可以在一个正确的区间中进行读写操作，它拥有Input Iterator的所有特性，和Output Iterator的部分特性，以及单步向前迭代元素的能力。Bidirectional Iterator：该类迭代器是在Forward Iterator的基础上提供了单步向后迭代元素的能力。Random Access Iterator：该类迭代器能完成上面所有迭代器的工作，它自己独有的特性就是可以像指针那样进行算术计算，而不是仅仅只有单步向前或向后迭代。这五类迭代器的从属关系，如下图所示，其中箭头A→B表示，A是B的强化类型，这也说明了如果一个算法要求B，那么A也可以应用于其中。
图1、五种迭代器之间的关系vector和deque提供的是RandomAccessIterator，list提供的是BidirectionalIterator，set和map提供的iterators是 ForwardIterator，关于STL中iterator的更多信息，请阅读参考1或2。二、结构Iterator模式的结构如下图所示：
二、结构Iterator模式的结构如下图所示：
图2、Iterator模式类图示意三、应用Iterator模式有三个重要的作用：1）它支持以不同的方式遍历一个聚合 复杂的聚合可用多种方式进行遍历，如二叉树的遍历，可以采用前序、中序或后序遍历。迭代器模式使得改变遍历算法变得很容易: 仅需用一个不同的迭代器的实例代替原先的实例即可，你也可以自己定义迭代器的子类以支持新的遍历，或者可以在遍历中增加一些逻辑，如有条件的遍历等。2）迭代器简化了聚合的接口 有了迭代器的遍历接口，聚合本身就不再需要类似的遍历接口了，这样就简化了聚合的接口。3）在同一个聚合上可以有多个遍历 每个迭代器保持它自己的遍历状态，因此你可以同时进行多个遍历。4）此外，Iterator模式可以为遍历不同的聚合结构（需拥有相同的基类）提供一个统一的接口，即支持多态迭代。简单说来，迭代器模式也是Delegate原则的一个应用，它将对集合进行遍历的功能封装成独立的Iterator，不但简化了集合的接口，也使得修改、增加遍历方式变得简单。从这一点讲，该模式与Bridge模式、Strategy模式有一定的相似性，但Iterator模式所讨论的问题与集合密切相关，造成在Iterator在实现上具有一定的特殊性，具体将在示例部分进行讨论。四、优缺点正如前面所说，与集合密切相关，限制了Iterator模式的广泛使用，就个人而言，我不大认同将Iterator作为模式提出的观点，但它又确实符合模式“经常出现的特定问题的解决方案”的特质，以至于我又不得不承认它是个模式。在一般的底层集合支持类中，我们往往不愿“避轻就重”将集合设计成集合 + Iterator的形式，而是将遍历的功能直接交由集合完成，以免犯了“过度设计”的诟病，但是，如果我们的集合类确实需要支持多种遍历方式（仅此一点仍不一定需要考虑Iterator模式，直接交由集合完成往往更方便），或者，为了与系统提供或使用的其它机制，如STL算法，保持一致时，Iterator模式才值得考虑。五、举例可以考虑使用两种方式来实现Iterator模式：内嵌类或者友元类。通常迭代类需访问集合类中的内部数据结构，为此，可在集合类中设置迭代类为friend class，但这不利于添加新的迭代类，因为需要修改集合类，添加friend class语句。也可以在抽象迭代类中定义protected型的存取集合类内部数据的函数，这样迭代子类就可以访问集合类数据了，这种方式比较容易添加新的迭代方式，但这种方式也存在明显的缺点：这些函数只能用于特定聚合类，并且，不可避免造成代码更加复杂。STL的list::iterator、deque::iterator、rbtree::iterator等采用的都是外部Iterator类的形式，虽然STL的集合类的iterator分散在各个集合类中，但由于各Iterator类具有相同的基类，保持了相同的对外的接口（包括一些traits及tags等，感兴趣者请认真阅读参考1、2），从而使得它们看起来仍然像一个整体，同时也使得应用algorithm成为可能。我们如果要扩展STL的iterator，也需要注意这一点，否则，我们扩展的iterator将可能无法应用于各algorithm。以下是一个遍历二叉树的Iterator的例子，为了方便支持多种遍历方式，并便于遍历方式的扩展，其中还使用了Strategy模式（见笔记21）：（注：1、虽然下面这个示例是本系列所有示例中花费我时间最多的一个，但我不得不承认，它非常不完善，感兴趣的朋友，可以考虑参考下面的参考材料将其补充完善，或提出宝贵改进意见。2、我本想考虑将其封装成与STL风格一致的形式，使得我们遍历二叉树必须通过Iterator来进行，但由于二叉树在结构上较线性存储结构复杂，使访问必须通过Iterator来进行，但这不可避免使得BinaryTree的访问变得异常麻烦，在具体应用中还需要认真考虑。3、以下只提供了Inorder<中序>遍历iterator的实现。）

#include <assert.h>

#include <iostream>
#include <xutility>
#include <iterator>
#include <algorithm>
using namespace std;

template <typename T>
class BinaryTree;
template <typename T>
class Iterator;

template <typename T>
class BinaryTreeNode
{
public:
typedef BinaryTreeNode<T> NODE;
typedef BinaryTreeNode<T>* NODE_PTR;

BinaryTreeNode(const T& element) : data(element), leftChild(NULL), rightChild(NULL), parent(NULL) { }
BinaryTreeNode(const T& element, NODE_PTR leftChild, NODE_PTR rightChild)
:data(element), leftChild(leftChild), rightChild(rightChild), parent(NULL)
{
if (leftChild)
leftChild->setParent(this);
if (rightChild)
rightChild->setParent(this);
}

T getData(void) const { return data; }
NODE_PTR getLeft(void) const { return leftChild; }
NODE_PTR getRight(void) const { return rightChild; }
NODE_PTR getParent(void) const { return parent; }
void SetData(const T& data) { this->data = item; }
void setLeft(NODE_PTR ptr) { leftChild = ptr; ptr->setParent(this); }
void setRight(NODE_PTR ptr) { rightChild = ptr; ptr->setParent(this); }
void setParent(NODE_PTR ptr) { parent = ptr; }
private:
T data;
NODE_PTR leftChild;
NODE_PTR rightChild;
NODE_PTR parent; // pointer to parent node, needed by iterator

friend class BinaryTree<T>;
};

template <typename T>
ostream& operator << (ostream& os, const BinaryTreeNode<T>& node) { return os << node.getData(); }

template <typename T>
class BinaryTree
{
public:
typedef BinaryTreeNode<T> NODE;
typedef BinaryTreeNode<T>* NODE_PTR;
typedef Iterator<T> iterator;
enum ATTACHTYPE {LEFT, RIGHT};

BinaryTree() : root(NULL) {} // default ctor, create a null tree
BinaryTree(const T& elem) { // create a tree with a node
root = new NODE(elem);
}
BinaryTree(const T& elem, BinaryTree& leftTree, BinaryTree& rightTree) { // create a tree with root node(elem) and two sub trees
root = new NODE(elem, leftTree.root, rightTree.root);
leftTree.root = NULL;
rightTree.root = NULL;
}
virtual ~BinaryTree() { destroy(root); } // default dtor

NODE_PTR getRoot(void) const { return root; }

void detach(NODE_PTR current) { // detach a sub tree with current as root
if (NULL == current)
return;

NODE_PTR parent = root->getParent();
if (NULL == parent)
root = NULL;
else
(parent->leftChild == current) ? parent->leftChild = NULL : parent->rightChild = NULL;
}
bool attach(NODE_PTR current, BinaryTree& tree, ATTACHTYPE attachType = LEFT) {
NODE_PTR ptr = tree.getRoot();
// must detach a sub-tree, before attach it to a new tree
tree.detach(ptr);
return attach(current, ptr, attachType);
}
bool attach(NODE_PTR current, NODE_PTR pNewNode = NULL, ATTACHTYPE attachType = LEFT) {
assert(find(current)); // current must be a member of this tree
if (NULL == current) {
if (NULL == root) {
root = pNewNode;
return true;
}
else
return false;
}
else {
switch (attachType) {
case LEFT:
if (current->getLeft())
destroy(current->getLeft());
current->setLeft(pNewNode);
return true;
case RIGHT:
if (current->getRight())
destroy(current->getRight());
current->setRight(pNewNode);
return true;
default:
return true;
}
}
}
bool find(NODE_PTR node) {
if (root == node)
return true;
else if (find(root->leftChild, node))
return true;
else if (find(root->rightChild, node))
return true;
else
return false;
}
bool find(NODE_PTR start, NODE_PTR node) {
if (start == node)
return true;
else if (start == NULL)
return false;
else if (find(start->leftChild, node))
return true;
else if (find(start->rightChild, node))
return true;
else
return false;
}
NODE_PTR getLeftmost() {
return getLeftmost(root);
}
NODE_PTR getRightmost() {
return getRightmost(root);
}
static NODE_PTR getLeftmost(NODE_PTR node){
NODE_PTR ret = node;
NODE_PTR tmp = ret->getLeft();
for(;!(NULL==tmp);ret=tmp, tmp=ret->getLeft());
return ret;
}
static NODE_PTR getRightmost(NODE_PTR node){
NODE_PTR ret = node;
NODE_PTR tmp = ret->getRight();
for(;!(NULL==tmp);ret=tmp, tmp=ret->getRight());
return ret;
}
private:
NODE_PTR root; // root node of a binary tree
void destroy(NODE_PTR ptr) { // destroy a sub tree with node as root
if(ptr != NULL) {
destroy(ptr->getLeft());
destroy(ptr->getRight());
delete ptr;
}
}
};

template<typename T>
struct IteratorImp {
typedef BinaryTreeNode<T> NODE;
typedef BinaryTreeNode<T>* NODE_PTR;

virtual NODE_PTR next(NODE_PTR node) = 0;
virtual NODE_PTR prev(NODE_PTR node) = 0;
virtual NODE_PTR begin(NODE_PTR node) = 0;
};

template<typename T>
class Inorder: public IteratorImp<T> {
public:
NODE_PTR next(NODE_PTR p) {
return p == NULL ? NULL : goRight(p);
}
NODE_PTR prev(NODE_PTR p) {
return p == NULL ? NULL : goLeft(p);
}
NODE_PTR begin(NODE_PTR p) {
return p == NULL ? NULL : BinaryTree<T>::getLeftmost(p);
}
private:
NODE_PTR ret(NODE_PTR const me, NODE_PTR const from) {
if(isNull(me)) {
return me;
}
else if(me->getLeft()==from) {
return me;
}
else {
return goParent(me);
}
}
NODE_PTR goRight(NODE_PTR const node) {
NODE_PTR const right(node->getRight());
if(NULL==right) {
return goParent(node, true);
}
else{
return BinaryTree<T>::getLeftmost(right);
}
}
NODE_PTR goLeft(NODE_PTR const node) {
NODE_PTR const left(node->getLeft());
if(NULL==left) {
return goParent(node, false);
}
else{
return BinaryTree<T>::getRightmost(left);
}
}
NODE_PTR goParent(NODE_PTR const node, bool left) {
NODE_PTR me = node->getParent();
NODE_PTR from = node;
if(NULL==me) {
return me;
}
else if((left && (me->getLeft()==from)) || (!left && (me->getRight()==from))) {
return me;
}
else {
return goParent(me, left);
}
}
};

template<typename T>
class Iterator : public iterator<bidirectional_iterator_tag, T> {
public:
typedef BinaryTreeNode<T> NODE;
typedef BinaryTreeNode<T>* NODE_PTR;
enum TRAVERSETYPE {PREORDER, INORDER, POSTORDER, NULLTYPE};
Iterator(NODE_PTR p = NULL, TRAVERSETYPE tt = INORDER) : current(p), pImp(NULL), type(NULLTYPE) {
setTraverseType(tt);
}
Iterator(const Iterator& it) : current(it.current), pImp(NULL) {
setTraverseType(it.type);
}
virtual ~Iterator() {
if (pImp)
delete pImp;
}

NODE& operator*() { return *current; }
NODE_PTR operator->() { return current; }
Iterator& operator=(const Iterator& it) {
current = it.current;
setTraverseType(it.type);
return *this;
}
Iterator& operator++() {
if (pImp)
current = pImp->next(current);
return *this;
}
Iterator operator++(int) {
Iterator tmp = *this;
++*this;
return tmp;
}
Iterator operator--() {
if (pImp)
current = pImp->prev(current);
return *this;
}
Iterator operator--(int) {
Iterator tmp = *this;
--*this;
return tmp;
}
bool operator==(const Iterator& i) const { return current == i.current; }
bool operator!=(const Iterator& i) const { return current != i.current; }

void setTraverseType(TRAVERSETYPE tt) {
if (type != tt) {
if (pImp)
delete pImp;
type = tt;
switch (type) {
case PREORDER:
// not implemented yet
assert(false);
break;
case INORDER:
pImp = new Inorder<T>;
break;
case POSTORDER:
// not implemented yet
assert(false);
default:
assert(false);
break;
}
}
}
protected:
NODE_PTR current;
IteratorImp<T>* pImp;
TRAVERSETYPE type;

friend bool operator==(const Iterator& i, NODE_PTR p) { return i.current == p; }
friend bool operator!=(const Iterator& i, NODE_PTR p) { return i.current != p; }
};

int main()
{
BinaryTree<char*> t1("A");
BinaryTree<char*> t2("B");
BinaryTree<char*> t3("C", t1, t2);
BinaryTree<char*> t5("D");
BinaryTree<char*> t6("E");
BinaryTree<char*> t7("F", t5, BinaryTree<char*>());
BinaryTree<char*> t8("G", BinaryTree<char*>(), t6);
BinaryTree<char*> t4;
BinaryTreeNode<char*>* ptr = t3.getRoot();
t4.attach(t4.getRoot(), t3);
t4.attach(t4.getRightmost(), t8, BinaryTree<char*>::RIGHT);
t4.attach(t4.getRightmost(), t7);
// we get a tree
// C
// A B
// G
// E
// F
// D

BinaryTree<char*>::iterator it(t4.getLeftmost());
BinaryTree<char*>::iterator end;
copy(it, end, ostream_iterator<BinaryTreeNode<char*> >(cout, " "));
cout << endl;

it = t4.getRightmost();
for (; it != end; --it)
cout << *it << " ";
cout << endl;

return 0;
}

参考： 1、泛型指標（Iterators）與Traits技術：http://www.jjhou.com/runpc-stl-2.pdf
2、STL源码剖析，jjhou
3、与树实现无关的树iterator：http://www.allaboutprogram.com/bb/viewtopic.php?t=629&postdays=0&postorder=asc&start=0
4、一个Java版的BinaryTree实现（只找到文档，没有找到code）：http://www.cs.uno.edu/~c2125/csci/docs/overview-summary.html