Deleting a pointer to the list of pointers

Question

I create a class, which creates a new list of pointers to objects:

FeatureSet::FeatureSet() {
    this->featuresList = new list<HaarFeature*>;
    globalCounter = 0;
}

Now I would like to delete all object from the list, and then delete the pointer to the list. My code is:

FeatureSet::~FeatureSet() {
    for (list<HaarFeature*>::iterator it = featuresList->begin(); it !=     featuresList->end(); it++) {
        delete *it;
    }
    delete featuresList; // this take a long time (more than half a minute)
}

My question is what is the best method to solve this problem? Does my approach is correct? Unfortunately, currently the last operation (deleting a pointer to the list) takes about half minute. List has about 250000 objects.

Answer 1

You really need to use a different data structure. Depending on your mutation patterns, you may be better off with containers like a deque or vector.

Answer 2

Your approach is correct. And it seems like the appropriate way to go about doing what you're trying to do. But list deallocation is expensive. Maybe try a different data structure?

The following:

 for (; _Pnode != _Myhead; _Pnode = _Pnext)
 {  // delete an element
    _Pnext = _Nextnode(_Pnode);
     this->_Alnod.destroy(_Pnode);
     this->_Alnod.deallocate(_Pnode, 1);
 }

is where the code spends most of the time. It needs to iterate through all the nodes and remove them. There's really no way going around this for a list.

I suggest you use a std::vector, deallocation is much faster.

Answer 3

Given that you're using a list, yes, that's the way to go about deleting the sub-elements. Note that whatever container you use, if you're storing pointers, the operation of 'acquiring the next pointer and deleting it' is likely to take the same amount of time. It's certainly worth testing as an exercise.

You may get some savings in the deletion of the container (and it's contained nodes) itself. But the choice of parent container is more likely to be determined by it's usage elsewhere. For instance: If you're adding nodes to it piecemeal then a vector will have to reallocate and copy the whole block of pointers to maintain it's internal structure.

That said, I'd also agree with the point made above about dynamic allocation of the container itself. Might as well make it a concrete member variable. (Of course you still have to iterate across it and delete the node sub-contents. But that's more a function of convention than anything else.

Answer 4

OK. So I performed some research. I just have tested four solutions. Results are presented in the table below: (I can't put an image, please click the link)

Comparing an efficiency of list and vector containers

As you can see from the table, vector containing objects is the fastest solution. It is also true that storing pointers to objects is much slower than containing real objects.

SUMMARY:

• Sequential access to objects aggregated in list is slow, probably because it requires "jumping" from pointer to pointer and particular objects don't have to be stored in consecutive memory cells
• Sequential access to vector is fast, probably because objects are stored in linear, consecutive memory cells
• Using iterator to access consecutive objects is faster than using indexes, what isn't surprising
• Storing pointers instead of real objects is much slower, especially during allocation and deallocation of container (heap allocation)
• Independently from storing object type, deallocation of list is much slower than deallocating of vector

Answering to question asked by @Emile Cormier - Why I would like to use pointer to container? This ensure me an access to vector/list elements even after deletion of parent class object. Please consider this part of code:

class A{
public:
A(){
    this->test = new vector<int>;
    for(int i = 0; i < 10; i++){
        test->push_back(i);
    }
}
~A(){
    cout << "object A is dead\n";
    test->clear(); // <--- COMMENTING this line allows to access to the vector's elements "after death" without copying
}
vector<int>* GetPointer(){
    return this->test;
}
private:
vector<int>* test;
};

class B{
public:
B(){
    for(int i = 0; i < 10; i++){
        test.push_back(i);
    }
}
~B(){
    cout << "object B is dead\n";
    test.clear();
}
vector<int> GetbyValue(){
    return test;
}
private:
vector<int> test;
};

cout << "\nCASE A\n";
A* instance = new A();
vector<int>* local = instance->GetPointer();
delete instance; //deletion before calling!!!
//Access is impossible, because clear method in destructor destroys original vector, connected with pointer
cout << "Printing A\n";
for(int i = 0; i < local->size(); i++){
    cout << (*local)[i] << "\n";
}
cout << "\nCASE B\n";
B* instance2 = new B();
vector<int> local2 = instance2->GetbyValue();
delete instance2; //deletion before calling!!!
//Access is still possible, because vector has been copied to local variable
cout << "Printing B\n";
for(int i = 0; i < local2.size(); i++){
    cout << (local2)[i] << "\n";
}
cout << "THE END\n";

When I don't use a pointer to vector (case B), I although can access objects from vector after deletion of "B" class object BUT in reality I use a local copy of returned vector. Using a pointer to vector (case A) allows me to get an access to vector objects even after deletion of "A" class object, when I don't call clear() method in destructor manually of course.

Finally - thanks everyone for help. I think that my problem has been solved.