2

假设我想在 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 的自定义迭代器的论文，但它没有帮助。我今天一定有点重... ;)

4

10 回答 10

8

尝试这个：

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 问题，要么将 vector 的 const_iterator 定义为您的迭代器，要么像 vector 一样定义双迭代器类型（const 和非 const 版本）。

于 2008-09-24T13:46:59.800 回答
3

Have a look at Adobe's any_iterator: this class uses a technique called type erase by which the underyling iterator type is hidden behind an abstract interface. Beware: the use of any_iterator incurs a runtime penalty due to virtual dispatching.

于 2008-09-24T16:51:07.220 回答
1

要隐藏您的迭代器基于您的事实，std::vector<Arc*>::iterator您需要一个委托给std::vector<Arc*>::iterator. std::iterator不这样做。

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

正如 Doug T. 在他的回答中提到的，boost 库有一些类可以更容易地编写迭代器。特别是，boost::indirect_iterator如果您希望迭代器Arc在取消引用时返回 an 而不是Arc*.

于 2008-09-24T14:06:56.243 回答
1

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

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

于 2008-09-24T13:41:51.247 回答
1

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

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

于 2009-08-05T03:49:03.837 回答
0

好吧，因为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;
};

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

于 2008-09-25T18:51:33.773 回答
0

我查看了头文件 VECTOR.

vector<Arc*>::const_iterator

是一个 typedef

allocator<Arc*>::const_pointer

那可能是你的 ArcIterator 吗？喜欢：

typedef allocator<Arc*>::const_pointer ArcIterator;
于 2008-09-24T13:55:29.563 回答
0

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()。当然，这意味着一次只有一个循环可以安全地迭代您的元素。

于 2008-09-24T14:44:12.860 回答
0

您可以模板化 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 本身（例如通过非常量方法）。

于 2008-09-24T14:18:00.880 回答
0

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

另一种方法是根据它应该在下面使用的容器类型对 Node 进行模板化。然后客户具体知道它使用的是什么类型的容器，因为他们告诉他们使用它。

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

于 2008-09-24T13:37:55.907 回答