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.
Re: I'm trying to build a binary tree with boost::shared_ptr
Quote:
Originally Posted by
whitehat1
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.
Re: I'm trying to build a binary tree with boost::shared_ptr
Quote:
Originally Posted by
nuzzle
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
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.
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 (:
Re: I'm trying to build a binary tree with boost::shared_ptr
Re: I'm trying to build a binary tree with boost::shared_ptr
Quote:
Originally Posted by
monarch_dodra
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.
Re: I'm trying to build a binary tree with boost::shared_ptr
Quote:
Originally Posted by
nuzzle
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...
