TigerCode TigerCode - 1 month ago 26
C++ Question

Singly Linked List - Segmentation Error due to Destructor implementation

I'm trying to figure out why I'm getting a seg-error from my singly linked list implementation.

I create an object of type Deque called dq1, compiler calls the destructor for it since the program is done - destructor calls remove_front() which deals with some move()'s for the head. I believe this is where the problem lies but I can't seem to figure out where exactly it is.

Debugger Info - Dont know what to make of this?

#0 0x4013ea std::unique_ptr<Node, std::default_delete<Node> >::get(this=0x8) (/usr/include/c++/6/bits/unique_ptr.h:305)
#1 0x401586 std::unique_ptr<Node, std::default_delete<Node> >::operator bool(this=0x8) (/usr/include/c++/6/bits/unique_ptr.h:319)
#2 0x40140b std::operator!=<Node, std::default_delete<Node> >(std::unique_ptr<Node, std::default_delete<Node> > const&, decltype(nullptr))(__x=<error reading variable: Cannot access memory at address 0x8>) (/usr/include/c++/6/bits/unique_ptr.h:670)
#3 0x401132 Deque::size(this=0x7fffffffe520) (Deque.cpp:75)
#4 0x4010f2 Deque::empty(this=0x7fffffffe520) (Deque.cpp:66)
#5 0x4016dd main() (/test.cpp:12)


Deque.cpp

#include "Deque.h"
#include <iostream>
#include <memory>
#include <utility>
#include <stdexcept>

using std::cout;
using std::endl;
using std::move;

Deque::~Deque()
{
while (!empty()) remove_front();
}


void Deque::insert_front(int a)
{
std::unique_ptr<Node> new_node;
new_node->val = move(a);
new_node->next = move(head); // head is wiped.
head = move(new_node); //head is init. with new_node val*/
}


int Deque::remove_front()
{
if (empty()) {throw std::runtime_error(std::string("Empty"));};

std::unique_ptr<Node> old;
int return_value = head->val;
old = move(head);
head = move(old->next);
delete &old;
return return_value;
}


bool Deque::empty() const
{
return (size() == 0);
}
int Deque::size() const
{

int size_val = 0;
const Node* p = head.get();

while ( p != NULL)
{
size_val++;
p = p->next.get();
}
return size_val;
}


test.cpp

#include <iostream>
#include "Deque.h"



using std::cout;
using std::endl;

int main()
{

Deque dq1;
return 0;
}


deque.h

#include "Node.h"
#include <memory>

class Deque{
public:
Deque() = default;
Deque(const Deque&);
~Deque(); //must use constant space
Deque& operator=(const Deque&){return *this;};
void insert_front(int);
int remove_front();
bool empty() const;

private:
friend Node;
std::unique_ptr<Node> head ;
std::unique_ptr<Node> tail ;

};


Node.h

#include "Node.h"

std::ostream& operator<<(std::ostream& out, const Node& n) {
return out << &n << ": " << n.val << " -> " << n.next.get();
}

Answer

You have UB right here:

std::unique_ptr<Node> new_node;
new_node->val = move(a);

you create a new pointer that is default initialized (points to nullptr) and you dereference it. You should initialize it with std::make_unique if you have C++14 or later or just initialize it with new:

std::unique_ptr<Node> new_node = std::make_unique<Node>(); // C++14 or later
std::unique_ptr<Node> new_node( new Node ); // pre C++14

This line also has issue:

delete &old;

this line does not make any sense. You get address of pointer itself, which is created as local variable and try to delete it. If you tried to delete data, where old points to, that is ether wrong - whole point of std::unique_ptr is to do that automatically.

This member:

std::unique_ptr<Node> tail ;

this is wrong by design, though you do not seem to use it in your code. This assumes you are going to have multiple std::unique_ptr to point to the same object. But this pointer is for unique ownership.

You seem to have issue in Deque::size() as well, but without seeing source it is impossible to say what is wrong there.

In your destructor you do not need to do anything (though it would not harm if other methods are implemented properly) - std::unqiue_ptr will destroy all data recursively.

Comments