基础集合的抽象迭代器

Question

基本上我想做的就是有一个纯虚方法，返回一个任意具体类型集合的迭代器，例如伪代码如下：

virtual Iterator<T> getIterator() const = 0;

这个类的用户实际上并不关心子类使用了哪种实现，可以是set、vector、list、array等等。

我知道std::iterator类，但我找不到一种正确的方法来指定它，以便与简单的vector一起使用。

virtual std::iterator<std::random_access_iterator_tag,T> getIterator() const = 0;

myVector.begin() // compilation error in implementation

定义带有 const T 作为类型参数的 std::iterator 并没有起作用。我也尝试过保留 T，而是将指针和引用类型定义为 const T* 和 const T&。

通过查看 std::vector 的实现，我发现 std::vector::const_iterator 实际上派生自 _Iterator012，后者又派生自 _Iterator_base。

让我很困扰的是，在 std 中没有任何方法可以使用任意集合。像在 <algorithm> 中那样将我的类实现为模板对我来说不是一个选项，原因有两个：

• 无法控制实际值类型
• 我只是不想让我的类变成模板，这会使我的设计更加复杂，使事情变得不太灵活。

所使用的类型参数 T 只是为了演示，实际上这是一个具体类型。

- Sebastian Hoffmann

---

这篇文章可能会很有用：http://www.artima.com/cppsource/type_erasure.html - juanchopanza

这正是模板的用途，标准库使用它们。它们只会让你的代码更加灵活！ - Joseph Mansfield

所以你想要模板，但不想使用模板，而且除了模板这个强大的特性外，C++并不支持模板，这可能会让你感到困扰。是的，你可能有点道理。 - Lightness Races in Orbit

@LightnessRacesinOrbit请离开这个问题。我只是不想和一个毫无理由如此讽刺的人争论。首先，我不明白解释我的整个架构来证明模板对我来说不是选项的意义所在。在我的具体情况下，我不想使用它们，请接受这一点。有没有人可以提出具体的解决方案，而不是讨论范式？ - Sebastian Hoffmann

如果您不介意动态分配，您可以为您的值类型创建一个简单的类型擦除迭代器。 - Kerrek SB

Answer 1

这是一种基本的、非常简单的类型抹消方法，涉及到IT技术。虽然你需要填补很多缺失的细节！

#include <memory>

template <typename T>
class TEIterator
{
    struct TEImplBase
    {
        virtual ~TEImplBase() { }
        virtual std::unique_ptr<TEImplBase> clone() const = 0;
        virtual void increment() = 0;
        virtual T & getValue() = 0;
        T * getPointer() { return std::addressof(getValue()); }
    };

    template <typename Iter>
    struct TEImpl
    {
        Iter iter;

        TEImpl(Iter i) : iter(i) { }

        virtual T & getValue()
        { return *iter; }

        virtual std::unique_ptr<TEImplBase> clone() const
        { return std::unique_ptr<TEImplBase>(new TEImpl<Iter>(*this)); }

        virtual void increment()
        { ++iter; }
    };

    std::unique_ptr<TEImplBase> impl;

public:

    template <typename T>
    TEClass(T && x)
    : impl(new TEImpl<typename std::decay<T>::type>(std::forward<T>(x)))
    {
    }

    TEClass(TEClass && rhs) = default;

    TEClass(TEClass const & rhs) : impl(rhs.impl.clone()) { }

    TEIterator & operator++()
    {
        impl->increment();
        return *this;
    }

    T & operator*() { return impl->getValue(); }
    T * operator->() { return impl->getPointer(); }
};

使用方法：

std::vector<int> v;
std::deque<int> dq;

TEIterator<int> a = v.begin(), b = dq.end();

- Kerrek SB

---

作为一种注释：有些人更慷慨地倡导类型擦除，因为它为多态概念提供了严格的值语义。正如您所看到的，您需要编写样板代码来从有效载荷类中提取相关行为。我认为有一个建议的Boost库可以系统地制作这些包装器类。 - Kerrek SB

我建议使用boost迭代器助手。将一个类型擦除的pImpl插入其中，并实现所需的方法。 - Yakk - Adam Nevraumont

Answer 2

如果您想使用虚方法，就不能使用任意返回值。您可以定义一个基类，它是迭代器的包装器，并从该包装器类派生子类。

但即使如此，您也必须限制自己使用最小公共分母，因为C++标准库中有几个迭代器类。

因此，我认为，如果不使用模板，使用任意迭代器的这种方法并不真正可行。

- Olaf Dietsche

---

一个简单的多态类并不是很好，因为迭代器需要能够通过值传递。 - Kerrek SB

@KerrekSB 是的，但是...如果您有一个带有虚方法的基类，并且这就是OP所拥有的，那么没有办法返回任意类型。没有if或when或类型擦除。 - Olaf Dietsche