Deleting a dynamic array of pointers in C++

Question

I have a question concerning deleting a dynamic array of pointers in C++. Let's imagine that we have a following situation:

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

where Node is a certain structure defined beforehand. Suppose that after allocation with the new operator, we change the content of the array1 (but we do not delete anything!). What is the proper way to delete the array1 and all its content if there is a possibility of repeated pointers in the array (without sorting them or inserting into the set, in linear time)?

Are the pointers in the array themselves allocated on the heap? If they are, you could add a reference count to Node or perhaps have another array that only contains unique pointers to allocated Nodes. — Pete
– Pete, Commented Mar 14, 2013 at 20:06
why is this tagged c++? if you're using c++ just use vectors for this. — none
– none, Commented Mar 14, 2013 at 20:06
Do you mean change the value of array1 itself, or the pointers within it? You are not showing how the content of array1 is being created in the code. — Mats Petersson
– Mats Petersson, Commented Mar 14, 2013 at 20:07
@MatsPetersson I'm going to assign certain values to the elements of the array1, so de facto I will change the pointers. Sorry for the obscurity. — zawodny
– zawodny, Commented Mar 14, 2013 at 20:15

score 3 · Accepted Answer · 2013-03-14 20:42:00Z

3

Using this allocation:

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

The contents of array1 are undefined. Each element is a Node*, and because the memory is uninitialized, the value could be anything.

Allocating an array of pointers does not construct objects of the pointed-to class.

So whatever pointers you put into the array, the objects they point to need to be constructed and destructed elsewhere.

So to answer your question, the proper way to delete array1 is

delete[] array1;

However, note that this will not result in destructors being called for each Node* - you should deal with whatever you put into the array before you delete the array.

EDIT: I was confused by the original question, which mentioned "change the value" in the array, as if there was a valid value in the array as allocated in your example.

BUT... now that I understand you want to keep track of the pointers for deletion later, perhaps you can just create another array for that purpose where each pointer exists only once. So you have the array you currently have above, which contains pointers to nodes that might be repeated, for whatever purpose you're using it. Then you have another array for the express purpose of managing the deletion, where each pointer occurs only once. It should be easy enough to set something like nodeCleanupArray[i] = pNewNode right after pNewNode = new Node(), then you can blast through that array in linear time and delete each element. (Which means you wouldn't bother inspecting the elements in array1, you'd rely on nodeCleanupArray for the cleanup)

edited Mar 14, 2013 at 20:42

answered Mar 14, 2013 at 20:13

user2088639

Sign up to request clarification or add additional context in comments.

2 Comments

zawodny Over a year ago

Thank you very much for the quick and thorough respond. However, how can I manage the repeating pointers in the array1? I can't use preimplemented dynamic data structures like std::vector or any other STL containers for this, because I'm not allowed to do so in my project.

zawodny Over a year ago

Great, that's exactly what I wanted to do. Once again, sorry for the lack of clarity in my explanation of the problem but I didn't occur to have fun with the pointers to the pointers in C++ previously. Thank you :)

Mats Petersson · Accepted Answer · 2013-03-14 20:19:50Z

1

There are MANY solutions to this sort of problem, but the most obvious choice would be to change it to use

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

Now you will have a reference counted pointer without writing any code, and an "array" that doesn't need to know it's predefined size.

You can of course implement a reference counted object within Node, or your own container object to do the same thing, but that seems like extra hassle for little or no benefit.

answered Mar 14, 2013 at 20:19

Mats Petersson

130k15 gold badges147 silver badges233 bronze badges

Comments

Valeri Atamaniouk · Accepted Answer · 2013-03-14 20:12:21Z

0

Try mark and sweep :) You are trying to implement a managed environment.

Here is an example:

struct Node
{
... 
    bool marked;

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

Now delete:

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

answered Mar 14, 2013 at 20:12

Valeri Atamaniouk

5,1632 gold badges18 silver badges19 bronze badges

Comments

Blazes · Accepted Answer · 2013-03-14 20:15:40Z

0

The way I'd do this is have a reference counters and have a Node::deref method that would delete the node itself when reference count is 0. When iterating through the list of nodes, calling node->deref will not actually delete the object until the last Node reference in the array.

answered Mar 14, 2013 at 20:15

Blazes

4,7792 gold badges25 silver badges29 bronze badges

Comments

bames53 · Accepted Answer · 2013-03-14 20:51:13Z

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.

Collectives™ on Stack Overflow

Deleting a dynamic array of pointers in C++

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related