c++ templates and destructor problems

Question

How to deal with memory leaking with template classes in C++?

In this code I defined 4 template classes:

• class node and class linked_list make up a doubly linked list
• class item and class bag just make up another doubly linked list

These template classes are designed to deal with objects of various classes. In the main function, I first created a linked_list<string> and a bag<int> and everything is fine.

But when I try to make a bag<linked_list<string>>, problems arise. I tried to trace back to see what happened, and I saw that in the function push_back in class bag, a destructor of linked_list has been called that erased all the data in the input v. I don't know why that happens.

Note that I overwrote the destructors for all classes and called className.~className() in the main function to prevent memory leaking. And it does work to prevent memory leaking from ls_1 and bag_1.

I don't know which part of my code is wrong. Can somebody help me?

#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;


//node and linked_list class make up a doubly linked list
template<class T> class node {
public:
    T value;
    node<T> * next;
    node<T> * previous;
    node<T>() { next = nullptr; previous = nullptr;  }
    node<T>(T v) { value = v; next = nullptr; previous = nullptr; }
    ~node<T>() { delete next; }
};

template<class T> class linked_list { //doubly linked list
public:
    node<T> * head;
    node<T> * tail;
    linked_list<T>() { head = nullptr; tail = nullptr;  }
    ~linked_list<T>() { delete head; }

    void push_front(T v) { //insert an item to the front
        node<T> * p = new node<T>(v);
        p->next = head;
        head = p;

        if (tail == nullptr) {
            tail = p;
        }
    }
};

//item and bag class just make up another doubly linked list
template<class X> class item {
public:
    X value;
    item<X> *next;
    item<X> *previous;
    item<X>(X v) { value = v; next = nullptr; previous = nullptr; }
    ~item<X>() { delete next; }
};

template<class X> class bag { //just another doubly linked list
public:
    item<X> *last;
    item<X> *first;
    int num_items;
    int size() { return num_items; }
    bag() { last = nullptr; first = nullptr; num_items = 0; } 
    ~bag() { delete first; }

    void push_back(X v) {  //insert an item to the back
        item<X> * p = new item<X>(v);

        if (num_items == 0) {
            last = first = p;
        }
        else {
            last->next = p;
            p->previous = last;
            last = p;
        }

        num_items++;
        last->next = nullptr;
    }
};

int main() {
    //When using built-in classes (like strings) as input
    //there's no problem at all
    linked_list<string> ls_1;
    ls_1.push_front("David");
    ls_1.push_front("John");

    bag<int> bag_1;
    bag_1.push_back(1);
    bag_1.push_back(2);

    //Problems arise here when using user defined classes (linked_list) as input
    //I traced back and found out that a destructor has been called
    //that erases all the data in the input. Donno how that happens
    bag<linked_list<string>> bag_string;
    bag_string.push_back(ls_1);

    //These lines are to prevent the memory leaking
    //I overwrote destructors for linked_list and node class
    //otherwise there's still memory leaking
    ls_1.~linked_list(); 
    bag_1.~bag();
    bag_string.~bag();

    _CrtDumpMemoryLeaks();

    getchar();
    getchar();
}

Answer 1

Implement node, linked_list, item, bag copy constructors and assignments or declare them as deleted. The default versions generated by the compiler do not do the deep copying and that leads to multiple deletes of same objects after they were copied.

Read the rule of three/five/zero for full details.

---

A bit off-topic, but making a list node delete its siblings is a classic gotcha: for a sufficiently long list it ends up calling ~node<T>() recursively until it exhausts the stack. And this is the reason node pointers cannot be smart-pointers.

A fix would be to have a default destructor for nodes and make the list destroy the nodes in a loop, rather than recursively.

---

You may also like to use the full list node as a head of the list that points to itself when empty. That removes that nullptr checking logic completely.

Answer 2

I tried to trace back to see what happened, and I saw that in the function push_back in class bag, a destructor of linked_list has been called that erased all the data in the input v

Yes, this happens because your bag::push_back() takes its argument by value. This means it creates a copy of the ls_1 you created in main. You have not specified how to "copy" a list, so the compiler generated this function (a copy constructor) automatically. It can do that because your linked_list only contains two pointers, so the compiler assumes (because you have not told it otherwise) that copying the pointers over is all that is necessary to generate a copy of a linked_list. Unfortunately, that is not correct.

You now have two lists that manage the same contents: The original ls_1 in main() and the function argument v in push_back() - they both contain the same pointers.

Then the same thing happens again in your item constructor: You make a local copy of the list that holds the same pointers as the first two.

You now have several list objects pointing to the same data. Each one will try to destroy the data once it dies. This results in undefined behavior.

---

To correct this, you need to figure out how copying of a list should work. This is (in part) what the rule linked in the other comment is about: If the destructor of your class is not trivial (i.e. the compiler-generated version would not be sufficient, most likely because you need to release a resource like allocated memory), you should/must always care about how to handle your class being copied around. The various mechanisms that may invoke copy-like behavior (assignment, copy constructor, plus move versions in newer C++) need to be specified (or forbidden) by you.