在C++中编写我自己的类似stl的Iterator实现

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,实现可以支持不同类型遍历的迭代器的最佳方法是使用可以访问List成员的受保护方法创建基类Iterator类(List的朋友).Iterator的具体实现将以不同的方式处理作业,并通过基接口访问List的私有和受保护数据.

从这里开始,事情变得令人困惑.说,我有类LinkedList和ArrayList,都是从List派生的,并且还有相应的迭代器,每个类都返回.我该如何实现LinkedListIterator？我完全没有想法.基础迭代器类可以从List中检索哪种数据(这只是一个接口,而所有派生类的实现差异很大)？

Answer 1

STL并没有真正使用抽象基类和虚函数.相反,它被明智地设计为不是OO(在GoF意义上)并且完全基于模板构建,旨在"编译时多态性".模板不关心抽象接口.只要它们具有足够相似的接口(例如,如果您要调用Append push_back,那么期望符合STL的容器的更多代码将适用于您,例如std::back_insert_iterator),事情就会起作用.

一个STL兼容的迭代器将不得不超负荷很多运营商的表现就像一个指针(尽可能,考虑到容器的限制),包括*,->,++,--(如果双向-双链接),==和!=.

Answer 2

C++标准库在迭代器的实现中不使用多态和继承; 相反,它使用C++模板元编程和"概念"的概念(但不是形式语法*).

从本质上讲,如果迭代器类的接口遵循一些要求,它将起作用.这组要求称为"概念".有几种不同的迭代器概念(请参阅此页面以获取所有这些概念的列表),它们是分层的.创建兼容的C++迭代器的基础是使您的接口符合该概念.对于仅向前方向的简单迭代器,这将需要:

• value_type取消引用迭代器的值的typedef .
• 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,尽管之后可能会重新考虑该标准.