1

我想问你如何为以下类编写一个复制构造函数（和 operator = ）。

类 Node 存储每个节点的坐标 x,y 和指向另一个节点的指针。

class Node
{
private:
double x, y;
Node *n;

public:
Node (double xx, double yy, Node *nn) : x(xx), y(yy), n(nn) {}
void setNode (Node *nn) : n(nn) {} 
...
};

类 NodesList（继承自 std::vector）存储所有动态分配的节点

class NodesList : public std::vector<Node *>
{}

主程序： 

int main()
{
Node *n1 = new Node(5,10,NULL);
Node *n2 = new Node(10,10,NULL);
Node *n3 = new Node(20,10,NULL);
n1->setNode(n2);
n2->setNode(n3);
n3->setNode(n2);
NodesList nl1;
nl1.push_back(n1);
nl1.push_back(n2);
nl1.push_back(n3);
//Copy contructor is used, how to write
NodesList nl2(nl1);
//OPerator = is used, how to write?
NodesList nl3 = nl1;

}

我不想创建每个节点的浅拷贝，而是创建每个节点的深拷贝。我可以问你一个带有复制构造函数的示例代码吗？

每个节点可以被多次指向。让我们有这样的情况，当 3 个节点 n[1]、n[2]、n[3] 存储在 NodesList nl1 中时：

n[1] 指向 n[2]

n[2] 指向 n[3]

n[3] 指向 n[2]

A] 我们的复制构造函数处理节点 n[1]。它创建一个由旧对象 n[1]_old 的副本表示的新对象 n[1]_new。从 n[1]_old 指向的节点 n[2] 仍然不存在，因此还必须创建 n[2]_new... 从 n1_new 指向 n2_new 的指针已设置。

B] 然后处理第二个点n[2]。它不能被创建两次，n[2]_new 是在 A] 中创建的。但是指向的节点 n[3] 不存在，因此创建了新对象 n[3]_new 作为旧对象 n[3]_old 的副本。从 n2_new 到 n3_new 的指针被设置。

C] 节点 n[3]_new 已经创建并且 n[2]_new。从 n3_new 到 n2_new 的指针已设置，不会创建其他对象...

所以复制构造函数应该检查对象是否在过去创建过或者没有...

一些引用计数可能会有所帮助......

4

5 回答 5

1

有我的问题的解决方案。添加了存储节点 n 的新版本的新数据成员 n_ref：

class Node
{
private:
double x, y;
Node *n, *n_ref;

public:
Node (double xx, double yy, Node *nn) : x(xx), y(yy), n(nn) {n_ref = NULL;}
Node * getNode() {return n;}
Node * getRefNode () {return n_ref;}
void setNode (Node *nn) {this->n = nn;} 
void setRefNode (Node *nn) {this->n_ref = nn;}

复制构造函数创建节点的浅拷贝：

Node (const Node *node) 
{
    x = node->x;
    y = node->y;
    n = node->n;
    n_ref = node->n_ref;
}

NodesList 的复制构造函数

    NodesList::NodesList(const NodesList& source)
    {
        const_iterator e = source.end();
        for (const_iterator i = source.begin(); i != e; ++i) {

            //Node* n = new Node(**i);

            //Node n still has not been added to the list
            if ((*i)->getRefNode() == NULL)
            {
                //Create node
                Node *node = new Node(*i);

                //Add node to the list
                push_back(node);

                //Set this note as processed
                (*i)->setRefNode(node);

                //Pointed node still has not been added to the list
                if ((*i)->getNode()->getRefNode() == NULL)
                {
                    //Create new pointed node
                    Node *node_pointed = new Node ((*i)->getNode());

                    //Add node to the list
                    push_back(node_pointed);

                    //Set pointer to n
                    node->setNode(node_pointed);

                    //Set node as processed
                    ((*i)->getNode())->setRefNode(node_pointed);
                }

                //Pointed node has already been added to the list
                else
                {
                    //Set pointer to node n
                    node->setNode((*i)->getRefNode());
                }
            }

            //Node n has already been added to the list
            else
            {
                //Get node
                Node * node = (*i)->getRefNode();

                //Pointed node still has not been added
                if ((*i)->getNode()->getRefNode() == NULL)
                {
                    //Create new node
                    Node *node_pointed = new Node ((*i)->getNode());

                    //Add node to the list
                    push_back(node_pointed);

                    //Set pointer to n
                    node->setNode(node_pointed);

                    //Set node as processed
                    ((*i)->getNode())->setRefNode(node_pointed);
                }

                //Pointed node has already been added to the list
                else
                {
                    //Set pointer to n
                    node->setNode((*i)->getNode()->getRefNode());
                }
            }
        }
    }
于 2010-03-07T09:27:25.507 回答
0

执行浅拷贝NodeList::NodeList(const NodeList&)，您不必担心循环中断拷贝操作。免责声明：以下内容未经测试，不完整，可能存在错误。

class NodeList {
private:
    typedef std::vector<Node*> Delegate;
    Delegate nodes;

public:
    NodeList(int capacity=16) : nodes() { nodes.reserve(capacity); }

