《STL源碼剖析》chapter3 疊代器概念與traits程式設計技法

chapter3 疊代器概念與

traits

程式設計技法

疊代器設計思維

疊代器(iterators) 是一種抽象的設計概念，23個設計模式中有

iterator

模式，其定義如下：提供一種方法，使之能依序巡訪某個聚合物（容器）所含的各個元素，而又無需暴露該聚合物的内部表達式。

有一個重要的概念需要清楚：設計适當的相應型别，是疊代器的責任(這裡的相應型别主要指五種類型，後面會詳細介紹).設計适當的疊代器，則是容器的責任，隻有容器本身才知道該設計出怎樣的疊代器來周遊自己，并執行疊代器的各種行為（前進、後退、取值、取用成員…）。

疊代器相應型别

疊代器相應型别不隻是“疊代器所指對象的型别”一種而已，根據經驗，最常用的相應型别有五種:

1. value type

   :即疊代器所指對象的型别

2. difference type

   :用來表示兩個疊代器的距離，是以它也可以用來表示一個容器的最大容量，因為對于連續空間的容器而言，頭尾之間的距離就是其最大容量。

3. reference type

   :即疊代器所指對象的引用類型

4. pointer type

   :即疊代器所指對象的指針類别

5. iterator_category

   :疊代器的種類類别。根據移動特性與施行操作，疊代器被分為五類:

   • Input iterator

     :這種疊代器所指的對象，不允許外接改變。隻讀。

   • Output iterator

     :唯寫。

   • Forward iterator

     :允許"寫入型"算法在此種疊代器形成的區間上進行讀寫操作

   • Bidirectional iterator

     :可雙向移動。

   • Random Access iterator

     :涵蓋所有指針的算術能力。

上圖中，直線與箭頭代表的并非

C++

的繼承關系，而是所謂

concept(概念)

與

refinement(強化)

的關系。

Traits

程式設計技法

為了獲得各種不同容器中疊代器的相應型别，

STL

中使用了

Traits

程式設計技法。

如上圖所示，所謂

Traits

程式設計技法，即要求凡是

class-type iterator

都應該定義自己的相應型别，之後通過定義的

iterator_traits

友善地擷取其相應型别。

偏特化的定義是：針對（任何）template參數更近一步的條件限制所設計出來的一個特化版本。

下面以擷取

value_type

的

iterator_traits

為例進行說明，其代碼如下所示:

template<class I>
struct iterator_traits{
    typedef typename I::value_type value_type;
};
//針對原生指針而設計的“偏特化”版
template<class T>
struct iterator_traits<T*>{
    typedef T value_type;
};
//針對const原生指針而設計的“偏特化”版
template<class T>
struct iterator_traits<const T*>{
    typedef T value_type;
};

//使用iterator_traits
template<class I>
typename iterator_traits<I>::value_type
func(I ite){
    return *ite;
}
           

上述代碼針對原生指針和const原生指針專門設計了“偏特化”版本，目的是使得

STL

對原始指針同樣支援。

iterator_category

可以使得選擇算法時，選擇一個最優的算法，比如下面這個例子：

template<class InputIterator,class Distance>
void advance_II(InputIterator& i,Distance n){
    //單向，逐一前進
    while(n--) ++i;
}

template<class BidirectionalIterator,class Distance>
void advance_BI(BidirectionalIterator& i,Distance n){
    //雙向，逐一前進
    if(n>=0)
        while(n--) ++i;
    else
        while(n++) --i;
}

template<class RandomAccessIterator,class Distance>
void advance_RAI(RandomAccessIterator& i,Distance n){
    //跳躍前進
    i+=n;
}
           

當程式調用

advance()

時，如果對于

Random Access Iterator

選擇

advance_II

，原本

O(1)

的操作成為了

O(n)

,這是極其缺乏效率的。是以才引入了

iterator_category

，使得算法可以進行重載決議，選擇最優的算法。

iterator_category

的實作及使用如下所示:

//五個作為标記用的型别(tag types)
//隻是作為标記用，是以不需要任何成員
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 { };

//重載使用不同種類的__advance
template<class InputIterator,class Distance>
inline void __advance(InputIterator& i,Distance n,
                        input_iterator_tag){
    //單向，逐一前進
    while(n--) ++i;
}

template<class ForwardIterator,class Distance>
inline void __advance(ForwardIterator& i,Distance n,
                        forward_iterator_tag){
    //單純地進行傳遞調用
    advance(i,n,input_iterator_tag());
}


template<class BidirectionalIterator,class Distance>
inline void __advance(BidirectionalIterator& i,Distance n,
                        bidirectional_iterator_tag){
    //雙向，逐一前進
    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){
    //跳躍前進
    i+=n;
}

//定義上層函數
template<class InputIterator,class Distance>
inline void advance(InputIterator& i,Distance n){
    __advance(i,n,iterator_traits<InputerIterator>::iterator_category());
}

//iterator_traits定義如下
template<class I>
struct iterator_traits{
    //...
    typedef typename I::iterator_category iterator_category;
};

template<class T>
struct iterator_traits<T*>{
    //...
    typedef random_access_iterator_tag iterator_category;
};

template<class T>
struct iterator_traits<const T*>{
    //..
    //注意，原生的pointer-to-const是一種Random Access Iterator
    typedef random_access_iterator_tag iterator_category;
};
           

advanced()

函數按理說可以接受各種類型的疊代器，還為什麼要将其型别參數命名為

InputIterator

?這其實是

STL

算法的一個命名規則：以算法所能接受之最低階疊代器類型，來為其疊代器型别參數命名。

然後為什麼五個用于标記的型别要使用繼承體系呢？原因是可以利用派生類向基類的轉換這一特性，避免不必要的類型判斷。(這裡可能沒有講清楚，可以參考《STL源碼剖析》p94頁)

std::iterator的保證

為了符合規範，任何疊代器都應該提供五個内嵌相應型别，以利于

traits

萃取。

STL

提供了一個

iterator class

如下，如果每個新設計的疊代器都繼承自它，就可保證複合

STL

所需之規範:

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;
};

//使用例子
//定義list的iterator
template<class Item>
struct ListIter:public std::iterator<std::forward_iterator_tag,Item>
{ //... }
           

最後

參考《STL源碼剖析》chapter3,我自己實作的

iterator

的源代碼及本節所有代碼可以參考github.