C++迭代器和继承

Question

关于以下实现迭代器的最佳方法，我有一个快速问题：

假设我有一个模板基类'List'和两个子类"ListImpl1"和"ListImpl2"。基类的基本要求是可迭代的，也就是说我可以这样做：

for(List<T>::iterator it = list->begin(); it != list->end(); it++){
   ...
}

我也想允许迭代器加法操作，例如：

for(List<T>::iterator it = list->begin()+5; it != list->end(); it++){
   ...
}

问题在于ListImpl1的迭代器实现与ListImpl2的不同。我通过使用一个包含指向ListIteratorImpl的指针的包装器ListIterator来解决这个问题，其中有子类ListIteratorImpl2和ListIteratorImpl2，但是这一切变得非常混乱，特别是当你需要在ListIterator中实现operator+时。

有没有更好的设计来解决这些问题？

- user360366

---

为什么不使用std::advance？ - kennytm

谢谢，但是假设我需要提供比仅重复使用operator++更有效的operator+，那么我仍然有同样的问题吗？ - user360366

前向迭代器（std::advance() 的作用）和随机访问迭代器之间的区别在于前向迭代器没有高效的 operator+ 实现（想想链表）。这个问题暗示了一个迭代器是静态随机访问，但其具有动态行为以进行访问。 - Simon Buchan

没错 - 我想要随机访问的动态行为。我不明白为什么会有问题？ - user360366

Answer 1

如果您可以不将 List<T>::iterator 设为虚函数，那么将虚函数的实现委托给 List 就可以使事情变得简单：

template<typename T>
class List
{
    virtual void add_assign(iterator& left, int right) = 0;

public:
    class iterator
    {
        const List* list;
        const T* item;
    public:
        iterator(const List* list, const T* item) : list(list), item(item) {}

        iterator& operator +=(int right)
        {
            list->add_assign(*this, right);
            return *this;
        }
        static iterator operator +(iterator const& left, int right)
        {
            iterator result = left;
            result += right;
            return result;
        }
    };

    virtual iterator begin() const = 0;
    virtual iterator end() const = 0;
};

否则（如果迭代器需要存储显着不同的数据，例如），则必须执行常规、乏味的指向实现的指针操作才能使其具有虚拟性：

template<typename T>
class List
{
    class ItImpl
    {
        virtual ItImpl* clone() = 0;
        virtual void increment() = 0;
        virtual void add(int right) = 0;
    };
public:
    class iterator
    {
        ItImpl* impl;
    public:
        // Boring memory management stuff.
        iterator() : impl() {}
        iterator(ItImpl* impl) : impl(impl) {}
        iterator(iterator const& right) : impl(right.impl->clone()) {}
        ~iterator() { delete impl; }
        iterator& operator=(iterator const& right)
        {
            delete impl;
            impl = right.impl->clone();
            return *this;
        }

        // forward operators to virtual calls through impl.
        iterator& operator+=(int right)
        {
            impl->add(right);
            return *this;
        }
        iterator& operator++()
        {
            impl->increment();
            return *this;
        }
    };
};

template<typename T>
static List<T>::iterator operator+(List<T>::iterator const& left, int right)
{
    List<T>::iterator result = left;
    result += right;
    return result;
}

template<typename T>
class MagicList : public List<T>
{
    class MagicItImpl : public ItImpl
    {
        const MagicList* list;
        const magic* the_magic;
        // implement ...
    };
public:
    iterator begin() const { return iterator(new MagicItImpl(this, begin_magic)); }
    iterator end() const { return iterator(new MagicItImpl(this, end_magic)); }
};

- Simon Buchan

Answer 2

在迭代器中，有一些非常重要的东西，叫做迭代器类别：

• 输入迭代器
• 输出迭代器
• 前向迭代器
• 双向迭代器
• 随机访问迭代器

每个类别定义了一组确切的操作，这些操作可以被迭代器高效地支持。

在这里，似乎你希望放弃这种强大的识别机制，创建某种混合类别，在其中所有操作都存在，但不能保证它们的效率。

我认为你的设计有问题。

- Matthieu M.

---

我不太明白你的意思。它只是一个随机访问迭代器，保证常数时间。 - user360366

那么 operator+ 应该是接口的一部分（接受有符号整数作为其右手边参数）。你有什么问题吗？ - Matthieu M.

问题在于operator+返回一个迭代器，但是两个子类中的迭代器实现不同，因此您必须将此实现隐藏在“包装”迭代器内。我的问题是是否有更好的方法来解决这个问题。 - user360366

很容易实现：一个pimpl类“iterator”，包含指向从“iterator_interface”类派生的动态分配对象的指针（具有“clone”方法）。这意味着每个实现需要2个类+1个类。 - Matthieu M.

这是原帖中的解决方案。我只是想知道是否有人能提供更简洁的建议，但似乎大家都认为这是获得结果的可行方法。 - user360366

Answer 3

所以问题在于ListImpl1的迭代器实现与ListImpl2的不同。我通过使用包含指向ListIteratorImpl的指针的包装器ListIterator来解决这个问题，其中包含子类ListIteratorImpl2和ListIteratorImpl2，但是这一切变得非常混乱，特别是当您需要在ListIterator中实现operator+时。

在我看来，这种设计很好，我看不出有什么混乱之处。除了相等和减法之外，迭代器的操作可以通过虚函数轻松实现，因此您将拥有类似以下的东西：

class ListIteratorInterface // abstract
{
protected:
  virtual Data& operator*()=0;
  // and other operations
};
class ListIteratorA;
class ListIteratorB; // implementation of the above
class ListIterator
{
  ListIteratorInterface* impl_;
public:
  // when you create this, allocate impl_ on the heap
  // operations, forward anything to impl_
};

- jpalecek

---

这就是我目前所拥有的。更混乱的地方在于ListIterator类中operator+的实现。因为我需要返回一个新的ListIterator和ListIteratorA/B，所以我想我需要在ListIteratorInterface中创建一个虚拟的clone()方法来创建正确类型的新impl。 - user360366

Answer 4

你可以将operator+作为基类中的私有虚拟方法存储，并让迭代器调用它。

另外，你可以考虑使用静态多态列表类，而不是运行时多态。

- Puppy

Answer 5

假设我有一个模板基类'List'和两个子类"ListImpl1"和"ListImpl2"，在这里使用继承到底能获得什么好处呢？

- fredoverflow

---

@jom：多态有不同种类。STL容器基于“编译时多态/静态绑定/泛型/模板”，而不是你所想的那种多态。 - fredoverflow

我在谈论运行时多态，即使用List<T>作为具有多个实现ListImpl1<T>和ListImpl2<T>的接口，对客户端代码透明，尽管这里显然也存在静态多态性。 - user360366