在设计模式中，迭代器的定义如下：提供一种方法能够依次访问聚合元素而又无需暴露内部的表达方式。由于STL标准库中的设计将容器与算法相互分隔开，迭代器扮演之间的粘合剂。

一、设计原理

STL中迭代器为智能指针（smart pointer），指针具有的行为有->和*，因此迭代器会重载operator->和operator*。STL中有个auto_ptr原生指针可供参考学习。

二、auto_ptr

auto_ptr作为C++中智能指针类的模板，实现原理为RAII（资源获取即初始化），在构造的时候资源获取，在析构的时候释放资源，常用来管理内存，避免内存泄漏。但是auto_ptr依旧有许多缺陷，如：不能避免使用两个auto_ptr指向同一对象，这样释放一个对象的资源后，另一个指针会成为悬浮指针。还有不能用auto_ptr管理数组指针，因为auto_ptr析构中调用delete，而不是delete[]。

头文件：#include<memory.h>

源码：

template <class _Tp> class auto_ptr {
private:_Tp* _M_ptr;//定义一个私有指针public:typedef _Tp element_type;explicit auto_ptr(_Tp* __p = 0) __STL_NOTHROW : _M_ptr(__p) {}//构造函数，explicit防止隐式转换auto_ptr(auto_ptr& __a) __STL_NOTHROW : _M_ptr(__a.release()) {}#ifdef __STL_MEMBER_TEMPLATEStemplate <class _Tp1> auto_ptr(auto_ptr<_Tp1>& __a) __STL_NOTHROW: _M_ptr(__a.release()) {}
#endif /* __STL_MEMBER_TEMPLATES */auto_ptr& operator=(auto_ptr& __a) __STL_NOTHROW {//赋值运算符的重载if (&__a != this) {//两个对象不相同delete _M_ptr;//释放原有对象的资源_M_ptr = __a.release();//赋值}return *this;}#ifdef __STL_MEMBER_TEMPLATEStemplate <class _Tp1>auto_ptr& operator=(auto_ptr<_Tp1>& __a) __STL_NOTHROW {if (__a.get() != this->get()) {delete _M_ptr;_M_ptr = __a.release();}return *this;}
#endif /* __STL_MEMBER_TEMPLATES */~auto_ptr() { delete _M_ptr; }//析构函数_Tp& operator*() const __STL_NOTHROW {//运算符*的重载return *_M_ptr;}_Tp* operator->() const __STL_NOTHROW {//运算符->的重载return _M_ptr;}_Tp* get() const __STL_NOTHROW {//获取这个指针return _M_ptr;}_Tp* release() __STL_NOTHROW {//释放指针_Tp* __tmp = _M_ptr;_M_ptr = 0;return __tmp;}void reset(_Tp* __p = 0) __STL_NOTHROW {//重置指针if (__p != _M_ptr) {delete _M_ptr;_M_ptr = __p;}}#if defined(__SGI_STL_USE_AUTO_PTR_CONVERSIONS) && \defined(__STL_MEMBER_TEMPLATES)public:auto_ptr(auto_ptr_ref<_Tp> __ref) __STL_NOTHROW//拷贝函数: _M_ptr(__ref._M_ptr) {}auto_ptr& operator=(auto_ptr_ref<_Tp> __ref) __STL_NOTHROW {//赋值运算符重载if (__ref._M_ptr != this->get()) {//两个对象不相同delete _M_ptr;//释放原有对象的资源_M_ptr = __ref._M_ptr;//赋值}return *this;}template <class _Tp1> operator auto_ptr_ref<_Tp1>() __STL_NOTHROW { return auto_ptr_ref<_Tp1>(this->release()); }template <class _Tp1> operator auto_ptr<_Tp1>() __STL_NOTHROW{ return auto_ptr<_Tp1>(this->release()); }#endif /* auto ptr conversions && member templates */
};__STL_END_NAMESPACE#endif /* __SGI_STL_MEMORY */

三、迭代器

五种迭代器类型：

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

源码：

（1）迭代器类型的定义：

