本節(jié)實驗我們將為大家講解迭代器，主要介紹 5 種常見迭代器：輸入、輸出迭代器，前向逆向迭代器，雙向迭代器和隨機迭代器。主要內(nèi)容包括各自的構(gòu)造方法和操作方法。

1.1 知識點
輸出迭代器
輸入迭代器
前向迭代器
雙向迭代器
隨機迭代器
迭代器輔助函數(shù)
1.2 實驗環(huán)境
g++
ubuntu 16.04
1.3 代碼獲取
可以通過以下鏈接獲取本課程的源碼內(nèi)容，本次實驗內(nèi)容主要包含在文件Iterator.h。

//獲取代碼
wget http://labfile.oss.aliyuncs.com/courses/1166/mySTL.zip
unzip -q mySTL.zip -d ./Code/

迭代器（iterator）是一種對象，它能夠用來遍歷標(biāo)準模板庫容器中的部分或全部元素，每個迭代器對象代表容器中的確定的地址。迭代器修改了常規(guī)指針的接口，所謂迭代器是一種概念上的抽象：那些行為上像迭代器的東西都可以叫做迭代器。然而迭代器有很多不同的能力，它可以把抽象容器和通用算法有機的統(tǒng)一起來。迭代器基本分為五種，輸入輸出迭代器，前向逆向迭代器，雙向迭代器和隨機迭代器。

簡單概括：迭代器是一種檢查容器內(nèi)元素并遍歷元素的可帶泛型數(shù)據(jù)類型。

下面，我們新建頭文件Iterator.h是頭文件，用來實現(xiàn)我們的迭代器，這里的代碼需要引用到系統(tǒng)頭文件#include <cstddef>，它主要用于定義一些類型。接下來我們定義5種迭代器的類型，將其寫入Iterator.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 {};//返回隨機迭代器

輸入迭代器

通過對輸入迭代器解除引用，它將引用對象，而對象可能位于集合中。通常用于傳遞地址。

template<class T, class Distance>
struct input_iterator {
typedef input_iterator_tag iterator_category;//返回類型
typedef T value_type;//所指對象類型
typedef Distance difference_type;//迭代器間距離類型
typedef T* pointer;//操作結(jié)果類型
typedef T& reference;//解引用操作結(jié)果類型
};

輸出迭代器

該類迭代器和輸入迭代器極其相似，也只能單步向前迭代元素，不同的是該類迭代器對元素只有寫的權(quán)力。通常用于返回地址。

struct output_iterator{
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};

前向迭代器

前向迭代器可以在一個正確的區(qū)間中進行讀寫操作，它擁有輸入迭代器的所有特性，和輸出迭代器的部分特性，以及單步向前迭代元素的能力。通常用于遍歷。

template <class T, class Distance> struct forward_iterator{
typedef forward_iterator_tag iterator_category;
typedefT value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};

雙向迭代器

該類迭代器是在前向迭代器的基礎(chǔ)上提供了單步向后迭代元素的能力，前向迭代器的高級版。

template <class T, class Distance> struct bidirectional_iterator{
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};

隨機迭代器

該類迭代器能完成上面所有迭代器的工作，它自己獨有的特性就是可以像指針那樣進行算術(shù)計算，而不是僅僅只有單步向前或向后迭代。

template <class T, class Distance> struct random_access_iterator{
typedef random_access_iterator_tag iterator_category;
typedefT value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};

迭代器輔助函數(shù)

迭代器的實現(xiàn)，我們這里主要會使用到兩個函數(shù)來輔助完成操作，分別是 advace 函數(shù)和 distance 函數(shù)。這兩個函數(shù)是寫到Algorithm.h文件中的。

advance 函數(shù): 用于迭代器前移，增加迭代的位置?？捎糜诙ㄏ蛟L問到迭代器的某個變量。
template<class InputIterator, class Distance>
void _advance(InputIterator& it, Distance n, input_iterator_tag){
assert(n >= 0);
while (n--){//當(dāng)n大于0，迭代器前移n位
++it;
}
}

void advance(InputIterator& it, Distance n){
typedef typename iterator_traits<InputIterator>::iterator_category iterator_category;
_advance(it, n, iterator_category());
}
distance 函數(shù): 用于計算迭代器間距離
template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
_distance(InputIterator first, InputIterator last, input_iterator_tag){
typename iterator_traits<InputIterator>::difference_type dist = 0;//初始化距離
while (first++ != last){//當(dāng)首地址不等于尾地址，距離增加
++dist;
}
return dist;//返回迭代器間距離
}

template<class Iterator>
typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last){
typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
return _distance(first, last, iterator_category());
}

測試實例

完成上面迭代器的實現(xiàn)后，我們現(xiàn)在在 Test 目錄下新建文件 iteratortest.cpp,用于測試 Iterator 的功能。這里的測試我們需要借助到 vector 容器。關(guān)于Vector 容器的內(nèi)容，我們將在后面的實驗中給大家講解，這里我們直接使用 Vector.h的內(nèi)容。該文件可以通過下載課程源碼找到。

#include <iostream>
#include "Iterator.h"
#include "Vector.h"

int main()
{
    mySTL::vector<int> vec;
    for(int i = 0;i < 10;i++)
        vec.push_back(i);

    mySTL::vector<int>::iterator it = vec.begin();
    mySTL::vector<int>::iterator end = vec.end();
    std::cout<<"The value of vector:";
    for(;it != vec.end();it++)
        std::cout<<*it<<" ";
    std::cout<<std::endl;

    //advance使用
    it = vec.begin();
    std::cout<<"After advance 3:";
    mySTL::advance(it,3);
    std::cout << *it << " "<<std::endl;

    //distance使用
    std::cout<<"The distance of position 3 to the end:";
    std::cout<<mySTL::distance(it,end)<<std::endl;

    return 0; 
}

command line:

g++ iteratortest.cpp -std=c++11 -o iteratortest -I ../include
./iteratortest

result: