8-puzzle problem, with memory leaks. C++

Question

I'm trying to apply breadth first search algorithm to solve 8-puzzle game in C++, the algorithm works fine, and so far finds the necessary moves to solve a 3x3 problem.

But using fsanitize, I got a lot of memory leaks, I checked the code for hours and not sure why the code still have memory leaks, here's the code (somehow solo learn doesn't show any output).

https://code.sololearn.com/cA2a0887A14A

Basically, each Node has the possible state after you move the blank tile up, down, left, right, my_deque holds all the possible states and possible_paths holds the nodes with the possible states depending of its current state.
The function expand_node() - line 73 - Is reserving some memory to those nodes and inserting it to a deque. That's why when I reach my goal, at lines 106-109 I'm deleting those nodes that were reserved in expand_node() function.

I'm also deleting the memory that was reserved from expand_node(), deleting each node that it's already visited (123-126).

Finally, I return current_state that is a node, each node has a parent so, I delete each parent after printing what moves you need to solve the puzzle, (166-169).

But still... fsanitize throws me some memory leaks... I'm not sure if I'm deleting correctly or where I need to delete more.

Any idea about how can I solve this?

Answer 1

Yes, you leak a lot of memory because you never delete the currently processed node in breadth_first_search() after it has been popped, but was not the note to be returned.
I understand that you don't do this because in main(), you want to be able to trace back the steps, but then the problem is that you only delete the one correct path in the entire tree you've built. It's a bit hard to explain like this, so if it is not clear where you leak, try sketching a few levels of the node structure and look at what happens if different nodes contain the final state.
Unfortunately, I haven't been able to come up with a clever deletion algorithm. If you want to be able to trace back, one way would be to keep a stack of operations in every node that inherits the stack from its parent and only adds the operation of its parent onto it. In this case, you wouldn't need the parent link anymore, and could delete processed notes immediately.

Edit: Maybe something like this:

https://code.sololearn.com/ca16a191A4A1/?ref=app

Answer 2

Shadow yeah... Using smart pointers definitely solves the leak problem, pretty smart, also saving the path to trace back the moves instead having a Node* is better.

There is some things that not sure how it works.
You are creating a:

deque<Node>

but why not use deque<Node *> or deque<std::unique_ptr< Node> > ?

Doing:

my_deque.emplace_back( initial_state, NO_OP, nullptr );

You are emplacing back a node which lives in the stack right? or it will live in the heap?

Now doing:

auto current_state = std::make_unique< Node >( my_deque.front());

You are getting that Node which will live now in the heap?

Also these lines:

Node( const Node& ) = default;
~Node() = default;

I guess that the copy constructor and destructor do everything automatically for you because the default ? Does std::unique_ptr needs the destructor to delete the pointer?

Also this line:

auto operator = ( const Node& ) -> Node& = default;

I don't understand, why "-> Node&?

Is necessary to have these lines:?

// Node( const Node& ) = default;
// auto operator = ( const Node& ) -> Node& = default;
// ~Node() = default;

I commented those lines and the code works fine, what would be the difference to have them and not to have them?

Maybe it's because I don't understand very well how smart pointers works but definitely I should learn them to avoid the tedious leaks.

Thank you so much, reading your code I feel it more like C++ style.

Answer 3

Containers that can store arbitrary amounts of elements usually allocate their space on the heap. In this case, I don't see any need to create another level of indirection, i.e. storing a (smart) pointer on the heap that itself refers to a node on the heap allocated elsewhere. The emplace_back() method simply constructs a node instance in such pre-allocated space.

Via std::make_unique(), I obtain an independant copy of the foremost node in the container that lives separately from the container on the heap, managed by the created smart pointer.

The defaulted constructor/ destructor/ assignment operator are remnants of the old Node class that contained a pointer. A compiler will likely issue a warning if no explicit declarations are made in such a case. I only put them there to silence those.

auto operator = ( ... ) -> const Node&;
is the same as
const Node& operator = ( ... );
and known as trailing return type syntax, a technique mainly helpful in template programming. I lately adopted it style-wise.

Answer 4

Smart pointers are simply wrappers around a pointer that manage a heap-allocated object. They have not too much overhead, which is why in modern C++, it is recommened to use them over plain new allocations.

A unique_ptr is solely responsible for its object, you can't copy it. The class will automatically delete its pointer if it is replaced by the programmer via a method, or if the smart pointer itself is destroyed. Either way, you don't have to worry about memory leaks.

In case of a shared_ptr, multiple smart pointers may manage the same pointer. The class internally keeps count of how many instances manage a pointer, and only delete the pointer once the last copy is destroyed. Therefore, they allow copy mechanics, but have slightly more overhead.

More here:

https://en.cppreference.com/w/cpp/memory

But it's really no magic. Here are sample implementations of both, if you are interested:

https://code.sololearn.com/cZumoInVE9ib/?ref=app
https://code.sololearn.com/cx1gqrR45Dqv/?ref=app