代码之家 › 专栏 › 技术社区 › Maksim Skurydzin

用C++编写我自己的STL类似Iterator的实现

iterator design-patterns c++

12

Maksim Skurydzin · 技术社区 · 16 年前

我目前正在尝试理解各种语言中迭代器的内部原理,即它们的实现方式。

例如,下面的类公开了列表接口。

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

从这里开始,事情变得越来越混乱。比如,我有类linkedlist和arraylist,它们都是从列表派生的,并且还有相应的迭代器,每个类都返回。如何实现LinkedListinator?我完全没有主意。基本迭代器类可以从列表中检索到什么类型的数据(这只是一个接口,而所有派生类的实现都有很大的不同)?

2 回复 | 直到 9 年前

1

14

UncleBens 16 年前

STL并没有真正使用抽象基类和虚拟函数。相反,它被有意设计成不使用OO(在gof的意义上)并且完全基于模板,目的是“编译时多态性”。模板不关心抽象接口。只要它们具有足够相似的接口(例如,如果要调用 Append push_back 相反,更多期望符合STL的容器的代码可以为您工作,例如 std::back_insert_iterator )

符合STL的迭代器必须重载许多运算符才能像指针一样工作(考虑到容器的限制,尽可能地),包括 * , -> , ++ , -- (如果双向-双链接) == 和 != .

2

7

Michael Aaron Safyan 13 年前

C++标准库在迭代器的实现中不使用多态性和继承性,而是使用C++模板元编程和“概念”的概念(但不是形式语法)。

从本质上讲,如果迭代器类的接口符合一些需求集,它将工作。这组需求称为“概念”。有几个不同的迭代器概念(请参见 this page for a list of all of them )并且它们是分层的。创建兼容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,尽管它很有可能在之后被重新考虑。