在C++中編寫我自己的stl-like迭代器實現

Question

我目前正在嘗試理解各種語言中迭代器的內在性，即它們實現的方式。

例如，有以下類暴露列表界面。

template<class T> 
class List 
{ 

    public: 

    virtual void Insert(int beforeIndex, const T item) throw(ListException) =0 ; 
    virtual void Append(const T item) =0; 

    virtual T Get(int position) const throw(ListException) =0; 
    virtual int GetLength() const =0; 

    virtual void Remove(int position) throw(ListException) =0; 


    virtual ~List() =0 {}; 
}; 

根據四人幫，實現能夠支持不同類型的遍歷的迭代器的最佳方式是創建基本的迭代器類（列表的朋友）與可訪問列表的成員保護的方法。 Iterator的具體實現將以不同的方式處理作業，並通過基本接口訪問List的私有和受保護數據。

從這裏開始，事情變得混亂。說，我有類LinkedList和ArrayList，都從List派生，並且還有相應的迭代器，每個類都返回。我怎樣才能實現LinkedListIterator？我完全沒有想法。基類迭代器類可以從列表中檢索什麼樣的數據（這是一個純粹的接口，而所有派生類的實現差別很大）？

Answer 1

STL並沒有真正使用抽象基類和虛函數。相反，它被有意設計成不是OO（在GoF意義上）並且完全基於模板，旨在「編譯時多態性」。模板不關心抽象接口。只要它們具有足夠類似的接口（例如，如果您打電話給Appendpush_back而不是更多的代碼，期望符合STL的容器可以爲您工作，如std::back_insert_iterator）。

一個兼容STL的迭代器將不得不超負荷很多運營商的表現就像一個指針（儘可能，考慮到容器的限制），包括*，->，++，--（如果雙向 - 雙鏈接）， ==和!=。

Answer 2

C++標準庫在迭代器的實現中不使用多態和繼承;相反，它使用C++模板元編程和「概念」的概念（但不是形式語法*）。

從本質上講，如果您的迭代器類的接口符合一些要求，它將會工作。這套要求被稱爲「概念」。有幾種不同的迭代器概念（參見this page for a list of all of them），它們是分層的。創建一個兼容的C++迭代器的基礎是讓你的接口符合這個概念。對於一個簡單的迭代器，也僅限於前進方向，這將需要：

• 一種從提領你的迭代所得的值的typedef value_type。
• A typedef reference_type，它是相應值類型的參考類型。
• A typedef pointer，它是相應值類型的指針類型。
• typedef iterator_category，根據您的遍歷機制，它需要是input_iterator_tag，forward_iterator_tag，bidirectional_iterator_tag或random_access_iterator_tag之一。
• A typedef difference_type指示減去兩個不同迭代器的結果。
• A const value_type& operator*()const取消引用迭代器的函數。
• A value_type& operator*()函數，如果你的迭代器可以用來操縱值。
• 遞增（operator++()和operator++(int)功能）尋求前進。
• 的不同功能：difference_type operator-(const type_of_iterator&)

如果你選擇了更先進的迭代器類別之一，你可能還需要以指定遞減，並且加上運營商能夠尋求向後或尋求的任意距離。

* C++標準庫以非正式方式頻繁使用概念，C++標準委員會試圖引入一種用C++聲明它們的正式機制（目前它們只存在於標準庫的文檔中，而不存在於任何顯式代碼）。然而，對於該提案的持續不同意見導致其被C++ 0x取消，不過之後它很可能會重新考慮該標準。