C++ std::set<Vertex> 带有自定义顶点的迭代器 class

Question

我对为自定义 classes 实现迭代器感到困惑。我正在尝试为 std::set 实现一个迭代器，其中我的顶点 class 声明为：

class Vertex{                                                   
public:
    int i, j; 
    std::set<Vertex*> adj; //references to adjacent vertices

    Vertex();
    ~Vertex();
    //end constructors

    /** must overload for set<Vertex> to function */
    const bool operator < (const Vertex &o) const;

};//END class Vertex

但是如果我定义

iterator<Vertex*> begin(){
    return iterator<Vertex*>( *this, 0 ); 
}
iterator>Vertex*> end(){ 
    return iterator<Vertex*>( *this, sizeof(Vertex) ); 
}

这样我就可以像这样迭代：

set<Vertex*>::iterator it;
    //for all vertices adjacent of cur
    for(it = cur.begin(); it != cur.end(); it++){
        //...
    }

并收到这些错误：

In file included from Vertex.cc:8:0:
Vertex.h:50:22: error: wrong number of template arguments (1, should be 5)
 std::iterator<Vertex*> begin();
                      ^
In file included from c:\mingw\lib\gcc\mingw32.8.1\include\c++\bits\stl_algoba
se.h:65:0,
                 from c:\mingw\lib\gcc\mingw32.8.1\include\c++\bits\stl_tree.h
:61,
                 from c:\mingw\lib\gcc\mingw32.8.1\include\c++\set:60,
                 from Vertex.h:10,
                 from Vertex.cc:8:
c:\mingw\lib\gcc\mingw32.8.1\include\c++\bits\stl_iterator_base_types.h:118:12
: error: provided for 'template<class _Category, class _Tp, class _Distance, cla
ss _Pointer, class _Reference> struct std::iterator'
     struct iterator
            ^
In file included from Vertex.cc:8:0:
Vertex.h:50:31: error: invalid type in declaration before ';' token
 std::iterator<Vertex*> begin();
                               ^
Vertex.h:51:22: error: wrong number of template arguments (1, should be 5)
 std::iterator<Vertex*> end();

<additional errors>

ss _Pointer, class _Reference> struct std::iterator'
     struct iterator
            ^
Vertex.cc:114:29: error: invalid use of 'this' in non-member function
  return iterator<Vertex*>( *this, 0 );
                             ^
Vertex.cc: At global scope:
Vertex.cc:116:1: error: invalid use of template-name 'std::iterator' without an
argument list
 iterator>Vertex*> end(){
 ^
Vertex.cc: In function 'int begin()':
Vertex.cc:115:1: warning: control reaches end of non-void function [-Wreturn-typ
e]
 }
 ^
make: *** [Vertex.o] Error 1

我需要帮助弄清楚如何去做这件事；我也发现大多数 tutorials/links 令人困惑。注意：我没有使用 C++11

Answer 1

我相信您正在寻找的迭代器类型是 std::set<Vertex*>::iterator 并且要获得 set 的 begin 和 end 您只需执行 cur.adj.begin() 和 cur.adj.end().

示例：

void func(Vertex* cur)
{
  if(cur == NULL)
    return;

  for(std::set<Vertex*>::iterator it = cur->adj.begin(); it != cur->adj.end(); ++it)
  {
    //Do something
  }
}

但是，如果您坚持将代码实现为 cur.begin() 和 cur.end()，一种方法是为您的 [=28] 实现 begin 和 end 函数=] 像这样。

std::set<Vertex*>::iterator begin()
{
  return adj.begin();
}
std::set<Vertex*>::iterator end()
{
  return adj.end();
}

Answer 2

这里涉及两个步骤：

您需要在 Vertex class 中提供一个名为 iterator 的类型。
然后您需要定义 begin 和 end 以正确使用该迭代器类型。

由于您希望在此处迭代基础 set，因此让我们将 Vertex class 导出的迭代器类型设为 set 提供的迭代器类型。你可以写

class Vertex{                                                   
public:
    int i, j; 
    std::set<Vertex*> adj; //references to adjacent vertices

    Vertex();
    ~Vertex();
    //end constructors

    /** must overload for set<Vertex> to function */
    const bool operator < (const Vertex &o) const;

    typedef std::set<Vertex*>::iterator iterator;
    iterator begin();
    iterator end();

};//END class Vertex

现在，我们可以定义begin和end如下：

Vertex::iterator Vertex::begin() {
    return adj.begin();
}
Vertex::iterator Vertex::end() {
    return adj.end();
}

现在可以让您编写类似

的内容

Vertex v = /* ... */;
for (Vertex::iterator itr = v.begin(); itr != v.end(); ++itr) {
    /* ... */
}

或

Vertex v = /* ... */
for (auto& adj: v) {
   /* ... */
}

尽管如此，您可以在很大程度上清理此代码。对于初学者，您可能不应该制作 i、j 和 adj public；这违反了封装原则。将这些数据成员设为私有并提供成员函数来访问这些值。

这里的另一个细节是您实际上不需要在这里定义 operator<。如果要将给定类型的对象直接存储在 set 中或作为键存储在 map 中，则需要定义 operator<，但此处存储的是指针指向set和map中的Vertexes。因此，除非您真的想稍后使用 operator<，否则我不会担心定义 operator<。你可以删除它。

希望对您有所帮助！

C++ std::set<Vertex> 带有自定义顶点的迭代器 class

C++ std::set<Vertex> iterator with custom Vertex class

c++

iterator