用C++编写类似STL迭代器的自定义实现

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 {};
};

根据GoF的说法，实现支持不同遍历方式的迭代器的最佳方法是创建一个基本的Iterator类（List的友元），该类具有可以访问List成员的受保护方法。 Iterator的具体实现将以不同的方式处理工作，并通过基本接口访问List的私有和受保护数据。

从这里开始事情变得混乱了。比如，我有一个LinkedList和ArrayList类，它们都派生自List，并且还有相应的迭代器，每个类返回不同的值。那么我该如何实现LinkedListIterator呢？我完全没有思路。此外，基本迭代器类能够从List中检索哪些数据（List仅仅是一个接口，而所有派生类的实现都有很大的差异）？

- Maksim Skurydzin

---

Boost Iterator库是一个很好的信息来源，可用于开发新的迭代器类型/特性。http://www.boost.org/doc/libs/1_42_0/libs/iterator/doc/index.html - Hippicoder

这看起来像是Java/C#代码。通常好的C++代码不会像Java或C#那样。 - deft_code

如果List已经被模板化，为什么还要从中派生呢？如果您删除所有的virtual限定符并提供缺失的定义，那么您已经可以将其用于任何可想象的目的了。 - wilhelmtell

@weilhelmtell：并非所有可能的情况都是如此。例如在Java中，Stack是Vector的子类，同样您可能希望从列表中派生堆栈或队列。这不是一个好主意，但很容易想象。 - Steve Jessop

@Steve 在C++中，std::stack是一个适配器，模板化于某些后端容器，例如上述的List。 - wilhelmtell

我知道。这是否意味着在C++中实现堆栈没有其他方法可行？ - Steve Jessop

Answer 1

STL并没有真正使用抽象基类和虚函数。相反，它是有意设计成不是面向对象的（按照GoF的定义），完全建立在模板上，并旨在实现“编译时多态性”。模板不关心抽象接口。只要它们具有足够相似的接口（例如，如果你将Append称为push_back，那么更多期望符合STL容器的代码将对你起作用，比如std::back_insert_iterator）。

遵循STL标准的迭代器必须重载大量操作符以像指针一样行事（在容器的限制下尽可能），包括*、->、++、--（如果双向 - 双向链接）、==和!=。

- UncleBens

---

请注意，++和--是两个不同的运算符。如果迭代器类型需要一个++，则都需要，--同理。 - Steve Jessop

Answer 2

C++标准库在迭代器的实现中没有使用多态和继承，而是使用C++模板元编程和“概念”的概念（但不是正式语法*）。

基本上，如果您的迭代器类接口符合一些要求，则它将起作用。这组要求称为“概念”。有几种不同的迭代器概念（请参见此页面以获取所有列表），它们是分层的。创建兼容的C++迭代器的基础知识是使您的接口符合概念。对于仅向前移动的简单迭代器，这将需要：

- 一个typedef value_type，用于从迭代器引用的值。 - 一个typedef reference_type，它是相应值类型的引用类型。 - 一个typedef pointer，它是相应值类型的指针类型。 - 一个typedef iterator_category，它需要是input_iterator_tag、forward_iterator_tag、bidirectional_iterator_tag或random_access_iterator_tag之一，具体取决于您的遍历机制。 - 一个typedef difference_type，表示两个不同迭代器之间的差异。 - 用于解引用迭代器的const value_type & operator*()const函数。 - 如果您的迭代器可用于操作值，则还需要一个value_type & operator*()函数。 - 递增（operator++()和operator++(int)函数）以向前寻找。 - 差异函数：difference_type operator-(const type_of_iterator&)。

如果您选择更高级的迭代器类别，则还需要指定递减和加运算符，以便能够向后寻找或者寻找任意距离。

*C++标准库在非正式的方式中经常使用概念，以至于C++标准委员会试图在C++中引入一种声明它们的形式机制（目前它们仅存在于标准库的文档中，而不是任何明确的代码中）。然而，有关该提案的持久性分歧导致它被放弃用于C++0x，尽管它很可能会在此之后重新考虑用于标准。

- Michael Aaron Safyan

---

typedef不是迭代器类型的要求，但是iterator_traits模板的适当特化是。最好的方式是使用iterator模板和一个迭代器类型标签进行安排，而不是显式定义typedef。此外，前向迭代器不需要operator-（直到RandomAccess才需要），但是需要==和!=表达式。reference_type和pointer不是迭代器所必需的，但默认的iterator_traits模板要求它们。我不知道为什么会这样。 - Steve Jessop

@Steve，没错...我提供的文档确实写着那样，但我想保持简单；换句话说，我的指示是足够的，但不是必要的。 - Michael Aaron Safyan