I'm trying to implement a linked list in C . The list contains a pointer to a node type allocated on the heap

The code is as follow:

#include <memory>

template<typename T>
class node {
public:
    node(T v) : value(v) {}
    
    ~node() = default;

    T value;
    node *next;
};

template<typename T, class Allocator = std::allocator<node<T>>>
class linked_list {
private:
    node<T>* head;
    Allocator alloc;

public:
    linked_list() : head(nullptr) {}

    ~linked_list() {
        for (auto start = head; start != nullptr; start = start->next) {
            start->~node();
            alloc.deallocate(start, 1);
        }
    }

    void push_back(T value) {
        node<T> *new_node = alloc.allocate(1); 
        new (new_node) node<T>(value);

        if (head == nullptr) {
            head = new_node;
            return;    
        }

        head->next = new_node;
        head = new_node;
    }
};

In main.cpp:

#include "linked_list.hpp"

int main() {
    linked_list<int> a;

    a.push_back(4);
    a.push_back(5);


    return 0;
}

When I ran it I got double free detected in cache T2. What did I do wrong with the destructor ?

CodePudding user response：

This is a common newbie error. You modified your loop control variable.

for (auto start = head; start != nullptr; start = start->next)
{
     start->~node();
     alloc.deallocate(start, 1);
}

You modified start (deleting the memory) in the for loop's body and then tried to dereference the pointer you just deleted in its continuation expression. BOOM! You are fortunate that the runtime library was smart enough to catch this and give you the "double free" error rather than, say, launch a nuclear missile.

This is one place a while loop is better than a for loop.

while (head)
{
   auto to_del = head;
   head = head->next; 
   to_del ->~node();
   alloc.deallocate(to_del, 1);
}

I've left out a lot of commentary about your antiquated techniques because they don't relate to the problem you're having, but if you really want to substitute in a different kind of allocator you should look into using allocator_traits for allocation, construction, destruction, and deallocation of your elements.

There are other problems, such as push_back being completely wrong as to where it inserts the new node. Replacing head->next = new_node; with new_node->next = head; will at least keep your program from orphaning all of the new nodes.