CODEWITHSUNDEEP
c++c++11memory-management
user775093
user775093

Reputation: 749

memory management for linked list and tree programs in c++

I solve algoritm questions from sites like leetcode, hacker rank or cracking the coding interview. I do most if the questions in c++. So for most of them i have a node struct as below

struct Node {
   Node* next;
   //for tree
   Node* left;
   Node* right;
   int data; 
   //ctor
   Node(int val) : left(nullptr);.....
};

then i have a function(s) which implements the algorithm

bool someAlgorithm(Node* root) {
  //do stuff
}

and finally i create the nodes in the main 

int main() {
  auto root = new  Node(4);
  root->left = new .. 
  root->left->left = new ..
}

I want to incorporate memory management in this kind of solutions. If i use c++11 shared_ptr do i need to provide a destructor ? if yes what should i write in the destructor ? But i found that shared_ptr makes code overly complex and un-understandbale for such small programs.

In general what is the best way to make solving such questions memory safe ?

Upvotes: 2

Views: 1005

Answers (3)

Laurent LA RIZZA
Laurent LA RIZZA

Reputation: 2975

If you want memory safety, start by realizing that objects created by new are a resource, i.e. something that is available in finite quantity in the system, that does not belong to your program, that your program has to borrow (through new in your case), and to give back (through delete in your case).

Resource management in C++11 maps this borrow/give back pair to the constructor/destructor pair. An object that borrows a resource through its constructor is said to OWN this resource, and is responsible for giving it back to the system.

Besides constructor and destructor, 4 other special functions participate to ownership:

  • The copy constructor: when an object is copied, you have to decide whether the resources may be owned by both resulting objects, or the resource should be duplicated, or if duplicating the resources is so meaningless/unfeasible, that copying the object should be disallowed.
  • The move constructor: loot the resources! An object is going to die. It may be a temporary unnamed object, a local object just about to be returned from a function, or an object that the programmer decided that it's going to die really soon (through the use of std::move), in any case, the object is not going to need its precious, expensively borrowed resources. So the new object can be made a full fledged object by taking ownership of the soon-to-die object's resources making them its own, thereby transferring ownership of the resources to the new object.
  • The copy assignment: the assigned-to object casts away (gives back) its presently owned resources and replaces them by a copy of the resources of the right-hand object. The decision of what to do is imperatively consistent with the copy constructor.
  • The move assignment. Same as copy assignment, but steals instead of duplicating. Goes hand-in-hand with the move constructor.

Therefore, if you read too fast, you may read that you have to reimplement all 6 of them. But this resource management is omnipresent in C++11, and the automatic generation of the special functions is made in a straightforward and sensible way, so that:

  • Copy/move constructors are automatically generated as resp. copying/moving all members of the object. So if any member cannot be copied/moved, the corresponding special function will not be generated.
  • Destructors destruct all member objects. So all resources releasing logic of members will be executed when an object dies.

C++11 provides some special classes to manage a single resource:

  • std::unique_ptr owns a single resource. It owns the resource, so it will release it if it still owns it when destroyed. You can't duplicate the resource, so copying it is disallowed. But the resource can change hands through moving. (loot!loot!loot!) It guarantees a single owner for the resource.
  • std::shared_ptr lets many objects share ownership of a single resource. You can copy it, and what you duplicate in this case is the ownership rights to the resource. In short, it maintains an appropriate counter on the resource to track how many pointers own it.

If you use instances of these classes to manage your allocated memory (as members of classes or as local varialbes), then deterministic resource release will automatically happen.

Upvotes: 0

Sam
Sam

Reputation: 101

The best way to make a simple problem like this memory safe is to add a destructor to node and delete the root node at the end of the program. Because root is allocated on the stack you will have a memory leak at the end currently.

Here's what the definition should somewhat look like.

~Node() {
    //call delete on every pointer in the struct
    delete next;
    delete left;
    delete right;
}

Then at the end of your program you can call delete root and the dtor will be called, recursively deleting every node below it. Even if you use shared_ptr or unique_ptr instead of calling delete you still need the dtor, otherwise all your child nodes will remain allocated when root is deleted.

Upvotes: 1

Matt
Matt

Reputation: 15176

If you need node deletion operation as part of your algorithm, you have to implement it yourself. No trick will help you to avoid it.

Deleting all nodes is quite straightforward task, as it requres just another traversing the tree structure, as you probably do anyway during someAlgorithm() execution.

So, I believe, the overall difficulty won't change much even if you choose manual deletion.

Upvotes: 0

Related Questions