迭代器榨汁機(jī)
template<typename I>
struct iterator_traits{
typedef typename I::iterator_category
typedef typename I::value_type;
typedef typename I::difference_type;
typedef typename I::pointer;
typedef typename I::reference;
}
迭代器型別
迭代器型別之一：value_type
value_type 是指對(duì)象的型別碍脏，每一個(gè)打算與STL算法完美搭配的class，都應(yīng)該定義自己的value_type內(nèi)嵌型別役拴。-
迭代器型別之二：difference_type
difference_type用來(lái)表示2個(gè)迭代器的距離急黎，因此它可以用來(lái)表示容器的最大容量。通常STL中泛型算法提供的計(jì)數(shù)功能功能淤击，例如STL中的count()故源。template <typename I, typename T> typename iterator_traits<I>::difference_type count( I first, I last, count T& value){ typename iterator_traits<I>::difference_type n = 0; for (; first != last; first++) if (*first == value) ++n; return n; } -
迭代器相應(yīng)型別之三：reference_type
迭代器所指之物的內(nèi)容是否允許改變， 迭代器分為2類印机，- 不允許改變“所指對(duì)象之內(nèi)容者”稱為constant iterators 例如 const int* pic。
- 允許改變“所指對(duì)象之內(nèi)容者” 稱為mutable iterators多柑，例如int *pi楣责。
提領(lǐng)constant iterators是一個(gè)右值。提領(lǐng)mutable iterators是一個(gè)左值初嘹。
-
迭代器相應(yīng)型別之四：pointer type
reference_type 表示迭代器所指之物沮趣，那么pointer type則表示迭代器所指之物的地址。// 針對(duì)原生指針而設(shè)計(jì)的"偏特化版" template <typename T> struct iterator_traits<T*> { ...... typedef T* pointer; typedef T& reference; } // 針對(duì)原生的pointer-to-const而設(shè)計(jì)的"偏特化" template <typename T> struct iterator_traits<const T*> { ...... typedef T* pointer; typedef T& reference; } -
迭代器相應(yīng)型別之五：Iterator_category
根據(jù)移動(dòng)特性與施行操作迭代器被分為5類- Input Iterator：這種迭代器所指的對(duì)象驻龟，不允許外界改變育叁，只讀。
- Output Iterator：只寫
- Forward Iterator：允許寫入型算法在此種迭代器所形成的區(qū)間上進(jìn)行讀寫操作谴蔑。
- Bidirectional Iterator：可雙向移動(dòng)龟梦，某些算法需要逆向走訪某個(gè)區(qū)間。
- Random AccessIterator：前4種迭代器只提供一部分指針?biāo)阈g(shù)能力钦睡，(前3種支持operator++躁倒，第4種支持operator--)，第5種則涵蓋所有指針?biāo)阈g(shù)能力褐桌。
為什么需要區(qū)分這么多的迭代器種類象迎？因?yàn)槲覀冊(cè)谠O(shè)計(jì)算法時(shí)呛踊，應(yīng)該針對(duì)某種強(qiáng)化的迭代器提供另一種定義谭网，這樣才能提供最大的效率赃春。
任何一個(gè)迭代器，其類型應(yīng)該落在"該迭代器所隸屬的各種類型中薄辅，最強(qiáng)化的那個(gè)"抠璃，例如脱惰，int* 既是RandomAccess Iterator，又是Bidirectional Iterator采盒，同時(shí)也是Forward Iterator蔚润，而且也是Input Iterator，那么其類型應(yīng)該歸屬為random_access_iterator烦租。
比如以advanced()為例.
template <typename InputIterator, typename Distance>
void advance_II(InputIterator& i, Distance n){
while(n--)
++i;
}
template <typename BidirectionalIterator, typename Distance>
void advance_BI(BidirectionalIterator& i, Distance n){
if (n >= 0)
while(n--)
++i;
else
while(n++)
--i;
}
template <typename RandomAccessIterator, typename Distance>
void advance_RAI(RandomAccessIterator& i, Distance n){
i += n;
}
template <typename InputIterator, typename Distance>
void advance(InputIterator& i, Distance n){
if (is_random_access_iterator(i)) // 有待實(shí)現(xiàn)叉橱。
advanced_RAI(i, n);
}
像在advanced中者蠕，通過(guò)判斷不同迭代器類型來(lái)調(diào)用不同的函數(shù)。第一種方法是多態(tài)粪小，但運(yùn)行期才確定未免成本太高抡句，同時(shí)胡亂繼承多態(tài)也是把問(wèn)題復(fù)雜化。第二種就是函數(shù)重載突想，我們可以事先標(biāo)記不同迭代器類型，
并將其作為第3個(gè)參數(shù)傳給advanced猾担。
// 以下只做標(biāo)記迭代器category之用
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 <typename InputIterator, typename Distance>
inline void advance(InputIterator &iter, Distance n){
typedef typename iterator_traits<InputIterator>::iterator_category category;
__advance(iter, n, category());
}
template <typename RandomAccessIterator, typename Distance>
void __advance(RandomAccessIterator iter, Distance n, random_access_iterator_tag){
iter += n;
}
template <typename InputIterator, typename Distance>
void __advance(InputIterator iter, Distance n, input_iterator_tag){
while(n--)
iter++;
}
template <typename BidirectionalIterator, typename Distance>
void __advance(BidirectionalIterator iter, Distance n, bidirectional_iterator_tag){
if (n >= 0)
while(n--)
iter++;
else
while(n++)
iter--;
}
__advanced中的第三個(gè)參數(shù)僅僅是激活重載稽荧。但我們還需要一個(gè)提供上層統(tǒng)一的接口工腋，在這一層中通過(guò)traits機(jī)制，將迭代器類型推導(dǎo)出來(lái)擅腰。
