• Advertisement
Sign in to follow this  

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

This topic is 4249 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have an array filled with pointers to objects on the heap. Some of the elements in the array point to the same object as others. The obvious problem when cleaning up then is in cycling through the array and 'delete'-ing each unique object, without deleting any more than once... The only way I can think to do this is to construct a new array of unique pointers using a few nested for-loops (to scan through the original array and scan through a new array, checking and inserting), then scan through the new array deleting each element. Anything more elegant much appreciated....? Cheers,

Share this post


Link to post
Share on other sites
Advertisement
I suggest you look into smart pointers, such as boost::shared_ptr.

You could also delete an item, add the address in a list set, and ignore any future pointer with an address that is in that list set. [edit: which amounts to building a list of unique pointers, meh.]

[edit2: I wonder if ordering the list first, then deleting and skipping duplicates would be more efficient. Worth a try.]


jfl.

Share this post


Link to post
Share on other sites
It really depends on what exactally you are aiming for, if the reason you don't want to create another array is due to memory concerns, you could always sort first, or just delete one pointer every iteration of the list... Not really any very elegant way to do it.

Indy

Share this post


Link to post
Share on other sites
Ah, ok. Thats settled then, there is no better way. Not so bothered about memory/efficiency, just like to make sure my code is as elegant as possible.

Thanks for the swift replies,

Share this post


Link to post
Share on other sites
[edit: read Fruny's response]
[edit2: the iterators should be double pointers]
The STL provides unique(), which is required to be of linear complexity. Use would be something like:

Item *array[20];
// ...

Item **end = std::unique( array, array + 20 );
for( Item **it = array; it != end; ++it ) {
delete *it;
}
// clear array


[Edited by - jflanglois on July 4, 2006 2:37:56 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by jflanglois
The STL provides unique(), which is required to be of linear complexity.


Please be warned that the sequence needs to be sorted first. unique() only eliminates adjacent duplicates.

Item *array[20];
// ...

std::sort(array, array + 20);
Item *end = std::unique( array, array + 20 );
for( Item *it = array; it != end; ++it ) {
delete it;
}

Share this post


Link to post
Share on other sites
Though, if it's a relatively small list, I would probally iterate over the list once per every object I have to delete, Null every one I delete, then iterate again, from the next index I didn't null, Mostly just to save on the overhead of the allocation and destruction of the second list. But for no real preformance reasons.

Indy

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
Quote:
Original post by jflanglois
The STL provides unique(), which is required to be of linear complexity.


Please be warned that the sequence needs to be sorted first. unique() only eliminates adjacent duplicates.

Item *array[20];
// ...

std::sort(array, array + 20);
Item *end = std::unique( array, array + 20 );
for( Item *it = array; it != end; ++it ) {
delete it;
}

Exactly right. My mistake.
Quote:
unique()
Every time a consecutive group of duplicate elements ...


[Edited by - jflanglois on July 4, 2006 2:42:03 AM]

Share this post


Link to post
Share on other sites
Surely the most appropriate thing to do here is to store reference-counted smart pointers in the array, instead of raw pointers?!?!
Then you simply delete them all![cool]

Share this post


Link to post
Share on other sites
Or better yet, assuming you have control over the array....

std::vector< boost::shared_ptr<Item> > array;

// do stuff with array, insert pointers, etc.
//...

// Surely this is too easy to be true!!!
array.clear();

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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,

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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!)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by NotAYakk
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!)


To be fair, I'm not sure I fully understand this statement myself [grin]. In fact, I can't see how delete could modify its pointer parameter.

Share this post


Link to post
Share on other sites
Emmanuel,

Sorry for my previous reply, I didn't take the time to fully analyse what the second point implicated. This is a thing I never knew of and I have to agree with you now that my idea is to be avoided...

I think i'll revise some of my own code... just to be sure I never made such a mistake! So the good way of doing it would be to make all the pointers appear just once in the array and then, to delete those pointers?

Yours

Share this post


Link to post
Share on other sites
Quote:
Original post by Emmanuel Deloget
Quote:
Original post by NotAYakk
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!)


To be fair, I'm not sure I fully understand this statement myself [grin]. In fact, I can't see how delete could modify its pointer parameter.


The implementation is allowed, in particular, to null out the pointer, "for safety". Stroustrup mentions this in his FAQs, lamenting that most implementors have not done this. But it wouldn't really be any use AFAICT without a guarantee, anyway, because you still have to write your code as if that behaviour didn't exist.

Share this post


Link to post
Share on other sites
Quote:
Original post by rikibee
So the good way of doing it would be to make all the pointers appear just once in the array and then, to delete those pointers?

Yes - using, for example, Fruny's code. But mikeman made a very valid point:

Quote:
Original post by mikeman
The question is, why do you keep an array that has multiple elements that point to the same object?

This is not a very good idea, mostly because of this ownership problem. Moreover, if one is able to push_back() the same value twice, it means that the pointer is already owned by someone else. Transfering the ownership of a single pointer twice is rather weird. I guess that while Fruny's solution would help, the correct solution would be to consider that this vector don't own the pointers - meaning that someone else does (Shannon Barber's solution).

Quote:

The implementation is allowed, in particular, to null out the pointer, "for safety". Stroustrup mentions this in his FAQs, lamenting that most implementors have not done this. But it wouldn't really be any use AFAICT without a guarantee, anyway, because you still have to write your code as if that behaviour didn't exist.

Thanks :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement