C++中的迭代器给容器的操作带来了极大的便利性,可以使用迭代器方便的实现容器的多种操作,还提供了对不同容器之间的统一算法的支持。在coolshell上看到如何用迭代器实现二叉树的中序遍历,并且正想温习下C++中迭代器的实现,并查找资料,学习了下C++中迭代器实现的标准方式,自己尝试写下了二叉树的中序遍历代码。
这篇文章的内容参考于下面两篇博文,再看下面的内容之前,先阅读这两篇文章可以加深理解:
之前自己也写过一篇文章,关于二叉树的遍历的多种实现方式,有递归,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
2
3
4
5
注意:
1.迭代器的构造函数,可以完成从link_type类型的数据到迭代器的隐式转换 2.在二叉树的遍历过程中,++操作符需要让迭代器中的link_type node指向++操作后的节点 3.这个实现中有大量的typedef,其中还混杂了typename,关于template中的typename与classs的区别,也体现出来了,typename多一功能,可以用在嵌套的从属命名规则中,参考Effective C++的条款42:了解typename的双重意义 4.迭代器中一个重要的概念是迭代器超尾,这其中的超尾使用的是NULL空指针来控制的。 5.代码中混在了大量没用到的typedef,只是想保留C++中实现迭代器的原貌,更清晰的源码参考前面给出的第二个链接。