天天看點
傳回

STL源碼學習（一）疊代器概念與traits程式設計技法類型萃取内嵌類型小結

STL的中心思想在于：将資料容器和算法分開，彼此獨立設計，最後再以一貼膠着劑将它們撮合在一起。這種膠着劑便是疊代器，疊代器設計的目的在于可以友善的擷取(周遊)容器中的資料同時又不暴露容器的内部實作。

比如說，當使用一個連結清單疊代器時，使用者根本不會知道資料在連結清單中是如何存儲的。這帶來的好處是，所有的STL算法隻需要接收疊代器最為參數就夠了，根本不用管是哪個容器的疊代器，隻要能夠擷取資料，通過疊代器改變資料就可以了。

不過，疊代器的實作并不是那麼簡單，因為在通常使用疊代器時，可能還需要知道疊代器指向的資料類型，比如某些算法中需要定義一個同類型的變量。這就産生了沖突，因為既不想暴露底層資料，又必須知道資料的類型，後面會看到，通過traits技法，可以很容易擷取疊代器所指類型

類型萃取

traits技法

作為容器專屬的疊代器，容器中儲存的資料類型疊代器是知道的(因為需要作為模闆參數)，是以如果在疊代器中定義内嵌類型，就可以擷取疊代器所指資料的類型，比如定義MyIter疊代器

template <class T>
struct MyIter
{
    /* 定義T的别名 */
    typedef T value_type;
    T* ptr;
    MyIter(T* p = ) : ptr(p) {}
    T& operator*() const { return *ptr; }
    //...
};

templace <class I>
/* 使用I的内嵌了類型擷取疊代器所指資料類型 */
typename I::value_type
func(I ite)
{
    return *ite;
}

//...
MyIter<int> ite(new int());
cout << func(ite);  //輸出8
當使用作用域符号表達一個類型時，需要在前面添加typename顯式指出這是一個型别。因為I是一個模闆參數，在具現化之前，編譯器對I一無所知，根本不知道I::value_type是什麼，是以需要顯式告訴編譯器，這是一個型别

Traits就是對上述内嵌類型擷取疊代器所指資料類型方法的封裝，形象地稱為”萃取”疊代器特性，而value_type正是疊代器特性之一

/* 用于萃取疊代器類型，疊代器指向元素的類型等
 * 使用時可以直接使用
 * iterator_traits<I>::value_type擷取疊代器指向元素類型 */
template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::value_type        value_type;
};

通過這個萃取器，如果Iterator聲明有value_type内嵌類型，那麼就可以使用如下方法擷取疊代器Iterator所指類型

templace <class I>
/* 函數傳回型别，通過iterator_traits從I中萃取出它儲存的資料類型 */
typename iterator_traits<I>::value_type 
func(I iter)
{
    return *iter;
}

指針特化版本

多了一層間接性帶來的好處是可以為iterator_traits定義特化版本，由于原生指針也可以算作疊代器的一種，是以像iterator_traits\

/* 針對原生指針的偏特化版本，因為指針沒有内嵌類型 */
template <class T>
struct iterator_traits<T*> {
  typedef T                          value_type;
};

/* 針對常量指針的偏特化版本 */
template <class T>
struct iterator_traits<const T*> {
  typedef T                          value_type;
};

有了上面的特化版本，當使用iterator_traits\

内嵌類型

定義

疊代器部分隻有iterator_traits萃取功能不容易了解，剩下的部分是關于疊代器型别的，包括

  • value type，疊代器指向的資料值類型
  • different type，疊代器差類型
  • reference type，疊代器指向的資料引用類型
  • pointer type，疊代器指向的資料指針類型
  • iterator_category，疊代器類型

這幾種類型在萃取器iterator_traits中也都有相應的定義，用于萃取出相應型别，同上述的valut_type一樣

/* 用于萃取疊代器類型，疊代器指向元素的類型等 */
/* 使用時可以直接使用
 * iterator_traits<I>::iteartor_category擷取疊代器I的類型
 * iterator_traits<I>::value_type擷取疊代器指向元素類型
 * 依次類推 */
template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_type;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};
  • value type實際上就是疊代器所指對象的型别，也就是模闆參數T。假設使用MyIter it疊代器，那麼value type就是int
  • difference type是指疊代器之間的距離類型，如兩個疊代器作差，儲存疊代器之間的距離等，其類型就是difference type，這個類型通常是ptrdiff_t類型
  • reference type是指疊代器所指對象的引用類型，通常是T&
  • pointer type是指疊代器所指對象的指針類型，通常是T* 
typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T&                         reference;
  typedef T*                         pointer;

疊代器類型

在STL中，根據疊代器所支援的算術運算，實際上存在多種類型的疊代器，分别是

  • input iterator隻讀疊代器，不可以改變疊代器所指對象。隻支援++操作
  • ouput iterator隻寫疊代器，允許改變疊代器所指對象。隻支援++操作
  • forward iterator前向疊代器，可讀寫。隻支援++操作
  • bidirectional iterator雙向疊代器，可讀寫。支援++和–操作
  • random access iterator随機疊代器，可讀寫。支援所有指針算術操作，包括+,-,+=,-=,++,–等

可以看到，不同類型的疊代器可以提供不同的功能，但這同時也帶來了一些問題，以advance函數為例，該函數将給定的疊代器移動n步，然而，不同類型的疊代器支援不同的算術操作，如果都使用++，那麼對随機疊代器而言就過于耗時(因為本可以直接使用+=)。這就是iterator_category疊代器類型的作用，結合模闆的參數推導區分不同的疊代器類型，同時采用最有效的方法進行算術操作

模闆函數參數推導功能保證根據參數類型選擇最合适的重載函數，是以在STL中，提供了五個類定義分别對應五個疊代器類型

/* 定義疊代器類型，每個疊代器中都會将自己疊代器類型typedef成iterator_categories
 * 由于C++不支援直接擷取類型操作，是以需要利用模闆參數推導實作不同類型的不同操作 */
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 {};

這五個類定義的繼承關系和疊代器之間的繼承關系相同，另外這五個類是空類，因為它的作用僅僅是作為模闆參數用于函數重載

在疊代器的定義中會根據自身所支援的功能最強的疊代器類型定義iterator_category，如

typedef random_access_iterator_tag iterator_category;

這樣，當再次使用advance函數時，傳入自己的疊代器類型對應的類，同時根據模闆參數推導就可以調用不同的函數

/* 将疊代器i移動n步，n可正可負 */
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
    /* 不同疊代器支援的操作不同
     * 隻讀，隻寫，正向疊代器隻支援++操作
     * 雙向疊代器支援++，--操作
     * 随機疊代器支援+=，-=，++，--操作
     * 為了根據不同疊代器選擇不同的__advance函數，采用模闆參數推導的方法實作重載 */
    /* iterator_category()也是一個模闆重載，用于建立一個疊代器i的tag對象
     * 根據模闆參數推導，可以實作__advance重載 */
  __advance(i, n, iterator_category(i));
}
模闆參數中疊代器類型是InputIterator類型的原因是STL将模闆參數類型設定為最弱的類型(類似繼承體系中的基類)，實際類型會根據i實際的類型判斷(類似于繼承體系中的多态)

iterator_category函數用于擷取疊代器對應的tag對象

/* 傳回疊代器類型對象，注意傳回的是一個類對象
 * 這是因為模闆參數推導隻針對類對象進行推導*/
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}

至此，根據__advance(i, n, iterator_category(i))函數調用的第三個參數類型，模闆參數推導可以實作調用不同的函數

/* 針對隻讀疊代器的__advance重載 */
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
  while (n--) ++i;
}


/* 針對雙向疊代器的__advance重載 */
template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, 
                      bidirectional_iterator_tag) {
  if (n >= )
    while (n--) ++i;
  else
    while (n++) --i;
}

/* 針對随機疊代器的__advance重載 */
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, 
                      random_access_iterator_tag) {
  i += n;
}
STL中隻提供了三個__advance函數重載，這是因為上述的繼承體系。由于output疊代器，forward疊代器的__advane操作和input疊代器的操作相同，是以完全可以向上調用input疊代器的對應函數(好比調用派生類的某個函數，但是派生類中不存在這個函數，就會向上調用基類的對應函數)

小結

疊代器部分的難點有兩個，一個是通過traits技法實作類型萃取，另一個是通過模闆參數推導實作函數重載。不過真正看過源碼後會發現其實并不困難，當然，STL需要内部的疊代器都遵循它的規定，即定義上述的五個型别

STL
上一篇: STL源碼剖析 疊代器（iterator）概念與程式設計技法（三）
下一篇: STL源碼剖析之疊代器與traits程式設計技法

繼續閱讀