    NodeList(const NodeList& from);
    virtual ~NodeList();

    NodeList& operator=(const NodeList& from);

    /* delegated stuff */
    typedef Delegate::size_type size_type;
    typedef Delegate::reference reference;
    typedef Delegate::const_reference const_reference;
    typedef Delegate::iterator iterator;
    typedef Delegate::const_iterator const_iterator;

    size_type size() const { return nodes.size(); }

    iterator begin() { return nodes.begin(); }
    const_iterator begin() const { return nodes.begin(); }
    iterator end() { return nodes.end(); }
    const_iterator end() const { return nodes.end(); }
    // ...
};

NodeList::NodeList(const NodeList& from)
    : nodes(from.size()), flags(NodeList::owner)
{
    std::map<Node*, Node*> replacement;
    Delegate::const_iterator pfrom;
    Delegate::iterator pto;
    // shallow copy nodes
    for (pfrom=from.begin(), pto=nodes.begin(); 
         pfrom != from.end(); 
         ++pfrom, ++pto) 
    {
        replacement[*pfrom] = *pto = new Node(**pfrom);
    }
    // then fix nodes' nodes
    for (pto = nodes.begin(); pto != nodes.end(); ++pto) {
        (*pto)->setNode(replacement[(*pto)->getNode()]);
    }
}

NodeList::operator=(const NodeList&)可以使用复制交换习语，与 Tronic 的Node::operator=(const Node&).

这种设计存在潜在的内存泄漏，因为副本NodeList（最初）是唯一引用其节点的地方。如果一个临时NodeList的超出范围，一个糟糕的实现将泄漏Node包含的列表。

一种解决方案是声明它NodeList是自己Node的。只要您不将 a 添加Node到多个NodeList（通过NodeList::push_back, NodeList::operator[]&c），NodeList的方法可以在必要时删除节点（例如 in NodeList::~NodeList, NodeList::pop_back）。

NodeList::~NodeList() {
    Delegate::iterator pnode;
    for (pnode = nodes.begin(); pnode != nodes.end(); ++pnode) {
        delete *pnode;
    }
}

void NodeList::pop_back() {
    delete nodes.back();
    nodes.pop_back();
}

另一种解决方案是使用智能指针，而不是Node*. NodeList应该存储共享指针。Node::n应该是防止所有权周期的弱指针。

于 2010-03-06T23:47:02.250 回答
0

显然每个节点只允许指向同一个列表中的另一个节点？否则，列表的“深拷贝”需要更多定义。不应该连接到原来的NodeList吗？它不应该连接到任何原始节点吗？不在列表中的节点副本是否被添加到其他列表或自由浮动？

如果所有节点到节点的指针都被限制在 NodeList 中，那么也许您应该存储索引而不是指针，那么不需要特殊处理。

于 2010-03-06T23:55:30.243 回答
0

您不应该从标准库容器继承（因为它们缺少虚拟析构函数）。相反，将它们作为成员变量包含在您的类中。

既然你想要一个深拷贝，你需要这些：（三规则）

Node(Node const& orig): x(orig.x), y(orig.y), n() {
    if (orig.n) n = new Node(*orig.n);
}
Node& operator=(Node const& orig) {
    // The copy-swap idiom
    Node tmp = orig;
    swap(tmp); // Implementing this member function left as an exercise
    return *this;
}
~Node() { delete n; }

一个更好的主意可能是完全避免使用指针，而只是将节点放在合适的容器中。

于 2010-03-06T11:37:48.917 回答
0

我只会使用 std::list<Node> 而不是 NodesList。好吧，让我们编码...

NodesList::NodesList(const NodesList& source)
{
    const_iterator e = source.end();
    for (const_iterator i = source.begin(); i != e; ++i) {
        Node* n = new Node(**i);
        push_back(n);
    }
}
于 2010-03-06T11:41:44.757 回答