Back to General and Gameplay Programming

Technique for destroying an array of non-unique objects (C++)?

General and Gameplay Programming Programming

Started by DangerDave July 04, 2006 01:11 AM

22 comments, last by Emmanuel Deloget 17 years, 9 months ago

122

July 04, 2006 08:46 AM

What I would do first is to sort the array.

Then you iterate in the sorted array and delete every pointers except if the pointer you're at is the same one you juste deleted. It keeps you from having two imbricated loops which is n^2 of complexity.

Something like that:

Item* Array[ARRAYSIZE];SortFunction( Array );Item* p = 0;for( int i = 0; i < ARRAYSIZE; ++i ){   if( Array != p )   {      p = Array;      delete Array;   }}

If you use a convenable sorting algorithm, you will have n*log(n) of complexity which is better than n^2 for an array of any size. ( Ok, its actually n*lg(n) plus n plus a constant, but it is still very much better than n^2! )

[Edited by - rikibee on July 4, 2006 4:46:27 PM]

CTar

1,134

July 04, 2006 09:05 AM

Quote:Original post by rikibee
What I would do first is to sort the array.

Then you iterate in the sorted array and delete every pointers except if the pointer you're at is the same one you juste deleted. It keeps you from having two imbricated loops which is n^2 of complexity.

Something like that:
*** Source Snippet Removed ***

If you use a convenable sorting algorithm, you will have n*log(n) of complexity which is better than n^2 for an array of any size. ( Ok, its actually n*lg(n) plus n plus a constant, but it is still very much better than n^2! )

Don't do this! If you want to use an approach like this then use what Fruny posted.

Shannon Barber

1,684

July 04, 2006 09:24 AM

You should keep two sets of pointers to the data.

The second set, which you already have, is topological and related to the functionality of the program. The first set is a simple list (read std::vector) that owns the objects. Topological sets never destroy objects, they only (weakly) reference them.

When you want to destroy an object you remove it from all the topological sets then remove & destroy it from the owning container.

- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara

rikibee

122

July 04, 2006 10:12 AM

Quote:Original post by CTar
Don't do this! If you want to use an approach like this then use what Fruny posted.

Why not?

Have i made some obvious error? I am certainly not an expert, I would like to know what is wrong with my idea?

Yours

Emmanuel Deloget

1,382

July 04, 2006 11:11 AM

Quote:Original post by rikibee
Quote:Original post by CTar
Don't do this! If you want to use an approach like this then use what Fruny posted.

Why not?

Have i made some obvious error? I am certainly not an expert, I would like to know what is wrong with my idea?

Yours

Quote:5.3.5 §4 of The Holy One
If the delete-expression calls the implementation deallocation function, and if the operand of the delete expression is not the null pointer constant, the deallocation function will deallocate the storage referenced by the pointer thus rendering the pointer invalid. [Note: the value of a pointer that refers to deallocated storage is indeterminate])

Emphasis is mine.

There is two problems with your code:

1) you are comparing a valid pointer to an invalid pointer. This is, in essence, bad.
2) If I understand the emphasized sentence correctly (Washuism might be needed for confirmation), the delete expression is not required to leave your now invalid pointer unchanged.

Other problems might arise if you consider multiple inheritance (not sure of this one).

Regards,

-- Emmanuel D. [blog, in French] [blog, very bad googlized translation]

Nitage

1,107

July 04, 2006 12:46 PM

It may not work with multiple inheritance due to the void* cast. Two pointers that point to the same object may not give the same void* if they are pointers to different types.

The method Fruny provided doesn't contain the bugs in your method - this is a good example of why it's preferable to use standard functions.

rikibee

122

July 04, 2006 12:59 PM

I see, thanks!
the type cast void* was a bad idea. I put void* because I didn't know the type of object that was stored in the array. Lets just call this type Item* :) I edited my code to make it more consistent with my idea.

For sure, the best would be to use smart-pointers or to introduce reference counting in the base class of those items.

Emmanuel Deloget

1,382

July 04, 2006 01:11 PM

Quote:Original post by rikibee
I see, thanks!
the type cast void* was a bad idea. I put void* because I didn't know the type of object that was stored in the array. Lets just call this type Item* :) I edited my code to make it more consistent with my idea.

Even if you update your code, the problem persists - read again point 2 in my post :)

-- Emmanuel D. [blog, in French] [blog, very bad googlized translation]

NotAYakk

876

July 04, 2006 01:19 PM

Once a pointer is deleted, it is no longer valid. You may not compare it with other pointers and expect a reasonable response. If you get a reasonable response, it is only because you are lucky.

(Edit: to be clear: the above statement is an attempt to restate claims written above. I am a touch surprised by this information myself!)

mikeman

3,017

July 04, 2006 01:42 PM

The question is, why do you keep an array that has multiple elements that point to the same object? You're probably using it so you can perform some operations to the objects. In that case, deletion is not your only problem. Wouldn't you, say, update the same object 2 or more times in the same iteration? The whole idea of keeping such an array, plus using it to actually destroy objects sounds like a bad idea on its own.

Hyperdrive - Futuristic Combat Racing

Technique for destroying an array of non-unique objects (C++)?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Technique for destroying an array of non-unique objects (C++)?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines