Look through smart pointer with a binary tree example

Preface

Recently, I learned the shared_pointer in C++11, but things is much complicated then I expected before, in this article, I will go through the an “easy” implementation of binary seach tree, then I will throw out a new concept- weak pointer.

Example

First Case

First, let me implement a tree node using shared pointer

#include <iostream>x
#include <memory>

class Node {
    int value;
public:
    std::shared_ptr<Node> left_ptr;
    std::shared_ptr<Node> right_ptr;
    Node(int val) : value(val) {
        std::cout<<"Contructor"<<std::endl;
    }
    ~Node() {
        std::cout<<"Destructor"<<std::endl;
    }
};

int main () {
    std::shared_ptr<Node> ptr = std::make_shared<Node>(4);
    ptr->left_ptr = std::make_shared<Node>(2);
    ptr->right_ptr = std::make_shared<Node>(5);
}

You can see the nodes are deleted safely.

Circle Reference Case

//
// Created by 佘国榛 on 2018/6/27.
//
#include <iostream>
#include <memory>

class Node {
    int value;
public:
    std::shared_ptr<Node> left_ptr;
    std::shared_ptr<Node> right_ptr;
    std::shared_ptr<Node> parent_ptr;
    Node(int val) : value(val) {
        std::cout<<"Contructor"<<std::endl;
    }
    ~Node() {
        std::cout<<"Destructor"<<std::endl;
    }
};

int main () {
    std::shared_ptr<Node> ptr = std::make_shared<Node>(4);
    ptr->left_ptr = std::make_shared<Node>(2);
    ptr->left_ptr->parent_ptr = ptr;
    ptr->right_ptr = std::make_shared<Node>(5);
    ptr->right_ptr->parent_ptr = ptr;

    std::cout<<"ptr reference count = "<<ptr.use_count()<<std::endl;
    std::cout<<"ptr->leftPtr reference count = "<<ptr->left_ptr.use_count()<<std::endl;
    std::cout<<"ptr->rightPtr reference count = "<<ptr->right_ptr.use_count()<<std::endl;
    return 0;
}

Result:

Contructor
Contructor
Contructor
ptr reference count = 3
ptr->leftPtr reference count = 1
ptr->rightPtr reference count = 1

You can see through output that the three node is not properly deallocated;

Why?????

Let me take a look at what happens during the process. When we reach the end of main function, we will delete the local variable, namely, ptr, but when we check the reference count of the ptr, it is 2,(The reason is that the current ptr is being pointed by the Node(2) and Node(5), so the deconstructor of the Node will not be implemented. This is how things work.

How to tackle it ——>weak_pointer

All we need to do is to hand set the type pf parent_ptr as weak_ptr

#include <iostream>
#include <memory>

class Node {
    int value;
public:
    std::shared_ptr<Node> left_ptr;
    std::shared_ptr<Node> right_ptr;
    std::weak_ptr<Node> parent_ptr;
    Node(int val) : value(val) {
        std::cout<<"Contructor"<<std::endl;
    }
    ~Node() {
        std::cout<<"Destructor"<<std::endl;
    }
};

int main () {
    std::shared_ptr<Node> ptr = std::make_shared<Node>(4);
    ptr->left_ptr = std::make_shared<Node>(2);
    ptr->left_ptr->parent_ptr = ptr;
    ptr->right_ptr = std::make_shared<Node>(5);
    ptr->right_ptr->parent_ptr = ptr;

    std::cout<<"ptr reference count = "<<ptr.use_count()<<std::endl;
    std::cout<<"ptr->leftPtr reference count = "<<ptr->left_ptr.use_count()<<std::endl;
    std::cout<<"ptr->rightPtr reference count = "<<ptr->right_ptr.use_count()<<std::endl;
    std::cout<<"ptr->rightPtr->parentPtr reference count = "<<ptr->right_ptr->parent_ptr.lock().use_count()<<std::endl;
    std::cout<<"ptr->leftPtr->parentPtr reference count = "<<ptr->left_ptr->parent_ptr.lock().use_count()<<std::endl;
    return 0;
}