【STL 源碼剖析】淺談 STL 迭代器與 traits 編程技法
大家好,我是小賀。
點贊再看,養成習慣
文章每周持續更新,可以微信搜索「herongwei」第一時間閱讀和催更,本文 GitHub : //github.com/rongweihe/MoreThanCPlusPlus 已經收錄,有一線大廠面試點思維導圖,也整理了很多我的文檔,歡迎 star 和完善。一起加油,變得更好!
前言
上一篇,我們剖析了 STL 空間配置器,這一篇文章,我們來學習下 STL 迭代器以及背後的 traits 編程技法。
在 STL 編程中,容器和算法是獨立設計的,容器裏面存的是數據,而算法則是提供了對數據的操作,在算法操作數據的過程中,要用到迭代器,迭代器可以看做是容器和算法中間的橋樑。
1、迭代器設計模式
為何說迭代器的時候,還談到了設計模式?這個迭代器和設計模式又有什麼關係呢?
其實,在《設計模式:可復用面向對象軟件的基礎》(GOF)這本經典書中,談到了 23 種設計模式,其中就有 iterator 迭代模式,且篇幅頗大。
碰巧,筆者在研究 STL 源碼的時候,同樣的發現有 iterator 迭代器,而且還佔據了一章的篇幅。
在設計模式中,關於 iterator 的描述如下:一種能夠順序訪問容器中每個元素的方法,使用該方法不能暴露容器內部的表達方式。而類型萃取技術就是為了要解決和 iterator 有關的問題的。
有了上面這個基礎,我們就知道了迭代器本身也是一種設計模式,其設計思想值得我們仔細體會。
那麼 C++ STL 實現 iterator 和 GOF 介紹的迭代器實現方法什麼區別呢? 那首先我們需要了解 C++ 中的兩個編程範式的概念,OOP(面向對象編程)和 GP(泛型編程)。
在 C++ 語言裏面,我們可用以下方式來簡單區分一下 OOP 和 GP :
OOP:將 methods 和 datas 關聯到一起 (通俗點就是方法和成員變量放到一個類中實現),通過繼承的方式,利用虛函數表(virtual)來實現運行時類型的判定,也叫”動態多態”,由於運行過程中需根據類型去檢索虛函數表,因此效率相對較低。
GP:泛型編程,也被稱為”靜態多態”,多種數據類型在同一種算法或者結構上皆可操作,其效率與針對某特定數據類型而設計的算法或者結構相同, 具體數據類型在編譯期確定,編譯器承擔更多,代碼執行效率高。在 STL 中利用 GP 將 methods 和 datas 實現了分而治之。
而 C++ STL 庫的整個實現採用的就是 GP(Generic Programming),而不是 OOP(Object Oriented Programming)。而 GOF 設計模式採用的就是繼承關係實現的,因此,相對來講,C++ STL 的實現效率會相對較高,而且也更有利於維護。
在 STL 編程結構裏面,迭代器其實也是一種模板 class
,迭代器在 STL 中得到了廣泛的應用,通過迭代器,容器和算法可以有機的綁定在一起,只要對算法給予不同的迭代器,比如 vector::iterator、list::iterator,std::find()
就能對不同的容器進行查找,而無需針對某個容器來設計多個版本。
這樣看來,迭代器似乎依附在容器之下,那麼,有沒有獨立而適用於所有容器的泛化的迭代器呢?這個問題先留着,在後面我們會看到,在 STL 編程結構裏面,它是如何把迭代器運用的爐火純青。
2、智能指針
STL 是泛型編程思想的產物,是以泛型編程為指導而產生的。具體來說,STL 中的迭代器將范型算法 (find, count, find_if)
等應用於某個容器中,給算法提供一個訪問容器元素的工具,iterator
就扮演着這個重要的角色。
稍微看過 STL 迭代器源碼的,就明白迭代器其實也是一種智能指針,因此,它也就擁有了一般指針的所有特點—— 能夠對其進行 *
和 ->
操作。
template<typename T>
class ListIterator {//mylist迭代器
public:
ListIterator(T *p = 0) : m_ptr(p){} //構造函數
T& operator*() const { return *m_ptr;} //取值,即dereference
T* operator->() const { return m_ptr;} //成員訪問,即member access
//...
};
但是在遍歷容器的時候,不可避免的要對遍歷的容器內部有所了解,所以,乾脆把迭代器的開發工作交給容器的設計者,如此以來,所有實現細節反而得以封裝起來不被使用者看到,這也正是為什麼每一種 STL 容器都提供有專屬迭代器的緣故。
比如筆者自己實現的 list
迭代器在這裡使用的好處主要有:
- (1) 不用擔心內存泄漏(類似智能指針,析構函數釋放內存);
- (2) 對於
list
,取下一個元素不是通過自增而是通過next
指針來取,使用智能指針可以對自增進行重載,從而提供統一接口。
3、template 參數推導
參數推導能幫我們解決什麼問題呢?
在算法中,你可能會定義一個簡單的中間變量或者設定算法的返回變量類型,這時候,你可能會遇到這樣的問題,假如你需要知道迭代器所指元素的類型是什麼,進而獲取這個迭代器操作的算法的返回類型,但是問題是 C++
沒有 typeof
這類判斷類型的函數,也無法直接獲取,那該如何是好?
注意是類型,不是迭代器的值,雖然 C++
提供了一個 typeid()
操作符,這個操作符只能獲得型別的名稱,但不能用來聲明變量。要想獲得迭代器型別,這個時候又該如何是好呢?
function template
的參數推導機制是一個不錯的方法。
例如:
如果 I
是某個指向特定對象的指針,那麼在 func 中需要指針所指向對象的型別的時候,怎麼辦呢?這個還比較容易,模板的參數推導機制可以完成任務,
template <class I>
inline void func(I iter) {
func_imp(iter, *iter); // 傳入 iter 和 iter 所指的值,class 自動推導
}
通過模板的推導機制,就能輕而易舉的獲得指針所指向的對象的類型。
template <class I, class T>
void func_imp(I iter, T t) {
T tmp; // 這裡就是迭代器所指物的類別
// ... 功能實現
}
int main() {
int i;
func(&i);//這裡傳入的是一個迭代器(原生指針也是一種迭代器)
}
上面的做法呢,通過多層的迭代,很巧妙地導出了 T
,但是卻很有局限性,比如,我希望 func()
返回迭代器的 value type
類型返回值, 函數的 “template
參數推導機制” 推導的只是參數,無法推導函數的返回值類型。萬一需要推導函數的返回值,好像就不行了,那麼又該如何是好?
這就引出了下面的內嵌型別。
4、聲明內嵌型別
上述所說的 迭代器所指對象的型別,稱之為迭代器的 value type
。
儘管在 func_impl
中我們可以把 T
作為函數的返回值,但是問題是用戶需要調用的是 func
。
如果在參數推導機制上加上內嵌型別 (typedef)
呢?為指定的對象類型定義一個別名,然後直接獲取,這樣來看一下實現:
template<typename T>
class MyIter {
public:
typedef T value_type; //內嵌類型聲明
MyIter(T *p = 0) : m_ptr(p) {}
T& operator*() const { return *m_ptr;}
private:
T *m_ptr;
};
//以迭代器所指對象的類型作為返回類型
//注意typename是必須的,它告訴編譯器這是一個類型
template<typename MyIter>
typename MyIter::value_type Func(MyIter iter) {
return *iter;
}
int main(int argc, const char *argv[]) {
MyIter<int> iter(new int(666));
std::cout<<Func(iter)<<std::endl; //print=> 666
}
上面的解決方案看着可行,但其實呢,實際上還是有問題,這裡有一個隱晦的陷阱:實際上並不是所有的迭代器都是 class type
,原生指針也是一種迭代器,由於原生指針不是 class type
,所以沒法為它定義內嵌型別。
因為 func
如果是一個泛型算法,那麼它也絕對要接受一個原生指針作為迭代器,下面的代碼編譯沒法通過:
int *p = new int(5);
cout<<Func(p)<<endl; // error
要解決這個問題,Partial specialization
(模板偏特化)就出場了。
5、Partial specialization(模板偏特化)
所謂偏特化是指如果一個 class template
擁有一個以上的 template
參數,我們可以針對其中某個(或多個,但不是全部)template
參數進行特化,比如下面這個例子:
template <typename T>
class C {...}; //此泛化版本的 T 可以是任何類型
template <typename T>
class C<T*> {...}; //特化版本,僅僅適用於 T 為「原生指針」的情況,是泛化版本的限制版
所謂特化,就是特殊情況特殊處理,第一個類為泛化版本,T
可以是任意類型,第二個類為特化版本,是第一個類的特殊情況,只針對原生指針。
5.1、原生指針怎麼辦?——特性 「萃取」 traits
還記得前面說過的參數推導機制+內嵌型別機制獲取型別有什麼問題嗎?問題就在於原生指針雖然是迭代器但不是class
,無法定義內嵌型別,而偏特化似乎可以解決這個問題。
有了上面的認識,我們再看看 STL
是如何應用的。STL
定義了下面的類模板,它專門用來「萃取」迭代器的特性,而value type
正是迭代器的特性之一:
traits
在 bits/stl_iterator_base_types.h
這個文件中:
template<class _Tp>
struct iterator_traits<_Tp*> {
typedef ptrdiff_t difference_type;
typedef typename _Tp::value_type value_type;
typedef typename _Tp::pointer pointer;
typedef typename _Tp::reference reference;
typedef typename _Tp::iterator_category iterator_category;
};
template<typename Iterator>
struct iterator_traits { //類型萃取機
typedef typename Iterator::value_type value_type; //value_type 就是 Iterator 的類型型別
}
加入萃取機前後的變化:
template<typename Iterator> //萃取前
typename Iterator::value_type func(Iterator iter) {
return *iter;
}
//通過 iterator_traits 作用後的版本
template<typename Iterator> //萃取後
typename iterator_traits<Iterator>::value_type func(Iterator iter) {
return *iter;
}
看到這裡也許你會問了,這個萃取前和萃取後的 typename :iterator_traits::value_type
跟 Iterator::value_type
看起來一樣啊,為什麼還要增加 iterator_traits
這一層封裝,豈不是多此一舉?
回想萃取之前的版本有什麼缺陷:不支持原生指針。而通過萃取機的封裝,我們可以通過類模板的特化來支持原生指針的版本!如此一來,無論是智能指針,還是原生指針,iterator_traits::value_type 都能起作用,這就解決了前面的問題。
//iterator_traits的偏特化版本,針對迭代器是原生指針的情況
template<typename T>
struct iterator_traits<T*> {
typedef T value_type;
};
看到這裡,我們不得不佩服的 STL 的設計者們,真·秒啊!我們用下面這張圖來總結一下前面的流程:
5.2 、const 偏特化
通過偏特化添加一層中間轉換的 traits 模板 class,能實現對原生指針和迭代器的支持,有的讀者可能會繼續追問:對於指向常數對象的指針又該怎麼處理呢?比如下面的例子:
iterator_traits<const int*>::value_type // 獲得的 value_type 是 const int,而不是 int
const 變量只能初始化,而不能賦值(這兩個概念必須區分清楚)。這將帶來下面的問題:
template<typename Iterator>
typename iterator_traits<Iterator>::value_type func(Iterator iter) {
typename iterator_traits<Iterator>::value_type tmp;
tmp = *iter; // 編譯 error
}
int val = 666 ;
const int *p = &val;
func(p); // 這時函數里對 tmp 的賦值都將是不允許的
那該如何是好呢?答案還是偏特化,來看實現:
template<typename T>
struct iterator_traits<const T*> { //特化const指針
typedef T value_type; //得到T而不是const T
}
6、traits編程技法總結
通過上面幾節的介紹,我們知道,所謂的 traits 編程技法無非 就是增加一層中間的模板 class
,以解決獲取迭代器的型別中的原生指針問題。利用一個中間層 iterator_traits
固定了 func
的形式,使得重複的代碼大量減少,唯一要做的就是稍稍特化一下 iterator_tartis
使其支持 pointer
和 const pointer
。
#include <iostream>
template <class T>
struct MyIter {
typedef T value_type; // 內嵌型別聲明
T* ptr;
MyIter(T* p = 0) : ptr(p) {}
T& operator*() const { return *ptr; }
};
// class type
template <class T>
struct my_iterator_traits {
typedef typename T::value_type value_type;
};
// 偏特化 1
template <class T>
struct my_iterator_traits<T*> {
typedef T value_type;
};
// 偏特化 2
template <class T>
struct my_iterator_traits<const T*> {
typedef T value_type;
};
// 首先詢問 iterator_traits<I>::value_type,如果傳遞的 I 為指針,則進入特化版本,iterator_traits 直接回答;如果傳遞進來的 I 為 class type,就去詢問 T::value_type.
template <class I>
typename my_iterator_traits<I>::value_type Func(I ite) {
std::cout << "normal version" << std::endl;
return *ite;
}
int main(int argc, const char *argv[]) {
MyIter<int> ite(new int(6));
std::cout << Func(ite)<<std::endl;//print=> 6
int *p = new int(7);
std::cout<<Func(p)<<std::endl;//print=> 7
const int k = 8;
std::cout<<Func(&k)<<std::endl;//print=> 8
}
上述的過程是首先詢問 iterator_traits::value_type
,如果傳遞的 I 為指針,則進入特化版本, iterator_traits
直接回答T
;如果傳遞進來的 I
為 class type
,就去詢問 T::value_type
。
通俗的解釋可以參照下圖:
總結:核心知識點在於 模板參數推導機制+內嵌類型定義機制, 為了能處理原生指針這種特殊的迭代器,引入了偏特化機制。traits
就像一台 「特性萃取機」,把迭代器放進去,就能榨取出迭代器的特性。
這種偏特化是針對可調用函數 func
的偏特化,想像一種極端情況,假如 func
有幾百萬行代碼,那麼如果不這樣做的話,就會造成非常大的代碼污染。同時增加了代碼冗餘。
7、迭代器的型別和種類
7.1 迭代器的型別
我們再來看看迭代器的型別,常見迭代器相應型別有 5 種:
-
value_type
:迭代器所指對象的類型,原生指針也是一種迭代器,對於原生指針 int*,int 即為指針所指對象的類型,也就是所謂的 value_type 。 -
difference_type
: 用來表示兩個迭代器之間的距離,對於原生指針,STL 以 C++ 內建的 ptrdiff_t 作為原生指針的 difference_type。 -
reference_type
: 是指迭代器所指對象的類型的引用,reference_type 一般用在迭代器的 * 運算符重載上,如果 value_type 是 T,那麼對應的 reference_type 就是 T&;如果 value_type 是 const T,那麼對應的reference_type 就是 const T&。 -
pointer_type
: 就是相應的指針類型,對於指針來說,最常用的功能就是 operator* 和 operator-> 兩個運算符。 -
iterator_category
: 的作用是標識迭代器的移動特性和可以對迭代器執行的操作,從 iterator_category 上,可將迭代器分為 Input Iterator、Output Iterator、Forward Iterator、Bidirectional Iterator、Random Access Iterator 五類,這樣分可以儘可能地提高效率。template<typename Category, typename T, typename Distance = ptrdiff_t, typename Pointer = T*, typename Reference = T&> struct iterator //迭代器的定義 { typedef Category iterator_category; typedef T value_type; typedef Distance difference_type; typedef Pointer pointer; typedef Reference reference; };
iterator class 不包含任何成員變量,只有類型的定義,因此不會增加額外的負擔。由於後面三個類型都有默認值,在繼承它的時候,只需要提供前兩個參數就可以了。這個類主要是用來繼承的,在實現具體的迭代器時,可以繼承上面的類,這樣子就不會漏掉上面的 5 個型別了。
對應的迭代器萃取機設計如下:
tempalte<typename I>
struct iterator_traits {//特性萃取機,萃取迭代器特性
typedef typename I::iterator_category iterator_category;
typedef typename I::value_type value_type;
typedef typeanme I:difference_type difference_type;
typedef typename I::pointer pointer;
typedef typename I::reference reference;
};
//需要對型別為指針和 const 指針設計特化版本看
7.2、迭代器的分類
最後,我們來看看,迭代器型別 iterator_category
對應的迭代器類別,這個類別會限制迭代器的操作和移動特性。
除了原生指針以外,迭代器被分為五類:
Input Iterator
: 此迭代器不允許修改所指的對象,是只讀的。支持 ==、!=、++、*、-> 等操作。Output Iterator
:允許算法在這種迭代器所形成的區間上進行只寫操作。支持 ++、* 等操作。Forward Iterator
:允許算法在這種迭代器所形成的區間上進行讀寫操作,但只能單向移動,每次只能移動一步。支持 Input Iterator 和 Output Iterator 的所有操作。Bidirectional Iterator
:允許算法在這種迭代器所形成的區間上進行讀寫操作,可雙向移動,每次只能移動一步。支持 Forward Iterator 的所有操作,並另外支持 – 操作。Random Access Iterator
:包含指針的所有操作,可進行隨機訪問,隨意移動指定的步數。支持前面四種 Iterator 的所有操作,並另外支持 [n] 操作符等操作。
那麼,這裡,小賀想問大家,為什麼我們要對迭代器進行分類呢?迭代器在具體的容器里是到底如何運用的呢?這個問題就放到下一節在講。
最最後,我們再來回顧一下六大組件的關係:
這六大組件的交互關係:container(容器) 通過 allocator(配置器) 取得數據儲存空間,algorithm(算法)通過 iterator(迭代器)存取 container(容器) 內容,functor(仿函數) 可以協助 algorithm(算法) 完成不同的策略變化,adapter(配接器) 可以修飾或套接 functor(仿函數)。
參考文章:
-
《STL源碼剖析-侯捷》
8、結尾
如果覺得文章對你有幫助,歡迎分享給你的朋友,一鍵三連,謝謝各位。
我是 herongwei ,是男人,就對自己狠一點,祝大家工作愉快,我們下期見。