一慨畸、概述

迭代器是c++中一種檢查容器內(nèi)元素并遍歷元素的數(shù)據(jù)類型伞梯。
迭代器提供對一個容器中的對象的訪問方法写隶，并且定義了容器中對象的范圍倔撞。
迭代器（Iterator）是指針（pointer）的泛化，它允許程序員用相同的方式處理不同的數(shù)據(jù)結(jié)構(gòu)（容器）慕趴。
每個容器定義了一種名為iterator的類型痪蝇，這種類型支持迭代器的各種行為。
迭代器模式是23種設(shè)計(jì)模式之一秩贰，迭代器模式提供一種方法順序訪問一個聚合對象中各個元素, 而又不需暴露該對象的內(nèi)部表示霹俺，使得我們可以在不知道對象內(nèi)部表示的情況下，按照一定順序訪問聚合對象中的各個元素毒费。

二丙唧、STL中迭代器的類型

Input Iterator：只能單步向前迭代元素，不允許修改由該類迭代器引用的元素觅玻。
Output Iterator：該類迭代器和Input Iterator極其相似想际，也只能單步向前迭代元素，不同的是該類迭代器對元素只有寫的權(quán)力溪厘。
Forward Iterator：該類迭代器可以在一個正確的區(qū)間中進(jìn)行讀寫操作胡本，它擁有Input Iterator的所有特性，和Output Iterator的部分特性畸悬，以及單步向前迭代元素的能力侧甫。
Bidirectional Iterator：該類迭代器是在Forward Iterator的基礎(chǔ)上提供了單步向后迭代元素的能力。
Random Access Iterator：該類迭代器能完成上面所有迭代器的工作，它自己獨(dú)有的特性就是可以像指針那樣進(jìn)行算術(shù)計(jì)算披粟，而不是僅僅只有單步向前或向后迭代咒锻。

這五類迭代器的從屬關(guān)系，如下圖所示守屉，其中箭頭A→B表示惑艇，A是B的強(qiáng)化類型，這也說明了如果一個算法要求B拇泛，那么A也可以應(yīng)用于其中滨巴。
input output
\ /
forward
|
bidirectional
|
random access

三、STL中迭代器的操作

對應(yīng)上述迭代器類型俺叭，歸納總結(jié)不同迭代器的操作：

image.png

四恭取、STL容器支持的迭代器類型

image.png

五、常用的迭代器函數(shù)

image.png

正向迭代器begin()從頭結(jié)點(diǎn)開始绪颖，end()指向末尾節(jié)點(diǎn)+1秽荤，反向迭代器方向相反甜奄。

image.png

六柠横、迭代器失效

容器的插入insert和erase操作可能導(dǎo)致迭代器失效，對于erase操作不要使用操作之前的迭代器课兄，因?yàn)閑rase的那個迭代器一定失效了牍氛，正確的做法是返回刪除操作時候的那個迭代器。

image.png

七烟阐、迭代器的輔助函數(shù)

STL 中有用于操作迭代器的三個函數(shù)模板搬俊，它們是：

• advance(p, n)：使迭代器 p 向前或向后移動 n 個元素。
• distance(p, q)：計(jì)算兩個迭代器之間的距離蜒茄，即迭代器 p 經(jīng)過多少次 + + 操作后和迭代器 q 相等唉擂。如果調(diào)用時 p 已經(jīng)指向 q 的后面，則這個函數(shù)會陷入死循環(huán)檀葛。
• iter_swap(p, q)：用于交換兩個迭代器 p玩祟、q 指向的值。

要使用上述模板屿聋，需要包含頭文件 algorithm空扎。下面的程序演示了這三個函數(shù)模板的 用法。

#include <list>
#include <iostream>
#include <algorithm> //要使用操作迭代器的函數(shù)模板润讥，需要包含此文件
using namespace std;
int main()
{
    int a[5] = { 1, 2, 3, 4, 5 };
    list <int> lst(a, a+5);
    list <int>::iterator p = lst.begin();
    advance(p, 2);  //p向后移動兩個元素转锈，指向3
    cout << "1)" << *p << endl;  //輸出 1)3
    advance(p, -1);  //p向前移動一個元素，指向2
    cout << "2)" << *p << endl;  //輸出 2)2
    list<int>::iterator q = lst.end();
    q--;  //q 指向 5
    cout << "3)" << distance(p, q) << endl;  //輸出 3)3
    iter_swap(p, q); //交換 2 和 5
    cout << "4)";
    for (p = lst.begin(); p != lst.end(); ++p)
        cout << *p << " ";
    return 0;
}

