0

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 ?

Lajos Arpad
  • 64,414
  • 37
  • 100
  • 175
Kain
  • 329
  • 1
  • 10
  • 3
    This `start->~node();` is very strange. And why use placement new here `new (new_node) node(value);` ? I don't think placement new / delete are required in this program. – Richard Critten Nov 18 '22 at 14:38
  • 1
    Even compiler finds error: https://godbolt.org/z/Kevjhenvo – Marek R Nov 18 '22 at 14:38
  • 1
    The code violates the rule of 3 / 5 /0: [https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) – drescherjm Nov 18 '22 at 14:40
  • Could you elaborate ? – Kain Nov 18 '22 at 14:41
  • 1
    *I'm trying to implement a linked list in C++* -- Why did you get into the weeds of using `placement-new`? Why not simply use `new`, and then graduate to smart pointers from there? – PaulMcKenzie Nov 18 '22 at 14:44
  • Again compiler explains what is the issue: after one iteration when object was deleted, `start->next` (in for statement) is access to go to next element what is UB! – Marek R Nov 18 '22 at 14:44
  • @Kain This for loop for (auto start = head; start != nullptr; start = start->next) { start->~node(); alloc.deallocate(start, 1); } invokes undefined behavior. – Vlad from Moscow Nov 18 '22 at 14:44
  • @PaulMcKenzie I read that construct and destroy is deprecated in C++17 here : https://stackoverflow.com/questions/59539057/c-does-it-lead-to-double-free-when-destroy-element-in-allocatorstring – Kain Nov 18 '22 at 14:45
  • @VladfromMoscow Could you explain to me why does it do that ? – Kain Nov 18 '22 at 14:45
  • @PaulMcKenzie I wonder if the point was to allow a different allocator to be substituted in instead of the default one. This was the syntax used in C++98 – Spencer Nov 18 '22 at 14:47
  • When you insert a new node, it's `next` pointer is left uninitialized. How should the condition `start != nullptr` work? Also, `head->next = new_node; head = new_node;` doesn't make sense to me. Where does `head->next` point to after those assignments? – Evg Nov 18 '22 at 14:49
  • `start = start->next` since `start` was already destructed, use-after-destruction is **undefined behavior**. – Eljay Nov 18 '22 at 14:49
  • 3
    Problem is not related to rule 3/5/0 since nothing gets copied or assigned. Problem is use after free! – Marek R Nov 18 '22 at 14:50
  • The Rule of Three doesn't even **remotely** apply here. – Spencer Nov 18 '22 at 14:50
  • @Eljay I figured it out, thanks. – Kain Nov 18 '22 at 14:53
  • 1
    *construct and destroy is deprecated in C++17* - That's true, but the answer you're referring to is wrong. The correct way is to go through `std::allocator_traits`, which has a static member function `construct()`. See [here](https://en.cppreference.com/w/cpp/memory/allocator_traits/construct). This is also true for `allocate()`. – Evg Nov 18 '22 at 15:03
  • Note, your `node`s only have a pointer to the next element, and when you push element to list, you are updating the `head` pointer to the new element, which means you don't have a way to get back to the first element. – Ranoiaetep Nov 18 '22 at 15:14

1 Answers1

2

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.

Spencer
  • 1,924
  • 15
  • 27