怎样给自定义的类实现一个迭代器？解决方法
怎样给自定义的类实现一个迭代器？
类似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;
类似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;