程序的輸出結(jié)果是：
1) 3
2) 2
3) 3
4) 1 5 3 4 2

八楚殿、迭代器中的traits

讓我們來看下面的一段代碼：

int ai[] = {3, 6, 9, 12, 15};
int *p = ai;
advance(p, 3);
cout <<"*p="<< *p << endl; //we get *p=12

可以看出advance不僅能夠?qū)ο駐ector撮慨，list這樣的容器處理，也可以對傳統(tǒng)的數(shù)據(jù)指針作處理。而我們知道傳統(tǒng)的int這種類型砌溺，是沒有iterator_category的菇曲，因此如果我們使用想當(dāng)然版本的_Iter_cat(p)，它會執(zhí)行typename int::iterator_category _Cat抚吠，毫無疑問這句話會失敗常潮，因?yàn)閴焊鵬nt就不是一個類類型，何談取它的iterator_category呢楷力。我們標(biāo)準(zhǔn)庫設(shè)計(jì)的人員創(chuàng)造性的提出了標(biāo)準(zhǔn)版本的_Iter_cat(p)喊式，它繞了遠(yuǎn)路，但是將類型tag析取的過程轉(zhuǎn)交給了iterator_traits類萧朝，由它通過iterator_traits<_Iter>::iterator_category 來獲取_Iter的類型〔砹簦現(xiàn)在我們有了iterator_traits類的輔助，我們就可以針對int這種特別的類型設(shè)計(jì)它的特化版本检柬，也就是說我們的iterator_traits類對常見的迭代器類献联，直接使用迭代器類的iterator_category，而對于非迭代器類int這種何址，設(shè)計(jì)了特化版本的實(shí)現(xiàn)來返回它的迭代器tag里逆。 根據(jù)我們的經(jīng)驗(yàn)，int p這種指針類型支持隨機(jī)存儲用爪，也就是說p+3原押，p+10都是可以的，因此我們針對普通指針的特化版本如下：

template<class _Ty> //_Ty can be int, double...
    struct iterator_traits<_Ty *>
    {   // get traits from pointer
    typedef random_access_iterator_tag iterator_category;
    typedef _Ty value_type;
    typedef ptrdiff_t difference_type;
    typedef ptrdiff_t distance_type;    // retained
    typedef _Ty *pointer;
    typedef _Ty& reference;
};

STL中”萃取機(jī)“的源碼
iterator_traits

// 用于traits出迭代其所指對象的型別
template <class Iterator>
struct iterator_traits
{
  // 迭代器類型, STL提供五種迭代器
  typedef typename Iterator::iterator_category iterator_category;

  // 迭代器所指對象的型別
  // 如果想與STL算法兼容, 那么在類內(nèi)需要提供value_type定義
  typedef typename Iterator::value_type        value_type;

  // 這個是用于處理兩個迭代器間距離的類型
  typedef typename Iterator::difference_type   difference_type;

  // 直接指向?qū)ο蟮脑羔橆愋?  typedef typename Iterator::pointer           pointer;

  // 這個是對象的引用類型
  typedef typename Iterator::reference         reference;
};
// 針對指針提供特化版本
template <class T>
struct iterator_traits<T*>
{
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

// 針對指向常對象的指針提供特化
template <class T>
struct iterator_traits<const T*>
{
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

type_traits

/**
 * 用來標(biāo)識真/假對象,利用type_traits響應(yīng)結(jié)果來進(jìn)行參數(shù)推導(dǎo)偎血，
 * 而編譯器只有面對class object形式的參數(shù)才會做參數(shù)推導(dǎo)诸衔，
 * 這兩個空白class不會帶來額外負(fù)擔(dān)
 */
struct __true_type{};
struct __false_type{};

/**
 * type_traits結(jié)構(gòu)體設(shè)計(jì)
 */
template <class type>
struct __type_traits
{
    // 不要移除這個成員
    // 它通知能自動特化__type_traits的編譯器, 現(xiàn)在這個__type_traits template是特化的
    // 這是為了確保萬一編譯器使用了__type_traits而與此處無任何關(guān)聯(lián)的模板時
    // 一切也能順利運(yùn)作
   typedef __true_type     this_dummy_member_must_be_first;

