2

我有一个关于在 C++ 中删除动态指针数组的问题。假设我们有以下情况：

int n;
scanf("%d", &n);
Node **array1 = new Node*[n];
/* ... */

其中 Node 是预先定义的某个结构。假设在使用 new 运算符分配之后，我们更改了 array1 的内容（但我们没有删除任何内容！）。如果数组中可能存在重复指针（在线性时间内不对它们进行排序或插入集合），那么删除 array1 及其所有内容的正确方法是什么？

4

5 回答 5

3

使用此分配：

Node **array1 = new Node*[n];

array1 的内容是未定义的。每个元素都是 a Node*，并且由于内存未初始化，因此值可以是任何值。

分配指针数组不会构造指向类的对象。

因此，无论您将指针放入数组中，它们指向的对象都需要在其他地方构造和销毁。

所以要回答你的问题，删除 array1 的正确方法是

delete[] array1;

但是，请注意，这不会导致为每个调用析构函数- 您应该在删除数组之前Node*处理您放入数组的任何内容。

编辑：我对原始问题感到困惑，其中提到了数组中的“更改值”，就好像在您的示例中分配的数组中有一个有效值一样。

但是...既然我知道您希望稍后跟踪要删除的指针，也许您可​​以为此目的创建另一个数组，其中每个指针仅存在一次。因此，您拥有上面当前拥有的数组，其中包含指向可能重复的节点的指针，无论您出于何种目的使用它。然后你有另一个数组用于管理删除的明确目的，其中每个指针只出现一次。nodeCleanupArray[i] = pNewNode设置类似right after应该很容易，然后您可以在线性时间和每个元素pNewNode = new Node()中爆炸该数组。delete（这意味着您不必费心检查 array1 中的元素，您将依赖 nodeCleanupArray 进行清理）

于 2013-03-14T20:13:52.550 回答
1

这类问题有很多解决方案，但最明显的选择是将其更改为使用

std::vector< std::shared_ptr<Node> >

现在您将拥有一个引用计数指针，而无需编写任何代码，以及一个不需要知道它的预定义大小的“数组”。

您当然可以在 中实现引用计数的对象Node，或者您自己的容器对象来做同样的事情，但这似乎是额外的麻烦，几乎没有好处。

于 2013-03-14T20:19:50.293 回答
0

我这样做的方法是有一个引用计数器并有一个 Node::deref 方法，当引用计数为 0 时会删除节点本身。当遍历节点列表时，调用 node->deref 实际上不会删除对象，直到数组中的最后一个节点引用。

于 2013-03-14T20:15:40.930 回答
0

尝试标记和扫描 :) 您正在尝试实施托管环境。

这是一个例子：

struct Node
{
... 
    bool marked;

    Node() : marked(false)
    {}
};

现在删除：

void do_delete(Node **data, size_t n)
{
    size_t uniq = 0;
    Node **temp = new Node*[n];

    for (size_t i = 0; i < n; i++)
    {
        if (data[i] && !data[i]->marked)
        {
            data[i]->marked = true;
            temp[uniq++] = data[i];
        }
    }

    for (i = 0; i < uniq; ++i)
    {
        delete temp[i];
    } 

    delete[] temp;
    delete[] data;
}
于 2013-03-14T20:12:21.523 回答
0

What is the proper way to delete the array1 and all its content

You show a single allocation; new Node*[n]. This allocation confers on the program the responsibility to call delete [] whatever_the_return_value_was. This is only about deleting that one allocation and not about deleting 'all its content'. If your program performs other allocations then the program needs to arrange for those responsibilities to be handled as well.

if there is a possibility of repeated pointers in the array

Well it would be undefined behavior to delete a pointer value that is not associated with any current allocation, so you have to avoid deleting the same pointer value more than once. This is not an issue of there being a single correct way, but an issue of programming practices, design, etc.

Typically C++ uses RAII to handle this stuff automatically instead of trying to do what you want by hand, because doing it by hand is really hard to get right. One way to use RAII here would be to have a second object that 'owns' the Nodes. Your array1 would then simply use raw pointers as 'non-owning' pointers. Deleting all the Nodes then would be done by letting the Node owning object go out of scope or otherwise be destroyed.

{
  // object that handles the ownership of Node objects.
  std::vector<std::unique_ptr<Node>> node_owner;

  // your array1 object that may hold repeated pointer values.
  std::vector<Node*> array1;

  node_owner.emplace_back(new Node); // create new nodes

  array1.push_back(node_owner.back().get()); // put nodes in the array
  array1.push_back(node_owner.back().get()); // with possible duplicates

  // array1 gets destroyed, but it's contents do not, so the repeated pointers don't matter
  // node_owner gets destroyed and destroys all its Nodes. There are no duplicates to cause problems.
}

And the destruction does occur in linear time.

于 2013-03-14T20:31:20.543 回答