用于枚举图中所有节点值的伪迭代器操作

Question

我正在尝试使用一个伪造的迭代器来枚举图中的所有节点值。该图可以按任何顺序抽象，只要该序列由图中所有且仅包含节点即可。应该有一个可变的限定符，4 个操作的实现很短，每个函数应该只有 1 行。

4个伪迭代器操作的测试用例如下，应该通过伪迭代器操作打印出一串图节点的值：

gdwg::Graph<std::string,int>> g
   for (g.begin(); !g.end(); g.next())
       std::cout << g.value() << std::end;

我将图表声明如下：

template <typename N, typename E> class Graph {

private:
    struct Node;
    struct Edge;

    struct Node {
        N val_;
        int numEdges_;
        int numIncomingEdges_;
        std::set<std::shared_ptr<Edge>> edges_;
        std::set<std::shared_ptr<Edge>> incomingEdges_;
        Node() {}
        Node(const N x) : val_{x} { numEdges_=0; numIncomingEdges_=0; }
        void printNode(N n);
        ~Node();
        void update();
    };

    struct Edge {
        std::weak_ptr<Node> orig;
        std::weak_ptr<Node> dest;
        E val_;
        Edge(std::shared_ptr<Node> o, std::shared_ptr<Node> d, E x);
        Edge() {};
        void printEdge();
        ~Edge();
    };

    // fake iterator operations
    void begin() const;
    bool end() const;
    void next() const;
    const N& value() const;



public:

    friend class Node_Iterator<N, E>;
    friend class Edge_Iterator<N, E>;


private:
    std::map< N, std::shared_ptr<Node> > nodes_;

    // fake iterator to be used for the four operations begin(), end(), next() and value()
    mutable typename std::map< N, std::shared_ptr<Node> >::iterator fakeIter_;

};

4个操作的实现如下：

// void begin() const: Sets an internal iterator, i.e., ``pointer'' to the first element of a sequence.
template <typename N, typename E>
void Graph<N,E>::begin() const {
    // gets iterator to the first key/value pair in map sequence
    fakeIter_ = nodes_.begin();
}

// bool end() const: Returns true if the iterator goes past the last element of the sequence and false otherwise.
template <typename N, typename E>
bool Graph<N,E>::end() const {
    // return true if iterator goes past last element, otherwise return false
    return ((fakeIter_ == nodes_.end()) ? true : false);
}

// void next() const: Moves the iterator to the next element of the sequence.
template <typename N, typename E>
void Graph<N,E>::next() const {
    fakeIter_ = std::next(fakeIter_, 1);
}

// const N& value() const: Returns the value of the node pointed to by the iterator.
template <typename N, typename E>
const N& Graph<N,E>::value() const {
    return fakeIter_->second->val_;
}

当我尝试编译时，弹出了一堆错误。我只是想知道我是否正确地实现了伪造的迭代器操作，如果需要，是否有任何方法可以改进它？

tests/Graph.tem: In instantiation of ‘void gdwg::Graph<N, E>::begin() const [with N = unsigned int; E = int]’:
tests/test13.cpp:23:15:   required from here
tests/Graph.tem:713:12: error: no match for ‘operator=’ (operand types are ‘std::map<unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node>, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > > >::iterator {aka std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >}’ and ‘std::map<unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node>, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > > >::const_iterator {aka std::_Rb_tree_const_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >}’)
  fakeIter_ = nodes_.begin();

In file included from /usr/local/include/c++/6.1.0/map:60:0,
                 from tests/Graph.h:19,
                 from tests/test13.cpp:3:
/usr/local/include/c++/6.1.0/bits/stl_tree.h:174:12: note: candidate: constexpr std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >& std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >::operator=(const std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >&)
     struct _Rb_tree_iterator
            ^~~~~~~~~~~~~~~~~
/usr/local/include/c++/6.1.0/bits/stl_tree.h:174:12: note:   no known conversion for argument 1 from ‘std::map<unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node>, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > > >::const_iterator {aka std::_Rb_tree_const_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >}’ to ‘const std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >&’
/usr/local/include/c++/6.1.0/bits/stl_tree.h:174:12: note: candidate: constexpr std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >& std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >::operator=(std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >&&)
/usr/local/include/c++/6.1.0/bits/stl_tree.h:174:12: note:   no known conversion for argument 1 from ‘std::map<unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node>, std::less<unsigned int>, std::allocator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > > >::const_iterator {aka std::_Rb_tree_const_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >}’ to ‘std::_Rb_tree_iterator<std::pair<const unsigned int, std::shared_ptr<gdwg::Graph<unsigned int, int>::Node> > >&&’

Answer 1

第一个错误的意思是，由于您的 begin 函数是 const，nodes_.begin() 将 return 变成 const_iterator。这不能分配给 iterator，类型 fakeIter_。

您需要从 begin 中删除 const，更改 fakeIter_ 的类型，或更改您的实现（begin 应该 return一个迭代器，不是 void)。

用于枚举图中所有节点值的伪迭代器操作

fake iterator operations for enumerating all the node values in a graph

c++

iterator

directed-graph

stdmap

mutable