Using unique_ptr instead of shared_ptr in BST

binary-search-tree, c++, c++11, shared-ptr, unique-ptr

Solution

`unique_ptr`s are not assignable but moveable. I reworked your example and now works with `unique_ptr`s. Notice, that I use `std::move` in order to move contents from one `unique_ptr` to another. Also due to the fact that `unique_ptr` isn't copyable, I pass `unique_ptr`s in member functions by reference and not by value:

#include <iostream>
#include <memory>

template<class T>
class BinarySearchTree{
    struct TreeNode;
    typedef std::unique_ptr<TreeNode> spTreeNode;
    struct TreeNode{
        T data;
        spTreeNode  left;
        spTreeNode  right;
        TreeNode(const T & value):data(value),left(nullptr),right(nullptr){}
    };



    spTreeNode root;
    bool insert(spTreeNode &node);
    void print(const spTreeNode&) const ;
public:
    BinarySearchTree();
    void insert( const T & node);
    void print()const;
};

template<class T>
BinarySearchTree<T>::BinarySearchTree():root(nullptr){}

template<class T>
void BinarySearchTree<T>::insert(const T & ref)
{
    std::unique_ptr<TreeNode> node(new TreeNode(ref));
    if (root == nullptr) {
        root = std::move(node);
    } else {
        TreeNode* temp = root.get();
        TreeNode* prev = root.get();
        while (temp != nullptr) {
            prev = temp;
            if (temp->data < ref)
                temp = temp->right.get();
            else
                temp = temp->left.get();
        }
        if (prev->data < ref)
            prev->right = std::move(node);
        else
            prev->left = std::move(node);
    }
}

template<class T>
void BinarySearchTree<T>::print()const
{
    print(root);
}

template<class T>
void BinarySearchTree<T>::print(const std::unique_ptr<TreeNode> &node) const
{
    if(node == nullptr) return;
    print(node->left);
    std::cout << node->data<< std::endl;
    print(node->right);
}

int main()
{
    BinarySearchTree<int> bst;
    bst.insert(13);
    bst.insert(3);
    bst.insert(5);
    bst.insert(31);
    bst.print();
    return 0;
}

LIVE DEMO

Problem

I am trying to implement BST with `unique_ptr`. I got a working program for `shared_ptr`. How do I go about using unique_ptr instead to enforce the single ownership semantics of the BinarySearchTree? When I replace `shared_ptr` with `unique_ptr`, I get compilation errors beyond my understanding. ``` #include <iostream> #include <memory> template<class T> class BinarySearchTree{ struct TreeNode; typedef std::shared_ptr<TreeNode> spTreeNode; struct TreeNode{ T data; spTreeNode left; spTreeNode right; TreeNode(const T & value):data(value),left(nullptr),right(nullptr){} }; spTreeNode root; bool insert(spTreeNode node); void print(const spTreeNode) const ; public: BinarySearchTree(); void insert( const T & node); void print()const; }; template<class T> BinarySearchTree<T>::BinarySearchTree():root(nullptr){} template<class T> void BinarySearchTree<T>::insert(const T & ref) { TreeNode *node = new TreeNode(ref); if (root==nullptr) { root.reset(node); } else { spTreeNode temp = root; spTreeNode prev = root; while (temp) { prev = temp; if (temp->data < ref) temp = temp->right; else temp = temp->left; } if (prev->data < ref) prev->right.reset(node); else prev->left.reset(node); } } template<class T> void BinarySearchTree<T>::print()const { print(root); } template<class T> void BinarySearchTree<T>::print(const spTreeNode node)const { if (node==nullptr) return; print(node->left); std::cout << node->data<< std::endl; print(node->right); } int main() { BinarySearchTree<int> bst; bst.insert(13); bst.insert(3); bst.insert(5); bst.insert(31); bst.print(); return 0; } ``` EDIT: Compilation errors in case anyone is interested. Warning: Wall of text. ``` prog.cpp: In instantiation of ‘void BinarySearchTree<T>::insert(const T&) [with T = int]’: prog.cpp:75:18: required from here prog.cpp:39:27: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’ spTreeNode temp = root; ^ In file included from /usr/include/c++/4.8/memory:81:0, from prog.cpp:2: /usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here unique_ptr(const unique_ptr&) = delete; ^ prog.cpp:40:27: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’ spTreeNode prev = root; ^ In file included from /usr/include/c++/4.8/memory:81:0, from prog.cpp:2: /usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here unique_ptr(const unique_ptr&) = delete; ^ prog.cpp:43:18: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>& std::unique_ptr<_Tp, _Dp>::operator=(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’ prev = temp; ^ In file included from /usr/include/c++/4.8/memory:81:0, from prog.cpp:2: /usr/include/c++/4.8/bits/unique_ptr.h:274:19: error: declared here unique_ptr& operator=(const unique_ptr&) = delete; ^ prog.cpp:45:22: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>& std::unique_ptr<_Tp, _Dp>::operator=(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’ temp = temp->right; ^ In file included from /usr/include/c++/4.8/memory:81:0, from prog.cpp:2: /usr/include/c++/4.8/bits/unique_ptr.h:274:19: error: declared here unique_ptr& operator=(const unique_ptr&) = delete; ^ prog.cpp:47:22: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>& std::unique_ptr<_Tp, _Dp>::operator=(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’ temp = temp->left; ^ In file included from /usr/include/c++/4.8/memory:81:0, from prog.cpp:2: /usr/include/c++/4.8/bits/unique_ptr.h:274:19: error: declared here unique_ptr& operator=(const unique_ptr&) = delete; ^ prog.cpp: In instantiation of ‘void BinarySearchTree<T>::print() const [with T = int]’: prog.cpp:79:15: required from here prog.cpp:59:15: error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = BinarySearchTree<int>::TreeNode; _Dp = std::default_delete<BinarySearchTree<int>::TreeNode>]’ print(root); ^ In file included from /usr/include/c++/4.8/memory:81:0, from prog.cpp:2: /usr/include/c++/4.8/bits/unique_ptr.h:273:7: error: declared here unique_ptr(const unique_ptr&) = delete; ^ prog.cpp:63:6: error: initializing argument 1 of ‘void BinarySearchTree<T>::print(BinarySearchTree<T>::spTreeNode) const [with T = int; BinarySearchTree<T>::spTreeNode = std::unique_ptr<BinarySearchTree<int>::TreeNode, std::default_delete<BinarySearchTree<int>::TreeNode> >]’ void BinarySearchTree<T>::print(const spTreeNode node)const ^ ```

Original source