以deque為例詳細解析容器、疊代器

C++是令人着迷的一門程式設計語言，容器和疊代器是是C++的重要組分。容器和疊代器算是比較容易了解，容器是靜态的，是負責存儲資料的，比如數組，連結清單，二叉樹等，疊代器是和容器密切相關的，是針對特定容器設計出來的資料通路器。二者緊密相連，為算法等建構提供基礎設施建設。下面就從源碼實作角度，詳細解析容器和疊代器的關系，分析對象為STL中的deque（雙端隊列）。

從源碼角度考察容器和疊代器之間的關系。

容器源碼：

template<class T,class Alloc=alloc,size_t BufSize=0>
class deque{
public:
        .....
protected:
        iterator start;
        iterator finish;
public:
iterator begin(){return start;}
iterator end(){return finish;}

 }
           

疊代器源碼：

template<class T,class Ref,class Ptr,size_t BufSiz>
struct __deque_iterator
{
T *cur;
T *first;
T *last;
}
           

首先要明白的一點是提供容器的同時必須要提供疊代器。看一下二者的“互相滲入”吧，首先對于容器來說，會提供兩個疊代器(也可以認為是兩個指針)分别指向容器的頭和尾。

疊代器的結構中，會有三個容器所容資料類型的指針，cur、first以及last，這三個指針将來是要深入容器中資料結構内部的。好了，二者的結合點，可以用這樣了解：容器和疊代器兩人對彼此都很了解，因為出自同一人之手，容器為疊代器提供了一個頭尾指針，疊代器内相應的指針，能夠在容器中自由遊走。下面先看看，疊代器是怎樣在容器中自由遊走的。