   // 以下條款應(yīng)當(dāng)被遵守, 因?yàn)榫幾g器有可能自動生成類型的特化版本
   //   - 你可以重新安排的成員次序
   //   - 你可以移除你想移除的成員
   //   - 一定不可以修改下列成員名稱, 卻沒有修改編譯器中的相應(yīng)名稱
   //   - 新加入的成員被當(dāng)作一般成員, 除非編譯器提供特殊支持

   typedef __false_type    has_trivial_default_constructor;
   typedef __false_type    has_trivial_copy_constructor;
   typedef __false_type    has_trivial_assignment_operator;
   typedef __false_type    has_trivial_destructor;
   typedef __false_type    is_POD_type;
};
// 特化類型:
//         char, signed char, unsigned char,
//         short, unsigned short
//         int, unsigned int
//         long, unsigned long
//         float, double, long double
/**
 * 以下針對C++內(nèi)置的基本數(shù)據(jù)類型提供特化版本, 
 * 使其具有trivial default constructor,
 * copy constructor, assignment operator, destructor并標(biāo)記其為POD類型
 */
__STL_TEMPLATE_NULL struct __type_traits<char>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對char的特化版本
__STL_TEMPLATE_NULL struct __type_traits<signed char>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對unsigned char的特化版本
__STL_TEMPLATE_NULL struct __type_traits<unsigned char>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對short的特化版本
__STL_TEMPLATE_NULL struct __type_traits<short>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對unsigned short的特化版本
__STL_TEMPLATE_NULL struct __type_traits<unsigned short>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對int的特化版本
__STL_TEMPLATE_NULL struct __type_traits<int>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對unsigned int的特化版本
__STL_TEMPLATE_NULL struct __type_traits<unsigned int>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對long的特化版本
__STL_TEMPLATE_NULL struct __type_traits<long>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對unsigned long的特化版本
__STL_TEMPLATE_NULL struct __type_traits<unsigned long>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對float的特化版本
__STL_TEMPLATE_NULL struct __type_traits<float>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對double的特化版本
__STL_TEMPLATE_NULL struct __type_traits<double>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};
//針對long double的特化版本
__STL_TEMPLATE_NULL struct __type_traits<long double>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

// 針對指針提供特化
template <class T>
struct __type_traits<T*>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

// 針對char *, signed char *, unsigned char *提供特化

struct __type_traits<char*>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

struct __type_traits<signed char*>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

struct __type_traits<unsigned char*>
{
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

九、自定義簡單迭代器的實(shí)現(xiàn)

STL中每個容器都有自己的迭代器颇玷，各種迭代器的接口相同笨农，內(nèi)部實(shí)現(xiàn)卻不相同，這也直接體現(xiàn)了泛型編程的概念帖渠，下面在單鏈表類中內(nèi)嵌入一個iterator的類來實(shí)現(xiàn)單鏈表的迭代

#include <iostream>

template<typename T>
struct ListNode {
    T value;
    ListNode* next;
    ListNode() {
        next = 0;
    }
    ListNode(T val, ListNode *p = nullptr) :
            value(val), next(p) {
    }
};

template<typename T>
class List {
private:
    ListNode<T> *m_pHead;
    ListNode<T> *m_pTail;
    int m_nSize;
public:
    List() {
        m_pHead = nullptr;
        m_pTail = nullptr;
        m_nSize = 0;
    }
    //從鏈表尾部插入元素
    void push_back(T value) {
        if (m_pHead == nullptr) {
            m_pHead = new ListNode<T>(value);
            m_pTail = m_pHead;
        } else {
            m_pTail->next = new ListNode<T>(value);
            m_pTail = m_pTail->next;
        }

    }