template <class _Tp, class _Distance> struct input_iterator {typedef input_iterator_tag iterator_category;typedef _Tp                value_type;typedef _Distance          difference_type;typedef _Tp*               pointer;typedef _Tp&               reference;
};struct output_iterator {typedef output_iterator_tag iterator_category;typedef void                value_type;typedef void                difference_type;typedef void                pointer;typedef void                reference;
};template <class _Tp, class _Distance> struct forward_iterator {typedef forward_iterator_tag iterator_category;typedef _Tp                  value_type;typedef _Distance            difference_type;typedef _Tp*                 pointer;typedef _Tp&                 reference;
};template <class _Tp, class _Distance> struct bidirectional_iterator {typedef bidirectional_iterator_tag iterator_category;typedef _Tp                        value_type;typedef _Distance                  difference_type;typedef _Tp*                       pointer;typedef _Tp&                       reference;
};template <class _Tp, class _Distance> struct random_access_iterator {typedef random_access_iterator_tag iterator_category;typedef _Tp                        value_type;typedef _Distance                  difference_type;typedef _Tp*                       pointer;typedef _Tp&                       reference;
};

（2）迭代器萃取机

#ifdef __STL_USE_NAMESPACES
template <class _Category, class _Tp, class _Distance = ptrdiff_t,class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {                             //为避免代码重复以及缺漏，自定义迭代器应该继承该迭代器typedef _Category  iterator_category;       //迭代器移动特性及可执行操作typedef _Tp        value_type;              //迭代器所指对象的类别typedef _Distance  difference_type;        //两个迭代器之间的距离typedef _Pointer   pointer;                 //迭代器所指对象typedef _Reference reference;               //迭代器所指对象的引用
};
#endif /* __STL_USE_NAMESPACES */#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtemplate <class _Iterator>
struct iterator_traits {                   //迭代器萃取机：获得迭代器特性typedef typename _Iterator::iterator_category iterator_category;typedef typename _Iterator::value_type        value_type;typedef typename _Iterator::difference_type   difference_type;typedef typename _Iterator::pointer           pointer;typedef typename _Iterator::reference         reference;
};template <class _Tp>
struct iterator_traits<_Tp*> {             //针对原生指针设计的偏特化版typedef random_access_iterator_tag iterator_category;typedef _Tp                         value_type;typedef ptrdiff_t                   difference_type;typedef _Tp*                        pointer;typedef _Tp&                        reference;
};template <class _Tp>                  //针对const的原生指针设计的偏特化版
struct iterator_traits<const _Tp*> {typedef random_access_iterator_tag iterator_category;typedef _Tp                         value_type;typedef ptrdiff_t                   difference_type;typedef const _Tp*                  pointer;typedef const _Tp&                  reference;
};

（3）获得迭代器特性

template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)           //获得某个迭代器的类型
{typedef typename iterator_traits<_Iter>::iterator_category _Category;return _Category();
}template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
__distance_type(const _Iter&)             //决定某个迭代器的different_type
{return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)                 //决定某个迭代器的value_type
{return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
}

（4）获取迭代器的空间

template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last, //InputIterator_Distance& __n, input_iterator_tag)
{while (__first != __last) { ++__first; ++__n; }
}template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first,                //RandomAccessIterator_RandomAccessIterator __last, _Distance& __n, random_access_iterator_tag)
{__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);__n += __last - __first;
}template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first, _InputIterator __last, _Distance& __n)
{__STL_REQUIRES(_InputIterator, _InputIterator);__distance(__first, __last, __n, iterator_category(__first));
}#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtemplate <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{typename iterator_traits<_InputIterator>::difference_type __n = 0;while (__first != __last) {++__first; ++__n;}return __n;
}template <class _RandomAccessIterator>
inline typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,random_access_iterator_tag) {__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);return __last - __first;
}template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last) {typedef typename iterator_traits<_InputIterator>::iterator_category _Category;__STL_REQUIRES(_InputIterator, _InputIterator);return __distance(__first, __last, _Category());
}#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */