Deleting data that is pointed to by multiple lists?

Question

I have a an object that will potentially end up in multiple lists.

For example

std::list<object*> lista = new std::list<object*>();
std::list<object*> listb = new std::list<object*>();

object* obj = new object();
lista->push_front(obj);
listb->push_front(obj);

Potentially, there are many objects that will end up in both lists in the same way. I realize smart pointers would be the easy thing to do, but call me a masochist - I'd prefer to figure out how to do it without.

Currently, I'm trying this technique:

td::list<object*>::iterator iter;
for(iter = lista->begin(); iter != lista->end(); iter++) {
    delete (*iter);
    *iter = 0;
}

std::list<object*>::iterator iterB;
for(iterB = listb->begin(); iterB != listb->end(); iterB++) {
    if(*iterB != 0) {
        delete (*iterB);
        *iter = 0;
    }
}

delete lista;
delete listb;

But it breaks on my equivalent of delete lista; at run time. Hopefully someone out there smarter about pointers can help me out. Thanks in advance!

P.S. I'm running Windows 7/MinGW.

Answer 1

A main problem is that you (apparently, you do not offer complete code) delete an object twice: once when iterating through list A, and once when iterating through list B.

There are three main solutions:

• Use a ref-counting smart pointer like std::shared_ptr.
  Recommended. Your statement that you do not want to use a smart pointer seems to be made out of ignorance rather than some silly-manager's requirement.

• Keep the nodes also in a primary list:
  delete a node only when you know that the only list it's still in, is the primary list.

• Implement a reference count yourself:
  The easiest is again to use an existing library solution such as boost::intrusive_ptr, but all you have to do is to meticulously maintain a reference count in each node. delete when the reference count goes down to 0.

A fourth possibility is to use a garbage collector such as the Boehm collector, but then the code needs to be structured to support it. Or at least that's my impression. And it may be difficult to get help with that, since very few C++ programmers use that approach (which indicates that it's not entirely free of problems).

Answer 2

Use shared_ptr or have a master list with unique_ptr.

Failing that, have a master list that owns the pointers, and delete from it after you clear but do not delete all other lists.

Failing that, do not directly delete from a list directly. Instead insert the pointers you want gone into a std::set, and either remove them from the other lists before deleting (iterate and find in the set), or accumulate all the pointers you want to dispose of then mass delete them from the set.

This is in rough order of suckitude by paragraph.

Answer 3

Not sure why you don't really want to use shared_ptr. Ok suit yourself. How about you just create a local shared_ptr? If not then load both the list into one master list. Clear the two sublist, and delete each element in the master list as well as clearing the master list.

Answer 4

In the line

if(*iterB != 0) {

*iterB will never be 0. So you are double deleting.

Answer 5

Add counter field to your object. Default initialize to 0. Add +1 on adding to a list. -1 on removal from a list. If counter==0, delete the object.

This is not thread safe as shared_ptr, but it can be much faster for the same reason.