C++ 迭代器的简单实现

C++中迭代器的简单实现，以及使用迭代器实现二叉树的中序遍历

C++中的迭代器给容器的操作带来了极大的便利性，可以使用迭代器方便的实现容器的多种操作，还提供了对不同容器之间的统一算法的支持。在coolshell上看到如何用迭代器实现二叉树的中序遍历，并且正想温习下C++中迭代器的实现，并查找资料，学习了下C++中迭代器实现的标准方式，自己尝试写下了二叉树的中序遍历代码。

这篇文章的内容参考于下面两篇博文,再看下面的内容之前，先阅读这两篇文章可以加深理解：

1.coolshell 二叉树迭代器算法 2.STL源码剖析，迭代器

之前自己也写过一篇文章，关于二叉树的遍历的多种实现方式，有递归，stack方式，morris算法，每种方式实现的前中后遍历。

二叉树的多种遍历

二叉树的迭代器实现

在C++中使用某种迭代器，一般都是采用这样的方式：

std::list<int>::iterator iter = oneList.begin();

这个语句告诉我迭代器在容器中以某种方式定义着，还有对于通用算法，find等，对不同容器都是统一处理的，我们知道不同的容器，可能拥有的迭代器类型不尽相同，输入迭代器输出迭代器，前向，随机，双向迭代器。不同的迭代器的性质也不完全相同。因此，对于某个容器，需要知道它所支持的迭代器类型，方便通用算法能对不同的容器采用合适的方法。

typedef forward_iterator_tag iterator_category;

上面这条语句，就定义了一个前向的迭代器。关于通用算法处理不同类型的迭代器方式，可以参考Effective C++中的条款47，请使用traits classb表现类型信息。

在编写下面二叉树的迭代器遍历过程中，主要从下面的几点来思考的：

1.容器包含多个元素，BinaryTree则包含多个节点 2.迭代器在任何时刻包含一个当前指向的元素,这样可以通过* 和->访问元素信息 3.可以由元素到迭代器的隐性转换，利用单参数的构造元素的特性完成转换 4.二叉树的迭代器遍历是模仿递归中的方式，通过stack保存左子树，可以参考上面给出的链接，现在只需要将stack移到迭代器中来，方便的实现迭代器的前进。

上面这四点都会体现在代码当中。

具体代码

#include<iostream>
#include<stack>

using namespace std;

template<typename T>
struct __tree_node{
    typedef __tree_node* pointer;
    pointer left;
    pointer right;
    T data;
    __tree_node(T t,pointer lchild = NULL,pointer rchild = NULL){
        data = t;
        left = lchild;
        right = rchild;
    }
};

template<class T,class Ref, class Ptr>
class __tree_iterator{
public:
    typedef __tree_iterator<T,T&,T*>    iterator;
    typedef __tree_iterator<T,const T&,const T*>    const_iterator;
    typedef __tree_iterator<T,Ref,Ptr>  self;

    typedef forward_iterator_tag iterator_category;

    typedef T value_type; 
    typedef Ptr pointer;
    typedef Ref reference;
    typedef __tree_node<T>* link_type;
    typedef size_t size_type;

    link_type node;

    __tree_iterator(link_type x);
    __tree_iterator(){}
    __tree_iterator(const iterator& x);

    bool operator==(const self& x)const{return node == x.node;}
    bool operator!=(const self& x)const{return node != x.node;}
    
    reference operator*(){return (*node).data;}
    pointer operator->(){return &(operator*());}
    
    self& operator++();

private:
    std::stack<link_type> stack;
};

template<class T, class Ref,class Ptr>
__tree_iterator<T,Ref,Ptr>& __tree_iterator<T,Ref,Ptr>::operator++(){
    if(stack.empty()){
        node = NULL;
        return *this;
    }
    stack.pop();
    if(node->right != NULL){
        link_type temp = node->right;
        while(temp != NULL){
            stack.push(temp);
            temp = temp->left;
        }
    }
    if(stack.empty()){
        node = NULL;
    }else{
        node = stack.top();
    }
    // we should return an iterator pointing to next element;
    return *this;
}

template<class T, class Ref,class Ptr>
__tree_iterator<T,Ref,Ptr>::__tree_iterator(link_type x){
    if(x == NULL){
        node = NULL;
        return;
    }
    stack.push(x);
    node = x;
    while(x->left != NULL){
        stack.push(x->left);
        x = x->left;
        node = x;
    }
}

template<class T, class Ref,class Ptr>
__tree_iterator<T,Ref,Ptr>::__tree_iterator(const iterator& x){
    node = x.node;
    stack = x.stack;
}

template<class T>
class BinaryTree{
public:
    typedef __tree_iterator<T,T&,T*> iterator;
    //typedef __tree_iterator<T,const T&,const T*> const_iterator;
    typedef typename __tree_iterator<T,T&,T*>::link_type link_type;

protected:
    link_type root;

public:
    BinaryTree();
    BinaryTree(link_type node);
    //void insert(T t);       

    // this function will call __tree__iterator' constructor function
    iterator begin();//{return root;}
    iterator end();//{return iterator(NULL);}
};

template<class T>
BinaryTree<T>::BinaryTree(){
    root = NULL;
}


template<class T>
BinaryTree<T>::BinaryTree(link_type node){
    root = node;
}

template<class T>
typename BinaryTree<T>::iterator BinaryTree<T>::begin(){
    return root;
}

template<class T>
typename BinaryTree<T>::iterator BinaryTree<T>::end(){
    return NULL;
}

int main(){
    __tree_node<int> one(2);
    __tree_node<int> two(3,&one);
    __tree_node<int> three(1,NULL,&two);
    __tree_node<int> four(5);
    __tree_node<int> root(4,&three,&four);

    BinaryTree<int> binarytree(&root);
    BinaryTree<int>::iterator iter = binarytree.begin();
    while(iter != binarytree.end()){
        cout << *iter << endl;
        ++iter;
    }
    return 0;
}

运行结果如下：

注意：

1.迭代器的构造函数，可以完成从link_type类型的数据到迭代器的隐式转换 2.在二叉树的遍历过程中，++操作符需要让迭代器中的link_type node指向++操作后的节点 3.这个实现中有大量的typedef，其中还混杂了typename，关于template中的typename与classs的区别，也体现出来了，typename多一功能，可以用在嵌套的从属命名规则中，参考Effective C++的条款42：了解typename的双重意义 4.迭代器中一个重要的概念是迭代器超尾，这其中的超尾使用的是NULL空指针来控制的。 5.代码中混在了大量没用到的typedef，只是想保留C++中实现迭代器的原貌，更清晰的源码参考前面给出的第二个链接。

前一篇: Openstack Network学习(一) 后一篇: C++ 构造智能指针