讀<泛型編程與STL>第二章
所謂concept，是一組“描述某個(gè)型別”的條件。當(dāng)某個(gè)型別滿足所有這樣的條件，我們便說它是該concept的一個(gè)model。舉例來說，char* 便是Input Iterator的model。
concept并不是類，變量或是template參數(shù)，事實(shí)上它不是可以直接在C++程序中呈現(xiàn)的東西。然而在每個(gè)運(yùn)用"泛型編程(generic programming)"的C++程序中，concept非常重要。也就是說concept不像class，int那樣有一個(gè)明確的關(guān)鍵字，可以在程序中直接聲明其對(duì)象的，它只是一組條件，作為一個(gè)concept的model，它必須滿足這個(gè)concept的所有條件。
Iterator是指針的概括物，它們是"用來指向其他對(duì)象"的一種對(duì)象，這對(duì)于像find這樣的泛型算法很重要，因?yàn)樗麄兛梢杂脕碓趯?duì)象區(qū)間內(nèi)"來回移動(dòng)(iterate)"。
Iterator對(duì)于泛型編程之所以重要，原因是它是算法與數(shù)據(jù)結(jié)構(gòu)之間的接口。類似find這樣的算法，以iterator為引數(shù)，便可以作用在許許多多不同的數(shù)據(jù)結(jié)構(gòu)上-即使彼此結(jié)構(gòu)不同(例如鏈表與C數(shù)組)。我們僅僅要求：iterator能夠以某種線性順序遍歷某個(gè)數(shù)據(jù)結(jié)構(gòu)，以訪問其中所有的元素。
Iterator不單單只是一個(gè)concept，而是五個(gè)不同的concepts：Input Iterator，Output Iterator，F(xiàn)orward Iterator，Bidirectional Iterator和Random Access Iterator。
<一> Input Iterator
本質(zhì)上，Input Iterator是某種類似指針的東西，并且在我們談到iterator range[first,last)時(shí)有意義：
1.當(dāng)它作為一般的C指針時(shí)，有三種價(jià)值：它是dereferenceable(可取值的)，past the end(可跨越尾端的)，singular(可為null的)。當(dāng)它作為指針，只有在first和last都不為null指針時(shí)，[first,last)才是有意義的range。
2.我們可以比較型別為Iterator的兩個(gè)對(duì)象的相等性。例如：while(first!=last)。
3.Input Iterator可以被復(fù)制或被賦值。在調(diào)用一個(gè)函數(shù)時(shí)，可以用傳值的方式傳入?yún)?shù)，如find的參數(shù)first和last就是兩個(gè)Iterator，可以用傳值來傳入?yún)?shù)，這會(huì)掉用Iterator的copy constructor。
4.可以提領(lǐng)(dereference)一個(gè)型別為Iterator的對(duì)象。也就是說，表達(dá)式*p有充分的定義。每一個(gè)Input Iterator都有一個(gè)associated value type，那是它所指的對(duì)象的型別。
5.可以對(duì)一個(gè)型別為Iterator的對(duì)象進(jìn)行累加動(dòng)作。也就是說，表達(dá)式++p和p++都有充分定義。
注意：
1.Input Iterator用來指向某對(duì)象，但不需要提供任何更改該對(duì)象的方法。可以提領(lǐng)一個(gè)Input Iterator，但不能對(duì)提領(lǐng)后的結(jié)果賦予新值，也就是說表達(dá)式*p=x不一定有效。
2.Input Iterator可以累加，但并非一定需要遞減。Input Iterator唯一需要的運(yùn)算形式是operator++。
3.可以測(cè)試兩個(gè)Input Iterator是否相等，但不能測(cè)試誰在誰之前。也就是說p1<p2不一定成立(p1,p2都是Input Iterator)。
4.Input Iterator的唯一正確使用方式是線性查找，這是一種"single pass(單回)"算法，它只遍歷range[first,last)一次，并對(duì)range中的值最多讀取一次。也就是說，遍歷時(shí)只能像前(++),不能退后，前一個(gè)遍歷的值不再有效。不能以兩個(gè)iterator指向"由Input iterator形成的range"中的兩個(gè)不同元素。
舉例：
1.template<class InputIterator, class T> inline
InputIterator find(InputIterator first, InputIterator last, const T& value)
上面為泛型算法find的定義，可以看見find的前兩個(gè)參數(shù)都為InputIterator類型的Iterator。
sample如下：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int size = 8;
vector<int> vec(size);
vector<int>::iterator iter = vec.begin();
for(int ix = 0; iter != vec.end(); ++iter,++ix)
*iter = ix;
cout << "Array = { ";
for(vector<int>::iterator iter2 = vec.begin(); iter2 != vec.end(); ++iter2)
cout << *iter2 <<",";
cout << "}" << endl;
vector<int>::iterator location;
int value = 7;
location = find(vec.begin(),vec.end(),value);
if(location != vec.begin() + vec.size())
cout << "First element that matches " << value << " is at location " << location - vec.begin() << endl;
else
cout << "The sequence doesn't contain any elements with value " << value << endl;
return 0;
}
MSDN中定義
vector::iterator
typedef T0 iterator; 說明iterator是vector中的一個(gè)型別，它是T0的別名，至于T0是在哪里定義的，可以參考vc98目錄下Include中的VECTOR文件，定義如下：（注意此定義與MSDN中的定義的區(qū)別）
///////////////////////////////////////////////////////////////////////////////////////
.......
template<class _Ty, class _A = allocator<_Ty> >
class vector {
public:
typedef vector<_Ty, _A> _Myt;
typedef _A allocator_type;
typedef _A::size_type size_type;
typedef _A::difference_type difference_type;
typedef _A::pointer _Tptr;
typedef _A::const_pointer _Ctptr;
typedef _A::reference reference;
typedef _A::const_reference const_reference;
typedef _A::value_type value_type;
typedef _Tptr iterator; //MSDN中此處_Tptr換成了T0，可知iterator是一個(gè)指針類型
typedef _Ctptr const_iterator;
//////////////////////////////////////////////////////////////////////////////////////////
在MSDN中有如下說明：
The object allocates and frees storage for the sequence it controls through a protected object named allocator, of class A. Such an allocator object must have the same external interface as an object of template class allocator.
而class allocator_object中是這樣說明pointer的：
pointer -- behaves like a pointer to T
所以iterator是一個(gè)指向T類型的指針，在本sample中，T是int類型，故iterator是int類型的指針。
2.istream_Iterator
istream_Iterator是一種Input Iterator。sample如下：
//輸入--排序--輸出
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
vector<int> V;
cout << "請(qǐng)輸入整數(shù)序列，按任意非數(shù)字鍵并回車結(jié)束輸入: \n";
copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(V));
cout << "排序中......" << endl;
sort(V.begin(),V.end());
cout << "下面顯示經(jīng)過排序的序列: \n";
copy(V.begin(),V.end(),ostream_iterator<int>(cout," "));
cout << endl;
return 0;
}
代碼具體解釋可參考Clare的blog：
http://www.cnblogs.com/oomusou/archive/2006/12/07/585123.html