Mixing
Binary Search Tree implementation using smart pointers
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}
$begingroup$
I have implemented below code for binary search tree implementation using shared pointer. At present, I have considered only integers. It supports insertion and deletion of values. Also, a print method is implemented for inorder traversal.
Please review and provide your suggestions.
class Bst {
struct node {
int val;
shared_ptr<node> left, right;
node(int v) : val(v), left(nullptr), right(nullptr){}
};
shared_ptr<node> root;
shared_ptr<node> _insert(shared_ptr<node> curr, int val);
shared_ptr<node> _del(shared_ptr<node> curr, int val);
shared_ptr<node> findmin(shared_ptr<node> curr);
void _print(shared_ptr<node> curr);
public:
void insert(int val) { root = _insert(root, val); }
void del(int val) { root = _del(root, val); }
void print() { _print(root); cout << 'n'; }
};
shared_ptr<Bst::node> Bst::_insert(shared_ptr<node> curr, int val)
{
if (curr == nullptr)
return make_shared<node>(val);
if (val < curr->val)
curr->left = _insert(curr->left, val);
else
curr->right = _insert(curr->right, val);
return curr;
}
shared_ptr<Bst::node> Bst::findmin(shared_ptr<node> curr)
{
while (curr->left)
curr = curr->left;
return curr;
}
shared_ptr<Bst::node> Bst::_del(shared_ptr<node> curr, int val)
{
if (val < curr->val)
curr->left = _del(curr->left, val);
else if (val > curr->val)
curr->right = _del(curr->right, val);
else {
if (curr->right == nullptr)
return curr->left;
if (curr->left == nullptr)
return curr->right;
shared_ptr<node> temp = findmin(curr->right);
curr->val = temp->val;
curr->right = _del(curr->right, curr->val);
}
return curr;
}
void Bst::_print(shared_ptr<node> curr)
{
if (curr == nullptr)
return;
_print(curr->left);
cout << curr->val << " ";
_print(curr->right);
}
c++ object-oriented c++11 design-patterns pointers
asked Feb 1 at 14:26
bornfreebornfree
1643
$endgroup$
add a comment |
$begingroup$
I have implemented below code for binary search tree implementation using shared pointer. At present, I have considered only integers. It supports insertion and deletion of values. Also, a print method is implemented for inorder traversal.
Please review and provide your suggestions.
class Bst {
struct node {
int val;
shared_ptr<node> left, right;
node(int v) : val(v), left(nullptr), right(nullptr){}
};
shared_ptr<node> root;
shared_ptr<node> _insert(shared_ptr<node> curr, int val);
shared_ptr<node> _del(shared_ptr<node> curr, int val);
shared_ptr<node> findmin(shared_ptr<node> curr);
void _print(shared_ptr<node> curr);
public:
void insert(int val) { root = _insert(root, val); }
void del(int val) { root = _del(root, val); }
void print() { _print(root); cout << 'n'; }
};
shared_ptr<Bst::node> Bst::_insert(shared_ptr<node> curr, int val)
{
if (curr == nullptr)
return make_shared<node>(val);
if (val < curr->val)
curr->left = _insert(curr->left, val);
else
curr->right = _insert(curr->right, val);
return curr;
}
shared_ptr<Bst::node> Bst::findmin(shared_ptr<node> curr)
{
while (curr->left)
curr = curr->left;
return curr;
}
shared_ptr<Bst::node> Bst::_del(shared_ptr<node> curr, int val)
{
if (val < curr->val)
curr->left = _del(curr->left, val);
else if (val > curr->val)
curr->right = _del(curr->right, val);
else {
if (curr->right == nullptr)
return curr->left;
if (curr->left == nullptr)
return curr->right;
shared_ptr<node> temp = findmin(curr->right);
curr->val = temp->val;
curr->right = _del(curr->right, curr->val);
}
return curr;
}
void Bst::_print(shared_ptr<node> curr)
{
if (curr == nullptr)
return;
_print(curr->left);
cout << curr->val << " ";
_print(curr->right);
}
c++ object-oriented c++11 design-patterns pointers
asked Feb 1 at 14:26
bornfreebornfree
1643
$endgroup$
add a comment |
$begingroup$
I have implemented below code for binary search tree implementation using shared pointer. At present, I have considered only integers. It supports insertion and deletion of values. Also, a print method is implemented for inorder traversal.
Please review and provide your suggestions.
class Bst {
struct node {
int val;
shared_ptr<node> left, right;
node(int v) : val(v), left(nullptr), right(nullptr){}
};
shared_ptr<node> root;
shared_ptr<node> _insert(shared_ptr<node> curr, int val);
shared_ptr<node> _del(shared_ptr<node> curr, int val);
shared_ptr<node> findmin(shared_ptr<node> curr);
void _print(shared_ptr<node> curr);
public:
void insert(int val) { root = _insert(root, val); }
void del(int val) { root = _del(root, val); }
void print() { _print(root); cout << 'n'; }
};
shared_ptr<Bst::node> Bst::_insert(shared_ptr<node> curr, int val)
{
if (curr == nullptr)
return make_shared<node>(val);
if (val < curr->val)
curr->left = _insert(curr->left, val);
else
curr->right = _insert(curr->right, val);
return curr;
}
shared_ptr<Bst::node> Bst::findmin(shared_ptr<node> curr)
{
while (curr->left)
curr = curr->left;
return curr;
}
shared_ptr<Bst::node> Bst::_del(shared_ptr<node> curr, int val)
{
if (val < curr->val)
curr->left = _del(curr->left, val);
else if (val > curr->val)
curr->right = _del(curr->right, val);
else {
if (curr->right == nullptr)
return curr->left;
if (curr->left == nullptr)
return curr->right;
shared_ptr<node> temp = findmin(curr->right);
curr->val = temp->val;
curr->right = _del(curr->right, curr->val);
}
return curr;
}
void Bst::_print(shared_ptr<node> curr)
{
if (curr == nullptr)
return;
_print(curr->left);
cout << curr->val << " ";
_print(curr->right);
}
c++ object-oriented c++11 design-patterns pointers
asked Feb 1 at 14:26
bornfreebornfree
1643
$endgroup$
I have implemented below code for binary search tree implementation using shared pointer. At present, I have considered only integers. It supports insertion and deletion of values. Also, a print method is implemented for inorder traversal.
Please review and provide your suggestions.
class Bst {
struct node {
int val;
shared_ptr<node> left, right;
node(int v) : val(v), left(nullptr), right(nullptr){}
};
shared_ptr<node> root;
shared_ptr<node> _insert(shared_ptr<node> curr, int val);
shared_ptr<node> _del(shared_ptr<node> curr, int val);
shared_ptr<node> findmin(shared_ptr<node> curr);
void _print(shared_ptr<node> curr);
public:
void insert(int val) { root = _insert(root, val); }
void del(int val) { root = _del(root, val); }
void print() { _print(root); cout << 'n'; }
};
shared_ptr<Bst::node> Bst::_insert(shared_ptr<node> curr, int val)
{
if (curr == nullptr)
return make_shared<node>(val);
if (val < curr->val)
curr->left = _insert(curr->left, val);
else
curr->right = _insert(curr->right, val);
return curr;
}
shared_ptr<Bst::node> Bst::findmin(shared_ptr<node> curr)
{
while (curr->left)
curr = curr->left;
return curr;
}
shared_ptr<Bst::node> Bst::_del(shared_ptr<node> curr, int val)
{
if (val < curr->val)
curr->left = _del(curr->left, val);
else if (val > curr->val)
curr->right = _del(curr->right, val);
else {
if (curr->right == nullptr)
return curr->left;
if (curr->left == nullptr)
return curr->right;
shared_ptr<node> temp = findmin(curr->right);
curr->val = temp->val;
curr->right = _del(curr->right, curr->val);
}
return curr;
}
void Bst::_print(shared_ptr<node> curr)
{
if (curr == nullptr)
return;
_print(curr->left);
cout << curr->val << " ";
_print(curr->right);
}
c++ object-oriented c++11 design-patterns pointers
c++ object-oriented c++11 design-patterns pointers
asked Feb 1 at 14:26
bornfreebornfree
1643
asked Feb 1 at 14:26
bornfreebornfree
1643
asked Feb 1 at 14:26
bornfreebornfree
1643
asked Feb 1 at 14:26
bornfreebornfree
1643
asked Feb 1 at 14:26
bornfreebornfree
1643
1643
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
- please do not
using namespace std;
- why has
Bst::findminno prefix_? - why do you use
std::shared_ptr<>at all?std::shared_ptris ment to represent shared ownership. This makes no sense for tree nodes, you're not going to have two trees with the same nodes.std::unique_ptr<>is a better candidate. - it is generally good to separate the data structure from its serialization. Make
printa separate function and also handle the member printing outside of the class.
Edit
As you had trouble getting the unique_ptr running, here's what works for me.
Modify the node to use unique_ptr:
struct node
{
int val;
std::unique_ptr<node> left;
std::unique_ptr<node> right;
// c'tor left out
};
Also, use a unique_ptr for root. You'll receive heavy compiler complaints,
because a unique_ptr cannot be simply copied (one of the instances must go invalid, as it's unique). I suggest altering the private functions:
void _insert(std::unique_ptr<node>& curr, int val);
void _del(std::unique_ptr<node>& curr, int val);
Sample implementation for _insert:
void Bst::_insert(std::unique_ptr<node>& curr, int val)
{
if (!curr)
{
curr = std::make_unique<node>(val);
return;
}
if (val < curr->val)
{
_insert(curr->left, val);
}
else
{
_insert(curr->right, val);
}
}
Your public insert method would be something like:
void insert(int val)
{
_insert(root, val);
}
Also: add a find function to see if an element is in the tree. Use the find function to write some simple tests. You may rename del to erase to be closer at the standard naming.
Edit 2 Separate output from data storage:
A friend function is relatively inflexible, as you cannot easily exchange the printing algorithm. You may implement iterators (hard) or provide a traverse function. I'd go for the second approach, as you already have the algorithm in _print: rename print to traverse and pass it a function pointer, then replace the output to std::cout by a call to the function pointer.
class Bst
{
...
// traverse with function pointer
void traverse(void (*func)(int));
};
int main()
{
Bst b;
// insert data ...
b.traverse((auto v){ std::cout << v << " "; });
std::cout << "n";
}
answered Feb 1 at 14:46
CornholioCornholio
53117
$endgroup$
$begingroup$
I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
$endgroup$
– bornfree
Feb 1 at 17:24
$begingroup$
You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers ascinorshared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.
$endgroup$
– Cornholio
Feb 1 at 17:33
$begingroup$
Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?
$endgroup$
– bornfree
Feb 2 at 6:32
add a comment |
$begingroup$
- Separate your class declaration and definition into separate
Bst.handBst.cppfiles - For
Bst.hprovide header guards
- initialize
shared_ptr<node>member,rootwithnullptr
answered Feb 1 at 16:09
programmerprogrammer
513
$endgroup$
2
$begingroup$
I thought root will be initialized to nullptr by default ?
$endgroup$
– bornfree
Feb 1 at 17:30
add a comment |
$begingroup$
You forgot to include any of the headers that your code depends on; copy/paste of this into https://godbolt.org/ gives lots of errors until I add #include <memory> and iostream, and some using declarations (https://godbolt.org/z/cE0GDR). So the code in the question is incomplete.
More importantly, for shared_ptr to be thread-safe, it has to use atomic-increment / decrement instructions, and check if the ref-count has become 0 after it's done referencing a node. This makes it significantly more expensive than I think you want. As another answer suggests, std::unique_ptr<> is probably a better choice.
So for example, your findmin() source looks really simple, just traversing down to the left-most leaf node, but because you're using shared_ptr it compiles (on x86-64) to lock add and lock xadd instructions, potentially calling the destructor to free the node.
(gcc emits checks before actually doing the atomic ++ / -- ref counting. It checks the address of a weak alias for __pthread_key_create. I think this might just be checking if the program could possibly be multi-threaded, i.e. linked with the thread library, rather than if multiple threads are currently running. So some of the cost of shared_ptr might go away in some single-threaded programs.)
If you're looking at the asm on the Godbolt compiler explorer, search for the lock prefix for x86-64. Or for AArch64, look for ldaxr/stlxr LL/SC retry loops (load-acquire exclusive / store sequential-release exclusive).
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212692%2fbinary-search-tree-implementation-using-smart-pointers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
- please do not
using namespace std;
- why has
Bst::findminno prefix_? - why do you use
std::shared_ptr<>at all?std::shared_ptris ment to represent shared ownership. This makes no sense for tree nodes, you're not going to have two trees with the same nodes.std::unique_ptr<>is a better candidate. - it is generally good to separate the data structure from its serialization. Make
printa separate function and also handle the member printing outside of the class.
Edit
As you had trouble getting the unique_ptr running, here's what works for me.
Modify the node to use unique_ptr:
struct node
{
int val;
std::unique_ptr<node> left;
std::unique_ptr<node> right;
// c'tor left out
};
Also, use a unique_ptr for root. You'll receive heavy compiler complaints,
because a unique_ptr cannot be simply copied (one of the instances must go invalid, as it's unique). I suggest altering the private functions:
void _insert(std::unique_ptr<node>& curr, int val);
void _del(std::unique_ptr<node>& curr, int val);
Sample implementation for _insert:
void Bst::_insert(std::unique_ptr<node>& curr, int val)
{
if (!curr)
{
curr = std::make_unique<node>(val);
return;
}
if (val < curr->val)
{
_insert(curr->left, val);
}
else
{
_insert(curr->right, val);
}
}
Your public insert method would be something like:
void insert(int val)
{
_insert(root, val);
}
Also: add a find function to see if an element is in the tree. Use the find function to write some simple tests. You may rename del to erase to be closer at the standard naming.
Edit 2 Separate output from data storage:
A friend function is relatively inflexible, as you cannot easily exchange the printing algorithm. You may implement iterators (hard) or provide a traverse function. I'd go for the second approach, as you already have the algorithm in _print: rename print to traverse and pass it a function pointer, then replace the output to std::cout by a call to the function pointer.
class Bst
{
...
// traverse with function pointer
void traverse(void (*func)(int));
};
int main()
{
Bst b;
// insert data ...
b.traverse((auto v){ std::cout << v << " "; });
std::cout << "n";
}
answered Feb 1 at 14:46
CornholioCornholio
53117
$endgroup$
$begingroup$
I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
$endgroup$
– bornfree
Feb 1 at 17:24
$begingroup$
You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers ascinorshared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.
$endgroup$
– Cornholio
Feb 1 at 17:33
$begingroup$
Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?
$endgroup$
– bornfree
Feb 2 at 6:32
add a comment |
$begingroup$
- please do not
using namespace std;
- why has
Bst::findminno prefix_? - why do you use
std::shared_ptr<>at all?std::shared_ptris ment to represent shared ownership. This makes no sense for tree nodes, you're not going to have two trees with the same nodes.std::unique_ptr<>is a better candidate. - it is generally good to separate the data structure from its serialization. Make
printa separate function and also handle the member printing outside of the class.
Edit
As you had trouble getting the unique_ptr running, here's what works for me.
Modify the node to use unique_ptr:
struct node
{
int val;
std::unique_ptr<node> left;
std::unique_ptr<node> right;
// c'tor left out
};
Also, use a unique_ptr for root. You'll receive heavy compiler complaints,
because a unique_ptr cannot be simply copied (one of the instances must go invalid, as it's unique). I suggest altering the private functions:
void _insert(std::unique_ptr<node>& curr, int val);
void _del(std::unique_ptr<node>& curr, int val);
Sample implementation for _insert:
void Bst::_insert(std::unique_ptr<node>& curr, int val)
{
if (!curr)
{
curr = std::make_unique<node>(val);
return;
}
if (val < curr->val)
{
_insert(curr->left, val);
}
else
{
_insert(curr->right, val);
}
}
Your public insert method would be something like:
void insert(int val)
{
_insert(root, val);
}
Also: add a find function to see if an element is in the tree. Use the find function to write some simple tests. You may rename del to erase to be closer at the standard naming.
Edit 2 Separate output from data storage:
A friend function is relatively inflexible, as you cannot easily exchange the printing algorithm. You may implement iterators (hard) or provide a traverse function. I'd go for the second approach, as you already have the algorithm in _print: rename print to traverse and pass it a function pointer, then replace the output to std::cout by a call to the function pointer.
class Bst
{
...
// traverse with function pointer
void traverse(void (*func)(int));
};
int main()
{
Bst b;
// insert data ...
b.traverse((auto v){ std::cout << v << " "; });
std::cout << "n";
}
answered Feb 1 at 14:46
CornholioCornholio
53117
$endgroup$
$begingroup$
I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
$endgroup$
– bornfree
Feb 1 at 17:24
$begingroup$
You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers ascinorshared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.
$endgroup$
– Cornholio
Feb 1 at 17:33
$begingroup$
Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?
$endgroup$
– bornfree
Feb 2 at 6:32
add a comment |
$begingroup$
- please do not
using namespace std;
- why has
Bst::findminno prefix_? - why do you use
std::shared_ptr<>at all?std::shared_ptris ment to represent shared ownership. This makes no sense for tree nodes, you're not going to have two trees with the same nodes.std::unique_ptr<>is a better candidate. - it is generally good to separate the data structure from its serialization. Make
printa separate function and also handle the member printing outside of the class.
Edit
As you had trouble getting the unique_ptr running, here's what works for me.
Modify the node to use unique_ptr:
struct node
{
int val;
std::unique_ptr<node> left;
std::unique_ptr<node> right;
// c'tor left out
};
Also, use a unique_ptr for root. You'll receive heavy compiler complaints,
because a unique_ptr cannot be simply copied (one of the instances must go invalid, as it's unique). I suggest altering the private functions:
void _insert(std::unique_ptr<node>& curr, int val);
void _del(std::unique_ptr<node>& curr, int val);
Sample implementation for _insert:
void Bst::_insert(std::unique_ptr<node>& curr, int val)
{
if (!curr)
{
curr = std::make_unique<node>(val);
return;
}
if (val < curr->val)
{
_insert(curr->left, val);
}
else
{
_insert(curr->right, val);
}
}
Your public insert method would be something like:
void insert(int val)
{
_insert(root, val);
}
Also: add a find function to see if an element is in the tree. Use the find function to write some simple tests. You may rename del to erase to be closer at the standard naming.
Edit 2 Separate output from data storage:
A friend function is relatively inflexible, as you cannot easily exchange the printing algorithm. You may implement iterators (hard) or provide a traverse function. I'd go for the second approach, as you already have the algorithm in _print: rename print to traverse and pass it a function pointer, then replace the output to std::cout by a call to the function pointer.
class Bst
{
...
// traverse with function pointer
void traverse(void (*func)(int));
};
int main()
{
Bst b;
// insert data ...
b.traverse((auto v){ std::cout << v << " "; });
std::cout << "n";
}
answered Feb 1 at 14:46
CornholioCornholio
53117
$endgroup$
- please do not
using namespace std;
- why has
Bst::findminno prefix_? - why do you use
std::shared_ptr<>at all?std::shared_ptris ment to represent shared ownership. This makes no sense for tree nodes, you're not going to have two trees with the same nodes.std::unique_ptr<>is a better candidate. - it is generally good to separate the data structure from its serialization. Make
printa separate function and also handle the member printing outside of the class.
Edit
As you had trouble getting the unique_ptr running, here's what works for me.
Modify the node to use unique_ptr:
struct node
{
int val;
std::unique_ptr<node> left;
std::unique_ptr<node> right;
// c'tor left out
};
Also, use a unique_ptr for root. You'll receive heavy compiler complaints,
because a unique_ptr cannot be simply copied (one of the instances must go invalid, as it's unique). I suggest altering the private functions:
void _insert(std::unique_ptr<node>& curr, int val);
void _del(std::unique_ptr<node>& curr, int val);
Sample implementation for _insert:
void Bst::_insert(std::unique_ptr<node>& curr, int val)
{
if (!curr)
{
curr = std::make_unique<node>(val);
return;
}
if (val < curr->val)
{
_insert(curr->left, val);
}
else
{
_insert(curr->right, val);
}
}
Your public insert method would be something like:
void insert(int val)
{
_insert(root, val);
}
Also: add a find function to see if an element is in the tree. Use the find function to write some simple tests. You may rename del to erase to be closer at the standard naming.
Edit 2 Separate output from data storage:
A friend function is relatively inflexible, as you cannot easily exchange the printing algorithm. You may implement iterators (hard) or provide a traverse function. I'd go for the second approach, as you already have the algorithm in _print: rename print to traverse and pass it a function pointer, then replace the output to std::cout by a call to the function pointer.
class Bst
{
...
// traverse with function pointer
void traverse(void (*func)(int));
};
int main()
{
Bst b;
// insert data ...
b.traverse((auto v){ std::cout << v << " "; });
std::cout << "n";
}
answered Feb 1 at 14:46
CornholioCornholio
53117
edited Feb 2 at 10:06
answered Feb 1 at 14:46
CornholioCornholio
53117
answered Feb 1 at 14:46
CornholioCornholio
53117
answered Feb 1 at 14:46
CornholioCornholio
53117
53117
$begingroup$
I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
$endgroup$
– bornfree
Feb 1 at 17:24
$begingroup$
You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers ascinorshared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.
$endgroup$
– Cornholio
Feb 1 at 17:33
$begingroup$
Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?
$endgroup$
– bornfree
Feb 2 at 6:32
add a comment |
$begingroup$
I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
$endgroup$
– bornfree
Feb 1 at 17:24
$begingroup$
You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers ascinorshared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.
$endgroup$
– Cornholio
Feb 1 at 17:33
$begingroup$
Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?
$endgroup$
– bornfree
Feb 2 at 6:32
$begingroup$
I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
$endgroup$
– bornfree
Feb 1 at 17:24
$begingroup$
I am doing "using std::cin"(similarly for others) and not "using namespace std". Is it ok ? Also, I thought of using unique_ptr but in that case how do i pass arguments in recursion as it is not allowed for unqiue_ptr ?
$endgroup$
– bornfree
Feb 1 at 17:24
$begingroup$
You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers as
cin or shared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.$endgroup$
– Cornholio
Feb 1 at 17:33
$begingroup$
You shouldn't do so in header files as you cannot tell if you/someone else wants to use identifiers as
cin or shared_ptr. In implementation files it's kind of ok, though I would strongly advice against doing. At best it looks funny. Everybody else will think it is something different than an STL template, so you're reducing the readability of your code.$endgroup$
– Cornholio
Feb 1 at 17:33
$begingroup$
Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?
$endgroup$
– bornfree
Feb 2 at 6:32
$begingroup$
Thanks for your valuable review. Regarding your fourth point of making print a separate function. Since, root is a private member of Bst class, I will have to create a friend function so that print can access the nodes ?
$endgroup$
– bornfree
Feb 2 at 6:32
add a comment |
$begingroup$
- Separate your class declaration and definition into separate
Bst.handBst.cppfiles - For
Bst.hprovide header guards
- initialize
shared_ptr<node>member,rootwithnullptr
answered Feb 1 at 16:09
programmerprogrammer
513
$endgroup$
2
$begingroup$
I thought root will be initialized to nullptr by default ?
$endgroup$
– bornfree
Feb 1 at 17:30
add a comment |
$begingroup$
- Separate your class declaration and definition into separate
Bst.handBst.cppfiles - For
Bst.hprovide header guards
- initialize
shared_ptr<node>member,rootwithnullptr
answered Feb 1 at 16:09
programmerprogrammer
513
$endgroup$
2
$begingroup$
I thought root will be initialized to nullptr by default ?
$endgroup$
– bornfree
Feb 1 at 17:30
add a comment |
$begingroup$
- Separate your class declaration and definition into separate
Bst.handBst.cppfiles - For
Bst.hprovide header guards
- initialize
shared_ptr<node>member,rootwithnullptr
answered Feb 1 at 16:09
programmerprogrammer
513
$endgroup$
- Separate your class declaration and definition into separate
Bst.handBst.cppfiles - For
Bst.hprovide header guards
- initialize
shared_ptr<node>member,rootwithnullptr
answered Feb 1 at 16:09
programmerprogrammer
513
answered Feb 1 at 16:09
programmerprogrammer
513
answered Feb 1 at 16:09
programmerprogrammer
513
answered Feb 1 at 16:09
programmerprogrammer
513
513
2
$begingroup$
I thought root will be initialized to nullptr by default ?
$endgroup$
– bornfree
Feb 1 at 17:30
add a comment |
2
$begingroup$
I thought root will be initialized to nullptr by default ?
$endgroup$
– bornfree
Feb 1 at 17:30
2
2
$begingroup$
I thought root will be initialized to nullptr by default ?
$endgroup$
– bornfree
Feb 1 at 17:30
$begingroup$
I thought root will be initialized to nullptr by default ?
$endgroup$
– bornfree
Feb 1 at 17:30
add a comment |
$begingroup$
You forgot to include any of the headers that your code depends on; copy/paste of this into https://godbolt.org/ gives lots of errors until I add #include <memory> and iostream, and some using declarations (https://godbolt.org/z/cE0GDR). So the code in the question is incomplete.
More importantly, for shared_ptr to be thread-safe, it has to use atomic-increment / decrement instructions, and check if the ref-count has become 0 after it's done referencing a node. This makes it significantly more expensive than I think you want. As another answer suggests, std::unique_ptr<> is probably a better choice.
So for example, your findmin() source looks really simple, just traversing down to the left-most leaf node, but because you're using shared_ptr it compiles (on x86-64) to lock add and lock xadd instructions, potentially calling the destructor to free the node.
(gcc emits checks before actually doing the atomic ++ / -- ref counting. It checks the address of a weak alias for __pthread_key_create. I think this might just be checking if the program could possibly be multi-threaded, i.e. linked with the thread library, rather than if multiple threads are currently running. So some of the cost of shared_ptr might go away in some single-threaded programs.)
If you're looking at the asm on the Godbolt compiler explorer, search for the lock prefix for x86-64. Or for AArch64, look for ldaxr/stlxr LL/SC retry loops (load-acquire exclusive / store sequential-release exclusive).
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
$endgroup$
add a comment |
$begingroup$
You forgot to include any of the headers that your code depends on; copy/paste of this into https://godbolt.org/ gives lots of errors until I add #include <memory> and iostream, and some using declarations (https://godbolt.org/z/cE0GDR). So the code in the question is incomplete.
More importantly, for shared_ptr to be thread-safe, it has to use atomic-increment / decrement instructions, and check if the ref-count has become 0 after it's done referencing a node. This makes it significantly more expensive than I think you want. As another answer suggests, std::unique_ptr<> is probably a better choice.
So for example, your findmin() source looks really simple, just traversing down to the left-most leaf node, but because you're using shared_ptr it compiles (on x86-64) to lock add and lock xadd instructions, potentially calling the destructor to free the node.
(gcc emits checks before actually doing the atomic ++ / -- ref counting. It checks the address of a weak alias for __pthread_key_create. I think this might just be checking if the program could possibly be multi-threaded, i.e. linked with the thread library, rather than if multiple threads are currently running. So some of the cost of shared_ptr might go away in some single-threaded programs.)
If you're looking at the asm on the Godbolt compiler explorer, search for the lock prefix for x86-64. Or for AArch64, look for ldaxr/stlxr LL/SC retry loops (load-acquire exclusive / store sequential-release exclusive).
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
$endgroup$
add a comment |
$begingroup$
You forgot to include any of the headers that your code depends on; copy/paste of this into https://godbolt.org/ gives lots of errors until I add #include <memory> and iostream, and some using declarations (https://godbolt.org/z/cE0GDR). So the code in the question is incomplete.
More importantly, for shared_ptr to be thread-safe, it has to use atomic-increment / decrement instructions, and check if the ref-count has become 0 after it's done referencing a node. This makes it significantly more expensive than I think you want. As another answer suggests, std::unique_ptr<> is probably a better choice.
So for example, your findmin() source looks really simple, just traversing down to the left-most leaf node, but because you're using shared_ptr it compiles (on x86-64) to lock add and lock xadd instructions, potentially calling the destructor to free the node.
(gcc emits checks before actually doing the atomic ++ / -- ref counting. It checks the address of a weak alias for __pthread_key_create. I think this might just be checking if the program could possibly be multi-threaded, i.e. linked with the thread library, rather than if multiple threads are currently running. So some of the cost of shared_ptr might go away in some single-threaded programs.)
If you're looking at the asm on the Godbolt compiler explorer, search for the lock prefix for x86-64. Or for AArch64, look for ldaxr/stlxr LL/SC retry loops (load-acquire exclusive / store sequential-release exclusive).
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
$endgroup$
You forgot to include any of the headers that your code depends on; copy/paste of this into https://godbolt.org/ gives lots of errors until I add #include <memory> and iostream, and some using declarations (https://godbolt.org/z/cE0GDR). So the code in the question is incomplete.
More importantly, for shared_ptr to be thread-safe, it has to use atomic-increment / decrement instructions, and check if the ref-count has become 0 after it's done referencing a node. This makes it significantly more expensive than I think you want. As another answer suggests, std::unique_ptr<> is probably a better choice.
So for example, your findmin() source looks really simple, just traversing down to the left-most leaf node, but because you're using shared_ptr it compiles (on x86-64) to lock add and lock xadd instructions, potentially calling the destructor to free the node.
(gcc emits checks before actually doing the atomic ++ / -- ref counting. It checks the address of a weak alias for __pthread_key_create. I think this might just be checking if the program could possibly be multi-threaded, i.e. linked with the thread library, rather than if multiple threads are currently running. So some of the cost of shared_ptr might go away in some single-threaded programs.)
If you're looking at the asm on the Godbolt compiler explorer, search for the lock prefix for x86-64. Or for AArch64, look for ldaxr/stlxr LL/SC retry loops (load-acquire exclusive / store sequential-release exclusive).
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
answered Feb 2 at 8:23
Peter CordesPeter Cordes
1,528516
1,528516
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f212692%2fbinary-search-tree-implementation-using-smart-pointers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
