sundayhut's Blog

本文参考一下的博客：

http://blog.csdn.net/yxysdcl/article/details/5567460

迭代器实现了容器中对象的访问方法。迭代器就如同一个指针，其实指针也就是特殊的迭代器。下面看两个小例子帮助理解：

1.简单变量类型迭代器

一下是vector类型的简单实现

template <class T>
class vector {
private:
	T* pbegin;
	int n; //当前大小
public:
	vector() {
		pbegin = new T[100]; //暂时先固定大小
		n = 0;
	}
	
	T* begin() {
		return pbegin;
	}
	void insert(T d){
		pbegin[n++] = d;
	}
	typedef T* iterator; //vector的迭代器就是基础指针类型
};

vector是数组的实现，故由首地址可以知道后面元素的位置，故访问vector迭代器，其实就是基础指针，可以通过++,--操作

下面为测试操作

//测试vector
	vector<int> a;
	a.insert(1);
	a.insert(2);
	vector<int>::iterator itra;
	itra = a.begin();
	printf("%d/n", *itra); 
	itra++;
	printf("%d/n", *itra);
	itra--; //基础指针类型都支持++,--,+,-等操作符
	printf("%d/n", *itra);

2.链表类型的迭代器。

链表每个元素在不同位置，那怎么设计迭代器，使得它也可以通过++/--等操作实现定位呢？一下为例子

template <class T>
class List{
private:
	struct Node{ //链表的节点
		T data;
		Node* next;
	};
	Node* pbegin; //表头
	class List_iterator{ //链表的迭代器
		Node* cur; //当前指向
	public:
		void operator = (Node* ptr) {
			cur = ptr;
		}
		void operator ++ () {
			cur = cur->next;
		}
		// ...还可以重载-- + -等操作符
		T operator * (){
			return cur->data;
		}
	};
public :
	List() {
		pbegin=NULL;
	}
	Node* begin() {
		return pbegin;
	}
	void insert(T d) {
		Node* p=pbegin;
		while(p && p->next) p=p->next;
		Node* t = new Node;
		t->data = d;
		t->next = NULL;
		if(pbegin==NULL)
			pbegin = t;
		else
			p->next = t;
	}
	typedef List_iterator iterator; //List的迭代器是一个类
};

如上面代码，即对++操作进行了重载。测试代码如下

/测试List
	List<int> b;
	b.insert(1);
	b.insert(2);
	List<int>::iterator itrb;
	itrb = b.begin();
	printf("%d/n", *itrb);
	itrb++; // 该迭代器只支持++
	printf("%d/n", *itrb);

由此我们可以看出迭代器的目的，即通过迭代器，更方便的便利访问容器里的元素。这样在STL设计算法时，可以脱离容器设计更加通用的算法。如，容器中查找一个元素一般是遍历整个集合，如果没有迭代器，需要为vector和list设计两个查找算法。

总结；

模板：将算法和特定的数据类型分离

迭代器：将算法和特定的容器分离