    //打印鏈表元素
    void print(std::ostream &os = std::cout) const {
        for (ListNode<T> *ptr = m_pHead; ptr != m_pTail->next ; ptr = ptr->next)
            std::cout << ptr->value << " ";
        os << std::endl;
    }

    //內(nèi)置迭代器
    class iterator {
    private:
        ListNode<T> *m_ptr;
    public:
        iterator(ListNode<T>* p = nullptr) :
                m_ptr(p) {
        }

        T operator*() const {
            return m_ptr->value;
        }
        ListNode<T>* operator->() const {
            return m_ptr;
        }
        iterator& operator++() {
            m_ptr = m_ptr->next;
            return *this;
        }
        iterator operator++(int) {
            ListNode<T>* tmp = m_ptr;
            m_ptr = m_ptr->next;
            return iterator(tmp);
        }

        bool operator==(const iterator &arg) const {
            return arg.m_ptr == this->m_ptr;
        }

        bool operator!=(const iterator &arg) const {
            return arg.m_ptr != this->m_ptr;
        }

    };

    //返回鏈表頭部指針
    iterator begin() const {
        return iterator(m_pHead);
    }

    //返回鏈表尾部指針
    iterator end() const {
        return iterator(m_pTail->next);
    }

    //其它成員函數(shù)

};

int main() {
    List<int> l;
    l.push_back(1);
    l.push_back(2);
    l.print();
    for (List<int>::iterator it = l.begin(); it != l.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    return 0;
}

十谒亦、STL源碼學(xué)習(xí)

stl_iterator_base.h

/// This file contains all of the general iterator-related utilities.
/// The internal file stl_iterator.h contains predefined iterators,
/// such as front_insert_iterator and istream_iterator.
 
#include <concept_checks.h>
 
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 {};
 
///這些迭代器類型并非C++ Standard,客戶端系自己的迭代器時
///可以根據(jù)屬性繼承這些類,以便擁有迭代器需具備的基本屬性
///方可使得自定義迭代器與STL算法融合
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;
};
 
///對這些迭代器重要屬性的型別推導(dǎo)函數(shù)
template <class _Tp, class _Distance>
inline input_iterator_tag
iterator_category(const input_iterator<_Tp, _Distance>&)
  { return input_iterator_tag(); }
 
inline output_iterator_tag iterator_category(const output_iterator&)
  { return output_iterator_tag(); }
 
template <class _Tp, class _Distance>
inline forward_iterator_tag
iterator_category(const forward_iterator<_Tp, _Distance>&)
  { return forward_iterator_tag(); }
 
template <class _Tp, class _Distance>
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
  { return bidirectional_iterator_tag(); }
 
template <class _Tp, class _Distance>
inline random_access_iterator_tag
iterator_category(const random_access_iterator<_Tp, _Distance>&)
  { return random_access_iterator_tag(); }
 
template <class _Tp>
inline random_access_iterator_tag iterator_category(const _Tp*)
  { return random_access_iterator_tag(); }
 
template <class _Tp, class _Distance>
inline _Tp* value_type(const input_iterator<_Tp, _Distance>&)
  { return (_Tp*)(0); }
 
template <class _Tp, class _Distance>
inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&)
  { return (_Tp*)(0); }
 
template <class _Tp, class _Distance>
inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&)
  { return (_Tp*)(0); }
 
template <class _Tp, class _Distance>
inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&)
  { return (_Tp*)(0); }
 
template <class _Tp>
inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); }
 
template <class _Tp, class _Distance>
inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&)
{
  return (_Distance*)(0);
}
 
template <class _Tp, class _Distance>
inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&)
{
  return (_Distance*)(0);
}
 
template <class _Tp, class _Distance>
inline _Distance*
distance_type(const bidirectional_iterator<_Tp, _Distance>&)
{
  return (_Distance*)(0);
}
 
template <class _Tp, class _Distance>
inline _Distance*
distance_type(const random_access_iterator<_Tp, _Distance>&)
{
  return (_Distance*)(0);
}
 
template <class _Tp>
inline ptrdiff_t* distance_type(const _Tp*) { return (ptrdiff_t*)(0); }
 
///iterator_traits使得Tp*和const Tp*可以再STL中用到任何需要迭代器的地方
template <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>
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;
};
 
