新图的深拷贝构造函数

Question

我正在尝试访问我的节点结构中的 edges_，因此我可以执行 for 循环将边复制到我的复制构造函数的新图形对象中。

当我尝试访问节点中的 edges_ 时，出现以下错误让我感到困惑。

tests/Graph.tem:280:24: error: ‘struct std::pair<const std::__cxx11::basic_string<char>, std::shared_ptr<gdwg::Graph<std::__cxx11::basic_string<char>, int>::Node> >’ has no member named ‘edges_’
   for (auto edge: node.edges_) {
                   ~~~~~^~~~~~

我正在尝试创建一个复制构造函数，将图形中的节点和边深度复制到新的图形对象中：

template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g):
    nodes_{g.nodes_}
    {

        for (auto node: g.nodes_) {

            for (auto edge: node.edges_) {

            }

        }


    }

以下是我的图表class:

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();
        };

首先，如何访问它来进行深拷贝？似乎有一些 ptr 问题。其次，有没有一种简单的方法可以将存储在节点内的边深度复制过来？

Answer 1

对于编译器消息，您应该将 for (auto edge: node.edges_) 替换为 for (auto edge: node.second->edges_)

要执行深拷贝，您需要 g 的源节点和您的副本的节点之间的关联映射。

这是我为您的深层复制构造函数编写的代码的想法（我没有尝试编译它）。

template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g):
    nodes_{g.nodes_}
    {   std::map<Node*, Node*> associativeMap;
        typename std::map<N, std::shared_ptr<Node>>::const_iterator
            thisIter(nodes_.begin()), sourceIter(g.nodes_.begin()),
            thisIterEnd(nodes_.end()), sourceIterEnd(g.nodes_.end());
        for (; thisIter != thisIterEnd; ++thisIter) {
            associativeMap.insert(std::make_pair(&*(sourceIter->second), &*(thisIter->second));
            ++sourceIter;
        }

        thisIter = nodes_.begin();
        for (auto sourceNode: g.nodes_) {
            Node* thisNode = &*thisIter->second;
            for (auto sourceEdge: sourceNode.second->edges_)
               addEdge(*thisNode, *associativeMap[&*sourceEdge->dest], ...);
            ++thisIter;
        }
    }

它基于带有签名 void addEdge(Node& origin, Node& destination, ...) 的 addEge 方法。

如果您的 Graph::nodes_ 很快被排序并且 addEdge 可以从键中检索节点 - 如果其签名是 bool addEdge(const N& orig, const N& dest, const E& val) -，则 associativeMap 不是更有用。这样的话，代码就简单多了。

template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g): nodes_{g.nodes_}
{  for (auto sourceNode: g.nodes_) {
      for (auto sourceEdge: sourceNode.second->edges_)
         addEdge(sourceNode.second->val_, sourceEdge->dest.lock()->val_, sourceEdge->val_);
   }
}

新图的深拷贝构造函数

Deep-copy constructor for a new graph

c++

directed-graph

deep-copy

copy-constructor

shared-ptr