在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取消，不过之后它很可能会重新考虑该标准。