本文的技術(shù)可以參考本博客: Traits 技術(shù) --- 模板元編程 (轉(zhuǎn))
迭代器可以區(qū)分為不同的類型，每個(gè)類型都有特定的迭代器功能。
根據(jù)迭代器類型，將算法根據(jù)類型的不同實(shí)現(xiàn)出更加有效率的版本，將會(huì)很有用，也很必要！
透過迭代器標(biāo)志(tags)和迭代器特性(traits,由<iterator>提供)可以實(shí)現(xiàn)這樣的重載.
STL為每種迭代器都提供了一個(gè)迭代器標(biāo)志(iterator tags),用來(lái)作為迭代器的標(biāo)簽(label)
namespace
{
struct output_iterator_tag
{
};
struct input_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
{
};
}
-------------------------------------------------------------------------------------------
五種迭代器類別
首先，引進(jìn)迭代器是為了在算法與容器之間隔開，可以讓兩者獨(dú)立發(fā)展。這樣勢(shì)必要求迭代器需要像算法展現(xiàn)統(tǒng)一的接口，也就是說(shuō)，從算法的角度出發(fā)，迭代器的功能接口是一樣的，算法無(wú)法直接看到容器的，而是通過迭代器簡(jiǎn)介管理操作容器，這樣可以推到出：算法眼里容器都是一樣的。而顯然這并不合理。
因?yàn)?，即使各種容器有統(tǒng)一的基本特性——“聚集”同一類型的數(shù)據(jù)元素。但是由于不同的容器聚集的方式不同，導(dǎo)致表現(xiàn)出來(lái)的許多功能特性不同。（例如vector，deque表現(xiàn)可以很好的支持random access性質(zhì)，但是你叫l(wèi)ist也支持這個(gè)，這將是非常不明智的）。所以，即使我們盡量希望向外部展現(xiàn)一個(gè)統(tǒng)一的容器接口（迭代器），我們?nèi)匀恍枰獏^(qū)分對(duì)待，我們?cè)诘魃蠀^(qū)分對(duì)待，就可以充分發(fā)揮各種容器的個(gè)性特點(diǎn)。算法也可以根據(jù)相應(yīng)的不同，優(yōu)化對(duì)待不同的容器。這就是出現(xiàn)不同的類型容器的原因。
Iterator Category | Ability | Providers |
Input iterator | Reads forward | istream |
Output iterator | Writes forward | ostream, inserter |
Forward iterator | Reads and writes forward | |
Bidirectional iterator | Reads and writes forward and backward | list, set, multiset, map, multimap |
Random access iterator | Reads and writes with random access | vector, deque string, array |
可以看到，不同類別的迭代器，所能支持的功能是不同的，定義容器的選擇定義哪個(gè)類別的應(yīng)不同的容器特性而定。在設(shè)計(jì)算法的時(shí)候，算法會(huì)通過類型萃取獲得該迭代器的類別。并根據(jù)不同的類別視機(jī)做特定的算法實(shí)現(xiàn)優(yōu)化。
Input iterator
Operations of Input Iterators |
Expression | Effect |
*iter | Provides read access to the actual element |
iter ->member | Provides read access to a member (if any) of the actual element |
++iter | Steps forward (returns new position) |
iter++ | Steps forward (returns old position) |
Iter1 == iter2 | Returns whether two iterators are equal |
Iter1 != iter2 | Returns whether two iterators are not equal |
TYPE(iter) | Copies iterator (copy constructor) |
這個(gè)迭代器用于，從容器中依次讀取數(shù)據(jù)（只讀，并且只能前進(jìn)）。但是還有一個(gè)會(huì)讓你匪夷所思的特性是，這種迭代器不能重復(fù)讀某個(gè)元素兩次。這是一個(gè)很奇怪但是有很合理的規(guī)定，最常見的需要用輸入迭代器的就是標(biāo)準(zhǔn)輸入口，不管有幾個(gè)迭代器指向這個(gè)標(biāo)準(zhǔn)輸入口，語(yǔ)義上不容許同一個(gè)元素被讀兩次。但是，我們奇怪的是，這個(gè)意思的就是說(shuō)，讀動(dòng)作是與迭代器相前進(jìn)一步的動(dòng)作是一起發(fā)生的，那么這種迭代器就不需要向前進(jìn)一步的功能的必要了，但這里提供了。
事實(shí)上我認(rèn)為，上面的要求只是一種語(yǔ)義上的要求。告訴你，如果你在某個(gè)容器定義迭代器的時(shí)候選擇了輸入迭代器，那么這個(gè)迭代器所應(yīng)該提供的功能模式應(yīng)該需要保持“不容許同一個(gè)元素被讀兩次”，我們知道STL對(duì)各種類別的區(qū)別只是用tags來(lái)區(qū)別的。語(yǔ)法上沒有寫死語(yǔ)義上的“建議”。
還有一個(gè)原因是，下面有幾種迭代器，是以這種迭代器為基礎(chǔ)的，所以如果你不提供這種基本的操作（向前去?。?，那他們?nèi)绾翁峁?br />
Output iterator
Operations of Output Iterators |
Expression | Effect |
*iter = value | Writes value to where the iterator refers |
++iter | Steps forward (returns new position) |
iter++ | Steps forward (returns old position) |
TYPE (iter) | Copies iterator (copy constructor) |
與input iterator 想對(duì)應(yīng)的就是output iterator，他們有很多相似點(diǎn)，并且，也有與前面類似的奇怪規(guī)定，這導(dǎo)致兩個(gè)指向同一個(gè)容器的寫迭代器，寫的過程不會(huì)出現(xiàn)覆蓋寫。其中一個(gè)有名的例子就是屏幕輸出。并且，你會(huì)發(fā)現(xiàn)寫迭代器沒有比較操作（讀模式中就有）。這是因?yàn)閷懙臅r(shí)候，是一直往外寫的，語(yǔ)義上以沒有終點(diǎn)限制的。有一個(gè)特殊的（也是我們將要介紹的）迭代器，就是inserter。
Forward iterator
Operations of Forward Iterators |
Expression | Effect |
*iter | Provides access to the actual element |
iter-> member | Provides access to a member of the actual element |
++iter | Steps forward (returns new position) |
iter++ | Steps forward (returns old position) |
iter1 == iter2 | Returns whether two iterators are equal |
iter1 != iter2 | Returns whether two iterators are not equal |
TYPE() | Creates iterator (default constructor) |
TYPE(iter) | Copies iterator (copy constructor) |
iter1 = iter2 | Assigns an iterator |
從iterator中表達(dá)的迭代器tags定義可以看出：
struct forward_iterator_tag : public input_iterator_tag {};
forward iterator 是以input iterator為基礎(chǔ)的。這就是給我們一個(gè)奇怪的錯(cuò)覺。語(yǔ)義上forward只限制了向前，不限制讀寫，這樣forward iterator應(yīng)該繼承input iterator和output iterator兩種。但是它只支持一種。
這里我們提出兩個(gè)原因：
首先，iterator中迭代器tags的規(guī)定只是語(yǔ)義上的規(guī)定，它對(duì)最終的具體實(shí)現(xiàn)沒有什么限制，（當(dāng)然你不按照這種方式實(shí)現(xiàn)，那將是一個(gè)不道德的行為）。所以這種定義，從本質(zhì)實(shí)現(xiàn)上并不能影響我們?cè)S多。
其次，權(quán)威的書籍中所闡述的原因是，output中，由于語(yǔ)義上不提供比較功能（這就表明不判斷是否越界）。所以forward不能全部繼承output的語(yǔ)義功能。
最后，我說(shuō)一句，這里的規(guī)定始終都是語(yǔ)義上的規(guī)定，所以基本上，forward iterator繼承誰(shuí)，都是一句屁話。這是標(biāo)準(zhǔn)，但是對(duì)于實(shí)際實(shí)現(xiàn)的程序員來(lái)說(shuō)，這些東西都是屁。
Bidirectional iterator
Additional Operations of Bidirectional Iterators |
Expression | Effect |
-- iter | Steps backward (returns new position) |
iter-- | Steps backward (returns old position) |
可以看出，雙向迭代器只是在forward iterator上面加上一個(gè)向后一步的功能。我們事實(shí)上我們知道我們通常見到的迭代器都這種，以及后面一種Random iterator.
Random iterator
Additional Operations of Random Access Iterators |
Expression | Effect |
iter[n] | Provides access to the element that has index n |
iter+=n | Steps n elements forward (or backward, if n is negative) |
iter-=n | Steps n elements backward (or forward, if n is negative) |
iter+n | Returns the iterator of the nth next element |
n+iter | Returns the iterator of the nth next element |
iter-n | Returns the iterator of the nth previous element |
iter1-iter2 | Returns the distance between iter1 and iter2 |
iter1<iter2 | Returns whether iter1 is before iter2 |
iter1>iter2 | Returns whether iter1 is after iter2 |
iter1<=iter2 | Returns whether iter1 is not after iter2 |
iter1>=iter2 | Returns whether iter1 is not before iter2 |
可以看出，Random iterator的功能主要體現(xiàn)在，在forward iterator 的基礎(chǔ)上提供了隨機(jī)存儲(chǔ)的功能，這個(gè)功能連帶提供了迭代器算數(shù)功能（指針?biāo)銛?shù)功能）以及比較功能。
-------------------------------------------------------------------------------------------
類型萃取器問題前面提到，類型萃取器用于給算法使用，同過它你可以得到有關(guān)你所操縱的迭代器的幾乎所有有用的相關(guān)類型。
namespace std {
template <class T>
struct iterator_traits {
typedef typename T::value_type value_type;
typedef typename T::difference_type difference_type;
typedef typename T::iterator_category iterator_category;
typedef typename T::pointer pointer;
typedef typename T::reference reference;
};
}
算法可以使用如下語(yǔ)句得到相關(guān)類型：
typename std::iterator_traits<T>::value_type
有些書上說(shuō)，這種設(shè)置有兩種好處：
首先，它規(guī)定了每種迭代器在定義的時(shí)候都需要提供者幾種類型信息以供被使用，從某種角度上講，它提供一種定義迭代器有關(guān)相關(guān)屬性的標(biāo)準(zhǔn)。
為了強(qiáng)行對(duì)這一標(biāo)準(zhǔn)進(jìn)行規(guī)定，在iterator頭文件中有一個(gè)結(jié)構(gòu)(struct iterator)用于給用戶定義迭代器的時(shí)候繼承的（就是接口），但是這并非是語(yǔ)法規(guī)定。事實(shí)上，如果你如果能夠保證一定會(huì)提供traits結(jié)構(gòu)中所需求的那些類型信息，不繼承這個(gè)也是可以的：
template <class Category, class T, class Distance = ptrdiff_t,
class Pointer = T*, class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
事實(shí)上，對(duì)于我們系統(tǒng)自定義的那五種迭代器，我們使用的比較多的仍然是tags。但是系統(tǒng)為了用戶子定義迭代器方便，仍然按照各自的特點(diǎn)，給他們各自定義了類似于iterator的、用于管理traits所指明的類型信息。
例如，定義特定類別迭代器的時(shí)候繼承特定結(jié)構(gòu)體，你就可以不同管trait規(guī)定的那些東西了。
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;
typedef T& 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 T, class Distance> struct forward_iterator {
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
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;
};
template <class T, class Distance> struct random_access_iterator {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef T& reference;
};
其次，它讓普通指針也被列為迭代器的一種。
namespace std {
template <class T>
struct iterator_traits<T*> {
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef random_access_iterator_tag iterator_category;
typedef T* pointer;
typedef T& reference;
};
}
如上面所說(shuō)，通過模板偏特化技術(shù)，使得當(dāng)算法獲得了普通指針作為迭代器的時(shí)候，需要同樣知道那些類型（事實(shí)上，這種情況下獲得還是比較簡(jiǎn)單的，但是需要和普通迭代器進(jìn)行統(tǒng)一，以實(shí)現(xiàn)泛型
為什么不使用常變量呢？指針沒辦法！所以traits技術(shù)最大的亮點(diǎn)就在于可以對(duì)traits類進(jìn)行特化。