Doubly circular linked list memory access error

Question

i've been trying to figure it out by my self but I cant figure it out, I've try to implement a doubly circular linked list template class, in purpose to create a menu for an app with SFML.

I dont know why but when i implement an instance of CDblLinkedList (int,string,sf::Text) it work without any error, but when i try to insert in CDblLinkedList an instance of CSubMenu i got an error Exception has occurred. EXC_BAD_ACCESS (code=1, address=0x170). When i debug it i've saw that at the second call of the destructor ~CDblLinkedList(), head->GetPrev()->SetNext(nullptr); generate this error because the prev pointer of the head is equal to nullptr.

CNode.h

#pragma once
template <typename T>
class CNode{

    private:
        CNode<T>*prev=nullptr;
        T data;
        CNode<T>*next=nullptr;

    public:
        CNode(T p_data);
        void SetNext(CNode<T>*p_next){next=p_next;};
        void SetPrev(CNode<T>*p_prev){prev=p_prev;};
        CNode<T>* GetNext(void){return(next);};
        CNode<T>* GetPrev(void){return(prev);};
        T* GetData(void){return(&data);};

};

template <typename T>
CNode<T>::CNode(T p_data):data(p_data){
   // data=p_data;
}

CDblLinkedList.h

#pragma once
#include "CNode.h"
#include <iostream>
template <typename T>
class CDblLinkedList{
    private:
        CNode<T>*head=nullptr,*current=nullptr;
    public:
        CDblLinkedList();
        void Insert(T p_data);
        void Next();
        void Prev();
        CNode<T>*GetCurr(void){return(current);};
        CNode<T>*GetHead(void){return(head);};
        ~CDblLinkedList();
};

template<typename T>
CDblLinkedList<T>::CDblLinkedList(){
}

template<typename T>
void CDblLinkedList<T>::Insert(T p_data){
    CNode<T> * dummy=new CNode<T>(p_data);
    if(!head){
        head=dummy;
        head->SetNext(head);
        head->SetPrev(head);
        current=head;
    }else{
        dummy->SetPrev(head->GetPrev());
        dummy->SetNext(head);
        head->GetPrev()->SetNext(dummy);
        head->SetPrev(dummy);
    }
}
template<typename T>
void CDblLinkedList<T>::Next(){
    current=current->GetNext();
}
template<typename T>
void CDblLinkedList<T>::Prev(){
    current=current->GetPrev();
}

template<typename T>
CDblLinkedList<T>::~CDblLinkedList(){
    if(head){
       head->GetPrev()->SetNext(nullptr);
        CNode<T>* dummy=nullptr;
        while(head){
            dummy=head;
            head=head->GetNext();
            delete dummy;
            dummy=nullptr;
        }
        head=nullptr;
        current=nullptr;
    }
}

main.cpp

#include<SFML/Graphics.hpp>
#include "CSubMenu.h"
int main(){
    sf::RenderWindow window({ 1600 ,900 }, "test");
    sf::Font font;
    font.loadFromFile("./assets/fonts/Oswald-Bold.ttf");
    CSubMenu left(300,450,"AlgoText",font,&window);
    left.AddChoice("1- BFS");
    left.AddChoice("2- DFS");
    left.AddChoice("3- A*");
    CDblLinkedList<CSubMenu>list;
    list.Insert(left);

    return 0;
}

I've try to create separate CSubMenu instance it work, but not when i try to insert one of them in a CDblLinkedList instance.

Thank you in advance :)

Answer 1

Implicit copies

You see multiple destructor calls, because copies of your type T object are created. See your modified code example that shows the constructor/destructor calls. Inserting a single element to list leads to multiple destructor calls, because multiple copies of T are made in the process.

This could explain why using type CDblLinkedList<int> works, but not CDblLinkedList<CSubMenu>. The latter most likely has no proper copy constructor.

There are plenty of ressources that explain this issue. In short: If you copy an object that holds a pointer and then at the end of its lifetime the destructor calls a delete on that pointer, you must write a copy constructor or you will end up with double delete issues. Because both - the original and the copied object - point to same address and therefore try to delete the same thing when destroyed.

Copy locations

First copy occurs when copying the argument in CNode.h:

list.Insert(left); 

Second copy: p_data is copied when calling the constructor of CNode while in function CDblLinkedList<T>::Insert:

CNode<T>* dummy = new CNode<T>(p_data); 

Third copy: Copy p_data argument to p_data member in CNode<T> constructor:

CNode<T>::CNode(T p_data) : data(p_data) {
    // data=p_data;
}

Solution

A) Provide a bug-free copy constructor for T similar to your modified code example.

B) Avoid copies of T that cause problems by providing a move constructor and then modify the code so that T is moved instead copied.

C) Or decouple lifetime issues from your class CDblLinkedList by only passing it a reference or a pointer to your Item, eg. use CDblLinkedList<CSubMenu&>, as demonstrated in this example on compiler-explorer. Additionally, to prevent unintended copies, explicitly delete the copy constructor: Foo(const Foo& other) = delete;