///對通用迭代器求距離,采用了型別推導(dǎo),這是STL非常常見的一種
///泛型編程技法
template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator __last,
                       _Distance& __n, input_iterator_tag)
{
  while (__first != __last) { ++__first; ++__n; }
}
 
template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first,
                       _RandomAccessIterator __last,
                       _Distance& __n, random_access_iterator_tag)
{
    ///對型別的檢驗(yàn),使得在編譯器發(fā)現(xiàn)問題,而非在運(yùn)行期導(dǎo)致程序崩潰
    ///檢驗(yàn)型別是否確實(shí)為隨機(jī)迭代器
  __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);
 
  ///調(diào)用型別推導(dǎo)函數(shù)iterator_category得到迭代器的屬性,從而調(diào)用合適的求距離函數(shù)
  ///為了或得效率(具有random_access_iterator_tag的迭代器求距離可以采用更具效率的做法)
  __distance(__first, __last, __n, iterator_category(__first));
}
 
 
template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
  while (__n--) ++__i;
}
 
template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance __n,
                      bidirectional_iterator_tag) {
  __STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
  if (__n >= 0)
    while (__n--) ++__i;
  else
    while (__n++) --__i;
}
 
template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance __n,
                      random_access_iterator_tag) {
  __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
  __i += __n;
}
 
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n) {
  __STL_REQUIRES(_InputIterator, _InputIterator);
  __advance(__i, __n, iterator_category(__i));
}

stl_iterator.h

///back_insert_iterator通過保存需要插入元素的容器指針
///每次容器元素的插入實(shí)際是調(diào)用其push_back成員函數(shù)實(shí)現(xiàn)的
///因此該容器必須具備push_back成員函數(shù).
 
#include <stl_iterator_base.h>
template <class _Container>
class back_insert_iterator {
protected:
  _Container* container;
public:
  typedef _Container          container_type;
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
 
  explicit back_insert_iterator(_Container& __x) : container(&__x) {}
 
  back_insert_iterator<_Container>&
  operator=(const typename _Container::value_type& __value) {
    container->push_back(__value);    ///每次為其賦值都調(diào)用綁定容器的push_back函數(shù)
    return *this;
  }
 
  back_insert_iterator<_Container>& operator*() { return *this; }
  back_insert_iterator<_Container>& operator++() { return *this; }
  back_insert_iterator<_Container>& operator++(int) { return *this; }
};
 
template <class _Container>
inline output_iterator_tag
iterator_category(const back_insert_iterator<_Container>&)
{
  return output_iterator_tag();
}
 
///實(shí)際更經(jīng)常使用這個函數(shù)
template <class _Container>
inline back_insert_iterator<_Container> back_inserter(_Container& __x) {
  return back_insert_iterator<_Container>(__x);
}
 
///除了調(diào)用push_front函數(shù)外,與back_insert_iterator如出一轍
template <class _Container>
class front_insert_iterator {
protected:
  _Container* container;
public:
  typedef _Container          container_type;
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
 
  explicit front_insert_iterator(_Container& __x) : container(&__x) {}
  front_insert_iterator<_Container>&
  operator=(const typename _Container::value_type& __value) {
    container->push_front(__value);
    return *this;
  }
 
  front_insert_iterator<_Container>& operator*() { return *this; }
  front_insert_iterator<_Container>& operator++() { return *this; }
  front_insert_iterator<_Container>& operator++(int) { return *this; }
};
 
template <class _Container>
inline output_iterator_tag
iterator_category(const front_insert_iterator<_Container>&)
{
  return output_iterator_tag();
}
 
template <class _Container>
inline front_insert_iterator<_Container> front_inserter(_Container& __x) {
  return front_insert_iterator<_Container>(__x);
}
 
///提供插入位置的插入迭代器,調(diào)用綁定容器的insert函數(shù)
template <class _Container>
class insert_iterator {
protected:
  _Container* container;
  typename _Container::iterator iter;
public:
  typedef _Container          container_type;
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
 
