CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Jun 2012
    Posts
    3

    I'm trying to build a binary tree with boost::shared_ptr

    Hello,

    I'm trying this to get the hang of boost::shared_prt and weak_ptr so far I have the following

    Code:
    #include <iostream>
    #include <string>
    #include <boost/thread.hpp>
    #include <boost/lambda/bind.hpp>
    #include <stack>
    #include <queue>
    #include <boost/shared_ptr.hpp>
    #include <boost/weak_ptr.hpp>
    
    
    
    using namespace std;
    #define Yes 1
    #define No 0
    
    class Node
    {
    public:
        boost::shared_ptr<Node> left;
        boost::shared_ptr<Node> rigth;
        int nVal;
        Node();
        Node(int);
        ~Node();
        int getVal(void);
        void setVal(int);
                
    };
    
    Node::Node()
    {
        cout << "creating node empty" << endl;
        nVal = 0;
        left.reset();
        rigth.reset();
        
    }
    
    Node::~Node()
    {
        cout << "entering destructor"  << nVal << endl;
    }
    
    Node::Node(int n)
    {
        cout << "creating node with value" << n << endl;
        nVal = n;
        left.reset();
        rigth.reset();
    }
    
    int Node::getVal(void)
    {
        cout << "returning value" << endl;
        return this->nVal;
    }
    
    void Node::setVal(int n)
    {
        cout << "setting value" << endl;
        nVal = n;
    }
    
    class Tree 
    {
    public:
        boost::shared_ptr<Node> root;
        Tree();
        ~Tree();
        void findParent(int n, int &found, boost::shared_ptr<Node> &parent);
        void add(int n);
        void post(boost::weak_ptr<Node> q);
        void del(int n);
        
    };
    
    Tree::Tree()
    {
       cout << "creating a tree" << endl;
       root.reset();
    }
    
    Tree::~Tree()
    {
        root.reset();
        cout << "deleting a tree" << endl;
        
    }
    
    void Tree::findParent(int n, int& found, boost::shared_ptr<Node>& parent)
    {
        boost::shared_ptr<Node> q;
        q = parent;
        while(!q)
        {
            if(q)
            {
                cout << "we hit a root" << endl;
                return;
            }
            if(q->nVal < n)
            {
                parent = q;
                q = q->left
            }
        }
    }
    
    class Triplet
    {
    public:
        boost::weak_ptr<Node> ptrNode1;
    };
    
    
    int THREADS_HOW_MANY = 0;
    
    int main()
    {
        Tree bt;
        bt.add(10);
        bt.add(4);
        bt.add(12);
        bt.add(2);
        bt.add(8);
        bt.add(15);
        bt.add(15);
       
        
      
        return 0;
    }
    My questions are, is the tree class defined correctly? How do I find the parent of a given node? And how does the insert part will work? Thanks.

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: I'm trying to build a binary tree with boost::shared_ptr

    Quote Originally Posted by whitehat1 View Post
    My questions are, is the tree class defined correctly? How do I find the parent of a given node? And how does the insert part will work? Thanks.
    Conceptually you implement the binary tree exactly as you would without shared_ptr and then just replace all pointer occurances with shared_ptr and remove all occurances of delete. That's it.

    Easiest is to define a shared_ptr type like,

    typedef boost::shared_ptr<Node> Node_PTR;

    or if you use C++ 11,

    typedef std::shared_ptr<Node> Node_PTR;

    Then just replace all Node* with Node_PTR and remove all deletes of Node* pointers.

    So it's business as usual with one exception, you cannot use Node_PTR circularly. It means you cannot have parent pointers in a tree because they point back to where they're pointed from forming circles. For that you need to a introduce a weak_ptr.

    Personally I solve this drawback by simply not using shared_ptr where circular pointing is absolutely unavoidable. It's mostly the case in very low-level algorithmic style code where shared_ptr introduces an unwanted level of indirection anyway. So in practice it's never a drawback to refrain from shared_ptr in that kind of code. At least I've never felt it was.
    Last edited by nuzzle; June 27th, 2012 at 05:24 AM.

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: I'm trying to build a binary tree with boost::shared_ptr

    Quote Originally Posted by nuzzle View Post
    So it's business as usual with one exception, you cannot use Node_PTR circularly. It means you cannot have parent pointers in a tree because they point back to where they're pointed from forming circles. For that you need to a introduce a weak_ptr.
    That is very true: Circular reference is the bane of any reference counted model. That said, weak_ptr is really only needed if there is a chance that the pointed object may go out of scope before the current object. In this case, it would mean that a parent node would be destroyed before a child node (!). This means that a plain old pointer to a parent will do just fine.

    Quote Originally Posted by nuzzle View Post
    Personally I solve this drawback by simply not using shared_ptr where circular pointing is absolutely unavoidable. It's mostly the case in very low-level algorithmic style code where shared_ptr introduces an unwanted level of indirection anyway. So in practice it's never a drawback to refrain from shared_ptr in that kind of code. At least I've never felt it was.
    Technically, shared_ptr doesn't add an extra level of indirection, as it stores both a pointer to data, and a pointer to the reference counter. The reference counter is only accessed on assignment/destruction. At least, that's the way it is implemented by GCC/boost, last time I checked. The reference counter also contains a redundant pointer to data, but that one is only used as a hook for weak_ptr.

    I do agree that shared_ptr does not add much though. That said, there is nothing wrong with using some of the other smart pointers, in particular, unique_ptr (or its locked-in-the-basement little brother, auto_ptr). This only brings compile time complexity.

    In the OP's tree model, I think having nodes pointing to children nodes with unique_ptr rather than shared_ptr would be a very good design choice.
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

  4. #4
    Join Date
    Jun 2012
    Posts
    3

    Re: I'm trying to build a binary tree with boost::shared_ptr

    Code:
    #include <iostream>
    #include <string>
    #include <boost/thread.hpp>
    #include <boost/lambda/bind.hpp>
    #include <stack>
    #include <queue>
    #include <boost/shared_ptr.hpp>
    #include <boost/weak_ptr.hpp>
    
    
    
    using namespace std;
    #define Yes 1
    #define No 0
    
    class Node
    {
    public:
      int key_value;
      boost::shared_ptr<Node> left;
      boost::shared_ptr<Node> right;
      Node();
      Node(int key_value);
      ~Node();
      int getVal(void);
      void setVal(int key_value);
    };
    
    Node::Node()
    {
        cout << "creating node" << endl;
        left.reset();
        right.reset();
        
    }
    
    Node::Node(int key_value)
    {
        this->key_value = key_value;
        
    }
    
    Node::~Node()
    {
        cout << "entering the destructor of node" << endl;
        
    }
    
    int Node::getVal()
    {
        cout << "getting value" << endl;
        return this->key_value;
    }
    
    
    void Node::setVal(int key_value)
    {
        cout << "setting key " << endl;
        this->key_value = key_value;
    }
    
    class Btree
    {
        public:
            Btree();
            ~Btree();
    
            void insert(int key);
            boost::shared_ptr<Node> search(int key);
            void destroy_tree();
    
        private:
            void destroy_tree(boost::shared_ptr<Node> leaf);
            void insert(int key, boost::shared_ptr<Node> leaf);
             boost::shared_ptr<Node> search(int key, boost::shared_ptr<Node> leaf);
            
            boost::shared_ptr<Node> root;
    };
    
    Btree::Btree()
    {
        cout << "creating root" << endl;
        boost::shared_ptr<Node> root(new Node());
    }
    
    Btree::~Btree()
    {
        cout << "deleting root" << endl;
        root.reset();
    }
    
    void Btree::insert(int key, boost::shared_ptr<Node> leaf)
    {
      if(key< leaf->key_value)
      {
        if(!leaf->left)
         insert(key, leaf->left);
        else
        {
         leaf->right= boost::shared_ptr<Node>(new Node());
          leaf->left->key_value=key;
          leaf->left->left.reset();    //Sets the left child of the child node to null
          leaf->left->right.reset();  //Sets the right child of the child node to null
        }  
      }
      else if(key>=leaf->key_value)
      {
        if(!leaf->right)
          insert(key, leaf->right);
        else
        {
          leaf->right= boost::shared_ptr<Node>(new Node());
          leaf->right->key_value=key;
          leaf->right->left.reset();  //Sets the left child of the child node to null
          leaf->right->right.reset(); //Sets the right child of the child node to null
        }
      }
    }
    
    void Btree::insert(int key)
    {
          if(!root)
        insert(key, root);
      else
      {
       root = boost::shared_ptr<Node>(new Node());
        root->key_value=key;
        root->left.reset();
        root->right.reset();
      }
    }
    
    boost::shared_ptr<Node> Btree::search(int key, boost::shared_ptr<Node> leaf)
    {
      if(!leaf)
      {
        if(key==leaf->key_value)
        {
            cout << "value is equal" << endl;
          return leaf;
         
        }
          if(key<leaf->key_value)
          {
              cout << "less value looking again" << endl;
              return search(key, leaf->left);
    
          }
          else
          {
              cout << "looking for more value" << endl;
              return search(key, leaf->right);
          }
          }
      else return root;
    }
    
    boost::shared_ptr<Node> Btree::search(int key)
    {
        cout << "search public" << endl;
      return search(key, root);
    }
    
    void Btree::destroy_tree()
    {
        cout << "destroying tree" << endl;
       destroy_tree(root);
    }
    
    void Btree::destroy_tree(boost::shared_ptr<Node> leaf)
    {
      if(!leaf)
      {
        destroy_tree(leaf->left);
        destroy_tree(leaf->right);
       
      }
      leaf.reset();
    }
    
    int main(int argc, char *argv[])
    {
        Btree bt;
        bt.insert(10);
        bt.insert(4);
        bt.insert(2);
        
        return 0;
    I have done this and is giving me this error
    Code:
    creating root
    creating node
    entering the destructor of node
    threads: /usr/include/boost/smart_ptr/shared_ptr.hpp:418: T* boost::shared_ptr< <template-parameter-1-1> >::operator->() const [with T = Node]: Assertion `px != 0' failed.
    
    RUN FAILED (exit value 1, total time: 67ms)
    why?? updated (:
    Last edited by whitehat1; June 27th, 2012 at 08:00 AM.

  5. #5
    Join Date
    Jun 2012
    Posts
    3

    Re: I'm trying to build a binary tree with boost::shared_ptr

    (:
    Last edited by whitehat1; June 27th, 2012 at 07:53 AM.

  6. #6
    Join Date
    May 2009
    Posts
    2,413

    Re: I'm trying to build a binary tree with boost::shared_ptr

    Quote Originally Posted by monarch_dodra View Post
    I do agree that shared_ptr does not add much though.
    Well, I never said that. I use shared_ptr and intrusive_ptr extensively. (My latest program is designed so I can easily switch between them at compile time. It's a little project I have in order to finally decide which one performs better in a real application.)

    I'm even more fond of smart pointers now after I learned that they preferrably should be passed by const reference thus avoiding much of the problem with extensive reference counting. And the circular reference problem can almost always be designed away except sometimes in low-level algorithmic style code where I then resort to ordinary pointers and manual memory management.

    But I realize my strong liking for smart pointers is because of my Java influenced OO programming style. More traditional C++ programmers probably won't create heap objects as freely as I do and thus won't benefit as much from smart pointers as I do.

  7. #7
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    Re: I'm trying to build a binary tree with boost::shared_ptr

    Quote Originally Posted by nuzzle View Post
    Well, I never said that.
    I meant in the context of "very low-level algorithmic style code". shared_ptr is of course a very useful thing. Sorry for putting words in your mouth though.

    Being a "traditional" C++ developer myself, I have become a huge fan of unique_ptr: You get to place stuff on the heap, but scope it on the stack. Yummy.



    ----
    To the OP: This is the perfect time to learn how to use your debugger...
    Is your question related to IO?
    Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
    It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured