为抽象类编写迭代器

Question

我制作了一个抽象类List，然后用类DLL（双向链表）来固有它。为了使其能够很好地访问顺序数据，我使用了迭代器。但我却深陷其中。我可以为 DLL 类创建迭代器，但我想虚拟地创建它。我的意思是迭代器可以与列表的任何派生类一起使用。下面是我的代码。你们能否给我一些想法，如何对类迭代器进行编码以实现我的目的。如果有一些示例代码，我将非常感激。

template<typename T>
class List {
public:
    class Iterator;
    virtual ~List() = default;
    virtual void push_back(T value) = 0;
    virtual void push_front(T value) = 0;
    virtual Iterator begin() = 0;
    virtual Iterator end() = 0;
};
template <typename T>
class DLL : public List<T> {
public:
    class Node;
private:
    Node <T> * head;
    Node <T> * tail;
    int size;
public:
    DLL();
    ~DLL();
    void push_front(T value);
    void push_back(T value);
    Iterator begin();
    Iterator end();
};

我希望迭代器可以像这样工作：

int main (){
    List<List<int>*> *ptr = new DLL<List<int>*>;
    List<int>* ptr1 = new DLL<int>;
    for (int i; i < 10; i++)
    ptr1->push_back(i);
    ptr->push_back(ptr1);
    List<List<int>*>::Iterator it = ptr->begin();
    List<int>::Iterator it1 = ptr1->begin();
}

也可以像这样工作吗（？）：

    DLL<DLL<int>*>* data = new DLL<DLL<int>*>;
    DLL<DLL<int>*>::Iterator it2 = data->begin();

注意：如果我写的内容不清楚或不准确，请告诉我。非常感谢你们！！

我希望我能让 Iterator 很好地适用于 List 的任何派生类。

Answer 1

因为您按值返回

List::Iterator

，所以您必须采取一些技巧来隐藏其中的多态性。

template <typename T>
class List<T>::Iterator {
public:
    class BaseImpl {
        virtual ~BaseImpl() {}
        virtual void advance(std::ptrdiff_t) = 0;
        virtual T& dereference() const = 0;
        virtual bool equal(BaseImpl&) const = 0;
        virtual std::unique_ptr<BaseImpl> clone() const = 0;
    }
private:
    std::unique_ptr<BaseImpl> impl;
public:
    Iterator(std::unique_ptr<BaseImpl> impl) : impl(std::move(impl)) {}
    Iterator(const Iterator & other) : impl(other.impl->clone()) {}
    Iterator& operator++() { impl->advance(1); return *this; }
    Iterator& operator--() { impl->advance(-1); return *this; }
    friend bool operator==(const Iterator & lhs, const Iterator & rhs) { return lhs.impl->equal(*rhs.impl); }
    friend bool operator!=(const Iterator & lhs, const Iterator & rhs) { return !(lhs == rhs); }
    T& operator*() { return impl->dereference(); }
};

您尚未展示

DLL

的工作原理，因此您需要填写

DLL_IteratorImpl

的成员

template <typename T>
class DLL_IteratorImpl : public List<T>::Iterator::BaseImpl {
    DLL<T>::Node * node;
    friend class DLL<T>;
    DLL_IteratorImpl(DLL<T>::Node * node) : node(node) {}
public:
    void advance(std::ptrdiff_t) override;
    T& dereference() const override;
    bool equal(BaseImpl& other) const override {
        if (DLL_IteratorImpl * d_other = dynamic_cast<DLL_IteratorImpl *>(&other)) {
            return node == other->node;
        }
        return false;
    }
    std::unique_ptr<BaseImpl> clone() const override {
        return new DLL_IteratorImpl(node);
    }
};

template <typename T>
List<T>::Iterator DLL<T>::begin() { return { new DLL_IteratorImpl(head) }; }
List<T>::Iterator DLL<T>::end() { return { new DLL_IteratorImpl(tail) }; }

这都是高度不惯用的C++，是由

List

的定义所强加的要求造成的。

注意：如果您可以使用 C++14 或更高版本，请使用

std::make_unique

而不是

new