  insert_iterator(_Container& __x, typename _Container::iterator __i)
    : container(&__x), iter(__i) {}
  insert_iterator<_Container>&
  operator=(const typename _Container::value_type& __value) {
    iter = container->insert(iter, __value);
    ++iter;    ///插入后要將所提供迭代器的位置前移一位
    return *this;
  }
  insert_iterator<_Container>& operator*() { return *this; }
  insert_iterator<_Container>& operator++() { return *this; }
  insert_iterator<_Container>& operator++(int) { return *this; }
};
 
template <class _Container>
inline output_iterator_tag
iterator_category(const insert_iterator<_Container>&)
{
  return output_iterator_tag();
}
 
template <class _Container, class _Iterator>
inline
insert_iterator<_Container> inserter(_Container& __x, _Iterator __i)
{
  typedef typename _Container::iterator __iter;
  return insert_iterator<_Container>(__x, __iter(__i));
}
 
/// This is the new version of reverse_iterator, as defined in the
///  draft C++ standard.  It relies on the iterator_traits template,
///  which in turn relies on partial specialization.  The class
///  reverse_bidirectional_iterator is no longer part of the draft
///  standard, but it is retained for backward compatibility.
 
template <class _Iterator>
class reverse_iterator
{
protected:
  _Iterator current;
public:
    ///反向迭代器的各項(xiàng)性質(zhì)型別與基迭代器保持一致
  typedef typename iterator_traits<_Iterator>::iterator_category
          iterator_category;
  typedef typename iterator_traits<_Iterator>::value_type
          value_type;
  typedef typename iterator_traits<_Iterator>::difference_type
          difference_type;
  typedef typename iterator_traits<_Iterator>::pointer
          pointer;
  typedef typename iterator_traits<_Iterator>::reference
          reference;
 
  typedef _Iterator iterator_type;
  typedef reverse_iterator<_Iterator> _Self;
 
public:
  reverse_iterator() {}
  explicit reverse_iterator(iterator_type __x) : current(__x) {}
 
  reverse_iterator(const _Self& __x) : current(__x.current) {}
 
  iterator_type base() const { return current; }
 
  reference operator*() const {
      ///由于STL中所有區(qū)間都是左閉右開區(qū)間,因此對反向迭代器的提領(lǐng)需要在
  ///基迭代器的基礎(chǔ)上后退一步再提領(lǐng),才不至于提領(lǐng)到非法指針
    _Iterator __tmp = current;
    return *--__tmp;
  }
 
  pointer operator->() const { return &(operator*()); }
 
 
  _Self& operator++() {
    --current;          ///反向迭代器前進(jìn)即使基迭代器的后退
    return *this;
  }
  _Self operator++(int) {
    _Self __tmp = *this;
    --current;
    return __tmp;
  }
  _Self& operator--() {
    ++current;
    return *this;
  }
  _Self operator--(int) {
    _Self __tmp = *this;
    ++current;
    return __tmp;
  }
 
  _Self operator+(difference_type __n) const {
    return _Self(current - __n);
  }
  _Self& operator+=(difference_type __n) {
    current -= __n;
    return *this;
  }
  _Self operator-(difference_type __n) const {
    return _Self(current + __n);
  }
  _Self& operator-=(difference_type __n) {
    current += __n;
    return *this;
  }
  reference operator[](difference_type __n) const { return *(*this + __n); }
};
 
template <class _Iterator>
inline bool operator==(const reverse_iterator<_Iterator>& __x,
                       const reverse_iterator<_Iterator>& __y) {
  return __x.base() == __y.base();
}
 
template <class _Iterator>
inline bool operator<(const reverse_iterator<_Iterator>& __x,
                      const reverse_iterator<_Iterator>& __y) {
  return __y.base() < __x.base();
}
 
template <class _Iterator>
inline typename reverse_iterator<_Iterator>::difference_type
operator-(const reverse_iterator<_Iterator>& __x,
          const reverse_iterator<_Iterator>& __y) {
  return __y.base() - __x.base();
}
 
template <class _Iterator>
inline reverse_iterator<_Iterator>
operator+(typename reverse_iterator<_Iterator>::difference_type __n,
          const reverse_iterator<_Iterator>& __x) {
  return reverse_iterator<_Iterator>(__x.base() - __n);
}
 
///istream_iterator類的聲明,后面operator==要用到
template <class _Tp, class _Dist = ptrdiff_t>
class istream_iterator;
 
