具有自定义 Vertex 类的 C++ std::set 迭代器

Question

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

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\4.8.1\include\c++\bits\stl_algoba
se.h:65:0,
                 from c:\mingw\lib\gcc\mingw32\4.8.1\include\c++\bits\stl_tree.h
:61,
                 from c:\mingw\lib\gcc\mingw32\4.8.1\include\c++\set:60,
                 from Vertex.h:10,
                 from Vertex.cc:8:
c:\mingw\lib\gcc\mingw32\4.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

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

Answer 1

这里涉及两个步骤:

1. 您需要提供一个名为 iterator 的类型在你的里面Vertex类。
2. 然后你需要定义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民众;这违反了封装原则。将这些数据成员设为私有(private)并提供成员函数来访问这些值。

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

希望这对您有所帮助!