返回“任何类型的输入迭代器” 而不是向量::迭代器或列表::迭代器

Question

假设我想用 C++ 实现一个数据结构来存储定向图。 由于 STL 容器，弧将存储在节点中。 我希望用户能够以类似 STL 的方式迭代节点的弧。

我遇到的问题是，我不想在 Node 类（实际上是一个抽象基类）中公开我将在具体类中实际使用的 STL 容器。 因此，我不想让我的方法返回 std::list::iterator 或 std::vector::iterator...

我尝试了这个：

class Arc;

typedef std::iterator<std::random_access_iterator_tag, Arc*> ArcIterator;  // Wrong!

class Node {
public:
  ArcIterator incomingArcsBegin() const {
    return _incomingArcs.begin();
  }
private:
  std::vector<Arc*> _incomingArcs;
};

但这是不正确的，因为不能使用 vector::const_iterator创建一个 ArcIterator。 那么这个 ArcIterator 会是什么？

我找到了这篇关于 STL 的自定义迭代器 的论文，但它没有帮助。 我今天一定有点重...;)

Answer 1

因为 std::vector 保证有连续的存储，所以这样做应该是完美的：

class Arc;
typedef Arc* ArcIterator;

class Node {
public:
    ArcIterator incomingArcsBegin() const {
        return &_incomingArcs[0]
    }

    ArcIterator incomingArcsEnd() const {
        return &_incomingArcs[_incomingArcs.size()]
    }
private:
    std::vector<Arc*> _incomingArcs;
};

基本上，指针的功能足够像随机访问迭代器，它们是一个足够的替代品。

Answer 2

我认为应该有一种方法可以通过直接的 STL 来做到这一点，类似于您想要做的事情。

如果没有，您可能需要考虑使用 boost 的迭代器外观和适配器，您可以在其中定义自己的迭代器或将其他对象适配到迭代器中。

Answer 3

要隐藏迭代器基于 std::vector::iterator 的事实，您需要一个委托给 std::vector的迭代器类： :迭代器。 std::iterator 不会执行此操作。

如果您查看编译器的 C++ 标准库中的头文件，您可能会发现 std::iterator 本身并不是很有用，除非您需要的只是一个为 std::iterator 定义 typedef 的类。 code>iterator_category、value_type 等。

正如 Doug T. 在他的回答中提到的，boost 库有一些类可以更轻松地编写迭代器。 特别是 boost::indirect_iteratorArc 而不是 Arc*，code> 可能会有所帮助。

Answer 4

考虑使用 访客模式 并反转关系：而不是向图形结构询问容器数据，您给图一个函子，并让图将该函子应用于其数据。

访问者模式是图形上常用的模式，请查看 boost 的有关访问者概念的图形库文档。

Answer 5

如果您确实不希望该类的客户端知道它在下面使用向量，但仍然希望他们能够以某种方式迭代它，那么您很可能需要创建一个将其所有方法转发到 std 的类::向量::迭代器。

另一种方法是根据 Node 应该使用的容器类型来模板化 Node。 然后客户明确知道它正在使用什么类型的容器，因为他们告诉他们使用它。

就我个人而言，我认为将向量封装远离用户通常是没有意义的，但仍然提供其大部分（甚至部分）接口。 它的封装层太薄，无法真正提供任何好处。

Answer 6

我查看了头文件 VECTOR.h

vector<Arc*>::const_iterator

是一个typedef，

allocator<Arc*>::const_pointer

它是你的ArcIterator吗？ 喜欢：

typedef allocator<Arc*>::const_pointer ArcIterator;

Answer 7

您可以模板化 Node 类，并在其中 typedef iterator 和 const_iterator。

例如：

class Arc {};

template<
  template<class T, class U> class Container = std::vector,
  class Allocator = std::allocator<Arc*>
>
class Node
{
  public:
    typedef typename Container<Arc*, Allocator>::iterator ArcIterator;
    typedef typename Container<Arc*, Allocator>::Const_iterator constArcIterator;

    constArcIterator incomingArcsBegin() const {
      return _incomingArcs.begin();
    }

    ArcIterator incomingArcsBegin() {
      return _incomingArcs.begin();
    }
  private:
    Container<Arc*, Allocator> _incomingArcs;
};

我还没有尝试过这段代码，但它给了你这个想法。 但是，您必须注意，使用 ConstArcIterator 只会禁止修改 Arc 的指针，而不允许修改 Arc 本身（例如通过非常量方法）。

Answer 8

C++0x 将允许您通过自动类型确定来完成此操作。

在新标准中，这个
for (vector::const_iterator itr = myvec.begin(); itr != myvec.end(); ++itr
可以用这个代替
for (auto itr = myvec.begin(); itr != myvec.end(); ++itr)

同样，您将能够返回任何合适的迭代器，并将其存储起来在 auto 变量中。

在新标准生效之前，您必须模板化您的类，或者提供一个抽象接口来访问列表/向量的元素。 例如，您可以通过在成员变量中存储迭代器并提供成员函数（例如 begin() 和 next()）来实现这一点。 当然，这意味着一次只有一个循环可以安全地迭代您的元素。

Answer 9

试试这个：

class Arc;
class Node {
private:
  std::vector<Arc*> incoming_;
public:
  typedef std::vector<Arc*>::iterator iterator;
  iterator incoming_arcs_begin()
  { return incoming_.begin(); }
};

并在代码的其余部分使用 Node::iterator。 当/如果您更改容器时，您必须在一个位置更改 typedef。 （您可以进一步使用额外的 typedef 进行存储，在本例中为向量。）

至于 const 问题，要么将向量的 const_iterator 定义为迭代器，要么将双迭代器类型（const 和非 const 版本）定义为矢量确实如此。

Answer 10

看看 Adob​​e 的 any_iterator：这个类使用了一种称为类型擦除，通过它，底层迭代器类型被隐藏在抽象接口后面。 请注意：使用 any_iterator 会因虚拟调度而导致运行时损失。