///operator==函數(shù)必須提前聲明,否則不能作為istream_iterator類的友元函數(shù)出現(xiàn)
template <class _Tp, class _Dist>
inline bool operator==(const istream_iterator<_Tp, _Dist>&,
                       const istream_iterator<_Tp, _Dist>&);
 
///istream_iterator類通過封裝一個istream類型的指針來實(shí)現(xiàn)對istream流的操作
template <class _Tp, class _Dist>
class istream_iterator {
 
  friend bool operator==<>(const istream_iterator&,
                         const istream_iterator&);
protected:
  istream* _M_stream;
  _Tp _M_value;         ///寫入的數(shù)據(jù)類型
  bool _M_end_marker;      ///流結(jié)束標(biāo)志
 
  void _M_read() {
      ///先判斷流是否結(jié)束,并重置結(jié)束標(biāo)志
    _M_end_marker = (*_M_stream) ? true : false;
    ///若尚未結(jié)束,讀取一個對象
    if (_M_end_marker) *_M_stream >> _M_value;
    ///再次重置流結(jié)束標(biāo)志
    _M_end_marker = (*_M_stream) ? true : false;
  }
 
public:
  typedef input_iterator_tag  iterator_category;
  typedef _Tp                 value_type;
  typedef _Dist               difference_type;
  typedef const _Tp*          pointer;
  typedef const _Tp&          reference;
  ///默認(rèn)關(guān)聯(lián)cin,并且處于流結(jié)束處
  istream_iterator() : _M_stream(&cin), _M_end_marker(false) {}
 
  ///創(chuàng)建流對象時,調(diào)用read,試圖讀入一個對象
  istream_iterator(istream& __s) : _M_stream(&__s) { _M_read(); }
  reference operator*() const { return _M_value; }
 
  pointer operator->() const { return &(operator*()); }
 
  istream_iterator<_Tp, _Dist>& operator++() {
      ///迭代器每前進(jìn)一步,調(diào)用一次read函數(shù),試圖讀取一個對象
    _M_read();
    return *this;
  }
  istream_iterator<_Tp, _Dist> operator++(int)  {
    istream_iterator<_Tp, _Dist> __tmp = *this;
    _M_read();
    return __tmp;
  }
};
 
template <class _Tp, class _Dist>
inline input_iterator_tag
iterator_category(const istream_iterator<_Tp, _Dist>&)
{
  return input_iterator_tag();
}
 
template <class _Tp, class _Dist>
inline _Tp*
value_type(const istream_iterator<_Tp, _Dist>&) { return (_Tp*) 0; }
 
template <class _Tp, class _Dist>
inline _Dist*
distance_type(const istream_iterator<_Tp, _Dist>&) { return (_Dist*)0; }
 
template <class _Tp, class _Distance>
inline bool operator==(const istream_iterator<_Tp, _Distance>& __x,
                       const istream_iterator<_Tp, _Distance>& __y) {
  return (__x._M_stream == __y._M_stream &&
          __x._M_end_marker == __y._M_end_marker) ||
         __x._M_end_marker == false && __y._M_end_marker == false;
}
 
///基本和istream實(shí)現(xiàn)相同,無結(jié)束標(biāo)示符
template <class _Tp>
class ostream_iterator {
protected:
  ostream* _M_stream;
  const char* _M_string;    ///輸出時用于分隔不同對象,有客戶端提供
public:
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
 
  ostream_iterator(ostream& __s) : _M_stream(&__s), _M_string(0) {}
  ostream_iterator(ostream& __s, const char* __c)
    : _M_stream(&__s), _M_string(__c)  {}
  ostream_iterator<_Tp>& operator=(const _Tp& __value) {
    *_M_stream << __value;
    if (_M_string) *_M_stream << _M_string;
    return *this;
  }
  ostream_iterator<_Tp>& operator*() { return *this; }
  ostream_iterator<_Tp>& operator++() { return *this; }
  ostream_iterator<_Tp>& operator++(int) { return *this; }
};
 
template <class _Tp>
inline output_iterator_tag
iterator_category(const ostream_iterator<_Tp>&) {
  return output_iterator_tag();
}