怎样给自定义的类实现一个迭代器？
类似vector <typename> ::iterator 的
哪里能找到文章，或者直接教我吧:)
[解决办法]
STL中迭代器的实现
junguo
最近在看候捷先生的《STL源码剖析》，侯先生写的挺好的。但我读起来总感觉有些拗，理解起来有些费劲，可能他看问题的观点和我不一样造成的。开始的时候总是不太理解，后来理顺了自己的思路，发现有些东西其实并不难。在此把我对迭代器的理解整理一下，也是帮助自己消化一下，因为我发现不动手，很多东西容易遗忘。
文章里提供的一些例子程序是在Dev-C++ 4.9.9.0中编译的，该版编译器使用的是GNU C++ 3.3.1版本的类库，该代码在其它版本上以及其它编译器中可能无法通过。3.3.1版本中的STL改进了一些内容，例如安全检查一类的东西，虽说使用上更保险。但也增加了理解的困难，所以我在源代码的摘取上参考了侯先生网站上提供的sgi-stl-2.91.57版本的内容，GUN的3.3.1其实也是在sgi-stl版本的基础上改进的。源代码可以在Dev-C++的安装目录的include/c++/3.3.1下找到，多是以stl_开头的（如 list的实现文件是stl_list.h）。
STL中为我们提供的最重要的两个内容是容器（vector，list等）和一系列的算法。在这些算法中有许多需要遍历容器中的所有元素，如 search，sort等算法。STL的设计者希望将算法和容器分离开来，一个算法可以帮不同的容器实现功能。为此目的，STL应用到了《设计模式》中提到的迭代器模式。
《设计模式》中将迭代器模式定义为：提供一种方法，使之能依序遍历容器中的每个元素，而不需要暴露容器内部的信息。在面向对象的设计里，实现迭代器，我们会为所有的迭代器提供一个统一的接口，然后更个容器的迭代器继承这个接口，然后在使用处通过接口来实现对不同迭代器的调用。但STL是采用泛型思维，利用摸版来实现的类库，所以它的迭代器的实现和面向对象稍有不同，但原理类似。在此将通过例子来具体看看STL中迭代器的实现。
我们先来看看find()函数的实现：
//摘自stl_algo.h
template <typename _InputIter, typename _Tp>
inline _InputIter
find(_InputIter __first, _InputIter __last,
const _Tp& __val,
input_iterator_tag)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}
find()函数的功能是在一个容器中查找一个元素，需要遍历两个迭代器对象_first和_last所在的区间。在此我们看到它对区间的遍历是通过++ __first来实现的。也就是说迭代器需要重载++运算符来实现对容器的遍历。来具体看看vector和list中的迭代器实现。
我们知道vector中的元素是连续存放的，类似于数组，在数组中可以通过指针很容易的实现对数组的遍历，在vector中也一样，并不需要提供给它专门的迭代器类，通过指针就可以实现迭代器的功能。看看例子：
#include <iostream>
#include <vector>
using namespace std;
template <typename _InputIter, typename _Tp>
inline _InputIter
myfind(_InputIter __first, _InputIter __last,
const _Tp& __val)
{
while (__first != __last && !(*__first == __val))
++__first;
return __first;
}
int main()
{
vector <int> vec;
for( int i = 0; i < 10 ; i ++ )
vec.push_back(i);
int *p0 = &vec[0];
int *p1 = &vec[10];
int *p2 = myfind(p0,p1,6);
if ( p2 != &vec[10])
cout < < *p2 < < endl;
system( "pause ");
return 0;
}
例子中，我对find做了改动，改成了myfind，这是因为3.3.1的源代码中加入了traits技巧（在VC中我们是可以直接用find的），稍后我们将讲到该问题。但这里可以看到，通过指针就可以实现对vector的遍历。一般我们对迭代器的使用是如下的方式：
vector <int> ::iterator it;
这里需要借助vector来定义迭代器，这里主要是为容器的使用提供一种统一的方式。因为list容器不能通过指针来实现遍历，它们需要实现自己的迭代器。我们来看看在vector中对于iterator的实现：
template <typename T,class Alloc = alloc >
class vector
{
public:
typedef T value_type;
typedef value_type* iterator;
...
};
在此可以看到iterator在vector中也只是简单的被定义成了我们传入的类型参数T的指针（在3.3.1的代码中与这里的代码并不一样，还是traits的原因）。我们使用迭代器的一般方式是如下：
find(vec.begin(),vec.end,6);
再简单看看begin和end函数的实现：
template <typename T,class Alloc = alloc >
class vector
{
proteted:
iterator start;
iterator finist;
public:
iterator begin(){return start;}
iterator end(){return end;}
...
};
这里可以看到，只是为vector设置一个头指针和尾指针，然后通过begin和end来得到这两个指针。
list就不可以直接通过指针来实现迭代器了，因为它里面的元素是不连续的。需要我们自己去实现，我们先把list的定义抽出来看看。
template <class _Tp >
struct _List_node {
_List_node < _Tp> * _M_next;
_List_node < _Tp> * _M_prev;
_Tp _M_data;
};
template <class _Tp, class Alloc = alloc>
class list {
protected:
_List_nod <_Tp> e* node;
....
public:
void push_front(const _Tp & x);
void push_back(const _Tp & x);
....
};
为了便于理解，我将代码进行了简单的修改，事实上3.3.1里的代码要比这个要复杂一些。一般来说设计一个链表，我们会把它分成两部分： _List_node用来存放数据，list用来操作链表。这样，迭代器实际传回的应该是_List_node，当它向前遍历的时候，传回的应该是它的下一个结点。按着这个结构，为链表来设计一个迭代器，如下：
template <class T>
struct __list_iterator {
_List_node <T> * node;
__list_iterator(_List_node <T> * x) : node(x) {}
__list_iterator() {}
bool operator==(const __list_iterator <T> & x) const { return node == x.node; }
bool operator!=(const __list_iterator <T> & x) const { return node != x.node; }
T& operator*() const { return (*node)._M_data; }
__list_iterator <T> & operator++() {
node = (_List_node <T> *)((*node)._M_next);
return *this;
}
__list_iterator <T> operator++(int) {
__list_iterator <T> tmp = *this;
++*this;
return tmp;
}
};
我们可以看到，迭代器中重载了==，！=，*，++等操作符，这是因为这些操作是在算法中经常要用到的操作符。看看myfind中实现，就可以明白：
while (__first != __last && !(*__first == __val))
++__first;
这里要用到两个迭代器的比较（__first != __last），所以我们需要重载等于运算符；迭代器中值的比较（*__first == __val），这时候比较的不再是迭代器，而是迭代器所包含的内容（这里是_List_node的对象），所以我们需要重载*来得到它；最重要的就是遍历的实现，需要重载++运算符，这里是通过node = (_List_node <T> *)((*node)._M_next);将迭代器中的_List_node对象改为它的下一个对象来实现的。这样我们就完成了迭代器的设计。再来看看它的用法：
int main(int argc, char *argv[])
{
list <int> mylist;
for(int i = 0;i <= 10; i++ )
{
mylist.push_back(i);
}
// mylist.begin()得到的是STL本身提供的迭代器，所以我们需要得到它所包含的_List_node <T> 对象指针。
_List_node <int> * p1 = (_List_node <int> *)mylist.begin()._M_node;
_List_node <int> * p2 = (_List_node <int> *)mylist.end()._M_node;
//这里用我们得到的指针来生成我们自己的迭代器
__list_iterator <int> it1(p1);
__list_iterator <int> it2(p2);
__list_iterator <int> it3 = myfind(it1,it2,6);
if ( it3 != it2 )
cout < < *it3 < < endl;
system( "PAUSE ");
return 0;
}
实际的迭代器的设计中，还会重载--和-> 运算符，感兴趣的可以自己看看源代码。还是和vector一样，STL会把迭代器的定义绑定到list类中去，我们来看看它的具体做法：
typedef _list_iterator <_Tp> iterator;
其实和vector一样，只要把以上的定义放到list类中，就可以了，然后，我们就可以通过list <int> ::iterator ite 来定义list的迭代器了，事实上它生成的就是一个_list_iterator <int> 对象。
从此可以看到迭代器就是为各个容器生成一个可以迭代自身的类，而再通过typedef来把该迭代类绑定到容器类中，这样就给了外部一个形式统一的使用方法。
