Using raw pointers in nodes and unique_ptr in treesShould I move a unique_pointer or should I send a pointer to a unique_pointer?What are the differences between a pointer variable and a reference variable in C++?What is a smart pointer and when should I use one?Returning unique_ptr from functionsCycles in family tree softwareDifferences between unique_ptr and shared_ptrHow do I pass a unique_ptr argument to a constructor or a function?Raw pointer lookup for sets of unique_ptrsWhy should I use a pointer rather than the object itself?Destroying tree structured vectors of std::unique_ptrC++ passing std::unique_ptr as an argument
What do you call something that goes against the spirit of the law, but is legal when interpreting the law to the letter?
least quadratic residue under GRH: an EXPLICIT bound
I probably found a bug with the sudo apt install function
What typically incentivizes a professor to change jobs to a lower ranking university?
Is there really no realistic way for a skeleton monster to move around without magic?
How can the DM most effectively choose 1 out of an odd number of players to be targeted by an attack or effect?
How does one intimidate enemies without having the capacity for violence?
Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?
What makes Graph invariants so useful/important?
XeLaTeX and pdfLaTeX ignore hyphenation
Infinite past with a beginning?
Is it possible to make sharp wind that can cut stuff from afar?
Copenhagen passport control - US citizen
How can bays and straits be determined in a procedurally generated map?
How do we improve the relationship with a client software team that performs poorly and is becoming less collaborative?
What is the offset in a seaplane's hull?
Why did the Germans forbid the possession of pet pigeons in Rostov-on-Don in 1941?
Why has Russell's definition of numbers using equivalence classes been finally abandoned? ( If it has actually been abandoned).
How is the claim "I am in New York only if I am in America" the same as "If I am in New York, then I am in America?
Simulate Bitwise Cyclic Tag
New order #4: World
What is the white spray-pattern residue inside these Falcon Heavy nozzles?
Draw simple lines in Inkscape
How can I fix this gap between bookcases I made?
Using raw pointers in nodes and unique_ptr in trees
Should I move a unique_pointer or should I send a pointer to a unique_pointer?What are the differences between a pointer variable and a reference variable in C++?What is a smart pointer and when should I use one?Returning unique_ptr from functionsCycles in family tree softwareDifferences between unique_ptr and shared_ptrHow do I pass a unique_ptr argument to a constructor or a function?Raw pointer lookup for sets of unique_ptrsWhy should I use a pointer rather than the object itself?Destroying tree structured vectors of std::unique_ptrC++ passing std::unique_ptr as an argument
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
I am a hobbyist programmer trying find the appropriate place to put unique_ptr
in my binary tree. Originally, I used unique_ptr
for the left and right children, but that "meant" that each node "owned" each subsequent node. I have been told in a previous post that the tree should own its nodes. This is my solution to the problem: all of the trees nodes are stored in a vector of unique pointers and unique_ptr::get
is used to extract the raw pointers which are used in the usual manner (example add).
#include "pch.h"
#include <iostream>
#include <sstream>
#include <string>
#include <memory>
#include <vector>
#include <unordered_map>
class Node
public:
Node(int data = 0) : data_(data), left_child(nullptr),
right_child(nullptr)
int data_;
Node *left_child;
Node *right_child;
;
class Tree
public:
Tree(int data = 0)
store.emplace_back(std::make_unique<Node>(data));
root = store.at(0).get();
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.get();
store.push_back(std::move(temp));
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.get();
store.push_back(std::move(temp));
return;
private:
std::vector<std::unique_ptr<Node>> store;
Node* root;
;
Removing a node seems like it will be painfully slow. Find the value in the tree (fast), find the pointer in the std::vector
(slow), remove the entry from the vector, and finally trim the pointer from the parent. Am I on the right track? If not, hints would be welcome.
c++ pointers tree c++14 unique-ptr
add a comment |
I am a hobbyist programmer trying find the appropriate place to put unique_ptr
in my binary tree. Originally, I used unique_ptr
for the left and right children, but that "meant" that each node "owned" each subsequent node. I have been told in a previous post that the tree should own its nodes. This is my solution to the problem: all of the trees nodes are stored in a vector of unique pointers and unique_ptr::get
is used to extract the raw pointers which are used in the usual manner (example add).
#include "pch.h"
#include <iostream>
#include <sstream>
#include <string>
#include <memory>
#include <vector>
#include <unordered_map>
class Node
public:
Node(int data = 0) : data_(data), left_child(nullptr),
right_child(nullptr)
int data_;
Node *left_child;
Node *right_child;
;
class Tree
public:
Tree(int data = 0)
store.emplace_back(std::make_unique<Node>(data));
root = store.at(0).get();
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.get();
store.push_back(std::move(temp));
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.get();
store.push_back(std::move(temp));
return;
private:
std::vector<std::unique_ptr<Node>> store;
Node* root;
;
Removing a node seems like it will be painfully slow. Find the value in the tree (fast), find the pointer in the std::vector
(slow), remove the entry from the vector, and finally trim the pointer from the parent. Am I on the right track? If not, hints would be welcome.
c++ pointers tree c++14 unique-ptr
2
I came to the conclusion that using smart pointers to implement basic container types is likely as much trouble as it is worth. The container itself is a RAII object and it is probably simpler to write a cleanup constructor than figure out if your nodes contain pointers to nodes or pointers to smart pointers to nodes... or whatever.
– Galik
Mar 19 at 5:32
When people tell you that the tree should own the nodes, they usually mean what Galik suggested. While thevector
's a good way to make sure the nodes are all freed when the tree is gone, you're no better off in the general case of freeing a node without destroying the tree. If you miss a case, or have a case where you forget to erase, you are almost back to where you started with detritus building up in thevector
. You might as well manuallydelete
.
– user4581301
Mar 19 at 5:40
add a comment |
I am a hobbyist programmer trying find the appropriate place to put unique_ptr
in my binary tree. Originally, I used unique_ptr
for the left and right children, but that "meant" that each node "owned" each subsequent node. I have been told in a previous post that the tree should own its nodes. This is my solution to the problem: all of the trees nodes are stored in a vector of unique pointers and unique_ptr::get
is used to extract the raw pointers which are used in the usual manner (example add).
#include "pch.h"
#include <iostream>
#include <sstream>
#include <string>
#include <memory>
#include <vector>
#include <unordered_map>
class Node
public:
Node(int data = 0) : data_(data), left_child(nullptr),
right_child(nullptr)
int data_;
Node *left_child;
Node *right_child;
;
class Tree
public:
Tree(int data = 0)
store.emplace_back(std::make_unique<Node>(data));
root = store.at(0).get();
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.get();
store.push_back(std::move(temp));
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.get();
store.push_back(std::move(temp));
return;
private:
std::vector<std::unique_ptr<Node>> store;
Node* root;
;
Removing a node seems like it will be painfully slow. Find the value in the tree (fast), find the pointer in the std::vector
(slow), remove the entry from the vector, and finally trim the pointer from the parent. Am I on the right track? If not, hints would be welcome.
c++ pointers tree c++14 unique-ptr
I am a hobbyist programmer trying find the appropriate place to put unique_ptr
in my binary tree. Originally, I used unique_ptr
for the left and right children, but that "meant" that each node "owned" each subsequent node. I have been told in a previous post that the tree should own its nodes. This is my solution to the problem: all of the trees nodes are stored in a vector of unique pointers and unique_ptr::get
is used to extract the raw pointers which are used in the usual manner (example add).
#include "pch.h"
#include <iostream>
#include <sstream>
#include <string>
#include <memory>
#include <vector>
#include <unordered_map>
class Node
public:
Node(int data = 0) : data_(data), left_child(nullptr),
right_child(nullptr)
int data_;
Node *left_child;
Node *right_child;
;
class Tree
public:
Tree(int data = 0)
store.emplace_back(std::make_unique<Node>(data));
root = store.at(0).get();
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.get();
store.push_back(std::move(temp));
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.get();
store.push_back(std::move(temp));
return;
private:
std::vector<std::unique_ptr<Node>> store;
Node* root;
;
Removing a node seems like it will be painfully slow. Find the value in the tree (fast), find the pointer in the std::vector
(slow), remove the entry from the vector, and finally trim the pointer from the parent. Am I on the right track? If not, hints would be welcome.
c++ pointers tree c++14 unique-ptr
c++ pointers tree c++14 unique-ptr
asked Mar 19 at 5:24
davidbeardavidbear
197
197
2
I came to the conclusion that using smart pointers to implement basic container types is likely as much trouble as it is worth. The container itself is a RAII object and it is probably simpler to write a cleanup constructor than figure out if your nodes contain pointers to nodes or pointers to smart pointers to nodes... or whatever.
– Galik
Mar 19 at 5:32
When people tell you that the tree should own the nodes, they usually mean what Galik suggested. While thevector
's a good way to make sure the nodes are all freed when the tree is gone, you're no better off in the general case of freeing a node without destroying the tree. If you miss a case, or have a case where you forget to erase, you are almost back to where you started with detritus building up in thevector
. You might as well manuallydelete
.
– user4581301
Mar 19 at 5:40
add a comment |
2
I came to the conclusion that using smart pointers to implement basic container types is likely as much trouble as it is worth. The container itself is a RAII object and it is probably simpler to write a cleanup constructor than figure out if your nodes contain pointers to nodes or pointers to smart pointers to nodes... or whatever.
– Galik
Mar 19 at 5:32
When people tell you that the tree should own the nodes, they usually mean what Galik suggested. While thevector
's a good way to make sure the nodes are all freed when the tree is gone, you're no better off in the general case of freeing a node without destroying the tree. If you miss a case, or have a case where you forget to erase, you are almost back to where you started with detritus building up in thevector
. You might as well manuallydelete
.
– user4581301
Mar 19 at 5:40
2
2
I came to the conclusion that using smart pointers to implement basic container types is likely as much trouble as it is worth. The container itself is a RAII object and it is probably simpler to write a cleanup constructor than figure out if your nodes contain pointers to nodes or pointers to smart pointers to nodes... or whatever.
– Galik
Mar 19 at 5:32
I came to the conclusion that using smart pointers to implement basic container types is likely as much trouble as it is worth. The container itself is a RAII object and it is probably simpler to write a cleanup constructor than figure out if your nodes contain pointers to nodes or pointers to smart pointers to nodes... or whatever.
– Galik
Mar 19 at 5:32
When people tell you that the tree should own the nodes, they usually mean what Galik suggested. While the
vector
's a good way to make sure the nodes are all freed when the tree is gone, you're no better off in the general case of freeing a node without destroying the tree. If you miss a case, or have a case where you forget to erase, you are almost back to where you started with detritus building up in the vector
. You might as well manually delete
.– user4581301
Mar 19 at 5:40
When people tell you that the tree should own the nodes, they usually mean what Galik suggested. While the
vector
's a good way to make sure the nodes are all freed when the tree is gone, you're no better off in the general case of freeing a node without destroying the tree. If you miss a case, or have a case where you forget to erase, you are almost back to where you started with detritus building up in the vector
. You might as well manually delete
.– user4581301
Mar 19 at 5:40
add a comment |
2 Answers
2
active
oldest
votes
Using std::unique_ptr for the children is the quick-and-dirty solution, but it does not match the requirement of the question. Putting the pointers into a vector is a bad idea due to the convoluted code, and time complexity involved.
The quick-and-dirty solution is to write a function in the tree, that will recursively delete the nodes. The disadvantage is a potential stack-overflow if the tree is unbalanced (just like with std::unique_ptr
on the children). There are several ways to combat the potential stack-overflow:
The efficient solution, that does not have the stack-overflow, neither the potential of std::bad_alloc
exception. It is a DFS algorithm, using the freed tree nodes as the stack. The Node::left entry will point to the payload (the subtree to be freed), and Node::right will have the role of next
in the DFS stack (a linked list).
static Node * & nextNode(Node & node)
return node.right_child;
static Node * & payload(Node & node)
return node.left_child;
Tree::~Tree()
Node temp;
Node *stack = & temp;
payload(*stack) = root;
nextNode(*stack) = nullptr;
constexpr bool TRACE = false;
while (stack)
Node * treeNode = payload(*stack);
Node * toPush1 = treeNode->left_child;
Node * toPush2 = treeNode->right_child;
if (toPush1)
payload(*stack) = toPush1;
if (toPush2)
payload(*treeNode) = toPush2;
nextNode(*treeNode) = stack;
stack = treeNode;
else
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else if (toPush2)
payload(*stack) = toPush2;
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else // nothing to push
Node *nextStack = nextNode(*stack);
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
// free the stack.
while (stack)
Node *nextStack = nextNode(*stack);
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
if (TRACE) std::cout << 'n';
This will get you both memory efficient, with O(1) additional memory, and time efficient, with O(N) time complexity.
For completeness, here is the rest of the Tree class:
class Tree
public:
Tree(int data = 0)
root = new Node(data);
~Tree();
Copy ctor, assignment, move ctor, move assignment
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.release();
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.release();
return;
private:
// owning the root and all descendants recursively
Node* root;
;
Sorry to be so thick, but what does the rest ofTree
look like? How is ownership established? How are child nodes added to the root?
– davidbear
Mar 21 at 23:07
@davidbear added more of Tree to the answer. Ownership is implied in the Tree. Ownership goes recursively from root.
– Michael Veksler
Mar 22 at 0:59
So bottom line is thatstd::unique_ptr
just cannot be effectively used in a binary tree structure where the nodes are "owned" by the tree? Given all the talk that there is no "good reason" to ever usenew
, this surprises me.
– davidbear
Mar 22 at 2:55
@davidbear not quite. The recommended approach is to have unique_ptr for children, but your request was to avoid that. After all, a subtree owns the left and right subtrees. If you insist you can rename Node to Subtree. Also, the stack overflow is non-issue for self balancing trees since even for a billion nodes it is not even 100 levels deep. But if one insists on unbalanced trees, then freening is better done iteratively, on top of unique_ptr
– Michael Veksler
Mar 22 at 7:20
the only reason for my request to avoidstd::unique_ptr
for children pointers was because I was told that that was a poor ownership model by someone on stackoverflow. My code was to solve the problem of wanting to usestd::unique_ptr
and get the ownership model "correct." I appreciate this discourse. Thanks
– davidbear
Mar 22 at 15:30
add a comment |
Of course it's a bad idea to have an vector
of all the allocated nodes in your Tree
class. As you pointed-out, manipulating it to find and erase a Node
is slow (i.e. depends linearly on your tree size), and diminishes all the advantages your tree is supposed to have.
A first suggestion would be using std::unique_ptr<Node>
for your left_child
and right_child
members of your Node
. Then you'll not need the vector
to store all the nodes.
But in your specific implementation is not enough: you do nothing to ballance the tree, hence in worst-case its depth will grow linearly, hence the recursive cleanup will fail (stack overflow). You'll need a hybrid iterative-recursive cleanup.
But you can do this as a next step. First step - just get rid of the vector
.
As I said, my first crack at this problem usedunique_ptr
for both left and right children, but I was told thatunique_ptr
conveyed "ownership." And it was suggested that the tree should do the owning. This specific implementation is just some example code using this ownership model. An AVL-type tree and proper destructors would probably be used in an actual implementation. Thank you for your thoughts.
– davidbear
Mar 19 at 5:41
2
Ok, then don't useunique_ptr
. Instead you'd need to implement the recursive deletion of yourNode
in theTree
class. But in either case usingvector
to store all the nodes just to "own" them is the worst idea.
– valdo
Mar 19 at 5:48
add a comment |
Your Answer
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: "1"
;
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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%2fstackoverflow.com%2fquestions%2f55234146%2fusing-raw-pointers-in-nodes-and-unique-ptr-in-trees%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Using std::unique_ptr for the children is the quick-and-dirty solution, but it does not match the requirement of the question. Putting the pointers into a vector is a bad idea due to the convoluted code, and time complexity involved.
The quick-and-dirty solution is to write a function in the tree, that will recursively delete the nodes. The disadvantage is a potential stack-overflow if the tree is unbalanced (just like with std::unique_ptr
on the children). There are several ways to combat the potential stack-overflow:
The efficient solution, that does not have the stack-overflow, neither the potential of std::bad_alloc
exception. It is a DFS algorithm, using the freed tree nodes as the stack. The Node::left entry will point to the payload (the subtree to be freed), and Node::right will have the role of next
in the DFS stack (a linked list).
static Node * & nextNode(Node & node)
return node.right_child;
static Node * & payload(Node & node)
return node.left_child;
Tree::~Tree()
Node temp;
Node *stack = & temp;
payload(*stack) = root;
nextNode(*stack) = nullptr;
constexpr bool TRACE = false;
while (stack)
Node * treeNode = payload(*stack);
Node * toPush1 = treeNode->left_child;
Node * toPush2 = treeNode->right_child;
if (toPush1)
payload(*stack) = toPush1;
if (toPush2)
payload(*treeNode) = toPush2;
nextNode(*treeNode) = stack;
stack = treeNode;
else
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else if (toPush2)
payload(*stack) = toPush2;
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else // nothing to push
Node *nextStack = nextNode(*stack);
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
// free the stack.
while (stack)
Node *nextStack = nextNode(*stack);
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
if (TRACE) std::cout << 'n';
This will get you both memory efficient, with O(1) additional memory, and time efficient, with O(N) time complexity.
For completeness, here is the rest of the Tree class:
class Tree
public:
Tree(int data = 0)
root = new Node(data);
~Tree();
Copy ctor, assignment, move ctor, move assignment
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.release();
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.release();
return;
private:
// owning the root and all descendants recursively
Node* root;
;
Sorry to be so thick, but what does the rest ofTree
look like? How is ownership established? How are child nodes added to the root?
– davidbear
Mar 21 at 23:07
@davidbear added more of Tree to the answer. Ownership is implied in the Tree. Ownership goes recursively from root.
– Michael Veksler
Mar 22 at 0:59
So bottom line is thatstd::unique_ptr
just cannot be effectively used in a binary tree structure where the nodes are "owned" by the tree? Given all the talk that there is no "good reason" to ever usenew
, this surprises me.
– davidbear
Mar 22 at 2:55
@davidbear not quite. The recommended approach is to have unique_ptr for children, but your request was to avoid that. After all, a subtree owns the left and right subtrees. If you insist you can rename Node to Subtree. Also, the stack overflow is non-issue for self balancing trees since even for a billion nodes it is not even 100 levels deep. But if one insists on unbalanced trees, then freening is better done iteratively, on top of unique_ptr
– Michael Veksler
Mar 22 at 7:20
the only reason for my request to avoidstd::unique_ptr
for children pointers was because I was told that that was a poor ownership model by someone on stackoverflow. My code was to solve the problem of wanting to usestd::unique_ptr
and get the ownership model "correct." I appreciate this discourse. Thanks
– davidbear
Mar 22 at 15:30
add a comment |
Using std::unique_ptr for the children is the quick-and-dirty solution, but it does not match the requirement of the question. Putting the pointers into a vector is a bad idea due to the convoluted code, and time complexity involved.
The quick-and-dirty solution is to write a function in the tree, that will recursively delete the nodes. The disadvantage is a potential stack-overflow if the tree is unbalanced (just like with std::unique_ptr
on the children). There are several ways to combat the potential stack-overflow:
The efficient solution, that does not have the stack-overflow, neither the potential of std::bad_alloc
exception. It is a DFS algorithm, using the freed tree nodes as the stack. The Node::left entry will point to the payload (the subtree to be freed), and Node::right will have the role of next
in the DFS stack (a linked list).
static Node * & nextNode(Node & node)
return node.right_child;
static Node * & payload(Node & node)
return node.left_child;
Tree::~Tree()
Node temp;
Node *stack = & temp;
payload(*stack) = root;
nextNode(*stack) = nullptr;
constexpr bool TRACE = false;
while (stack)
Node * treeNode = payload(*stack);
Node * toPush1 = treeNode->left_child;
Node * toPush2 = treeNode->right_child;
if (toPush1)
payload(*stack) = toPush1;
if (toPush2)
payload(*treeNode) = toPush2;
nextNode(*treeNode) = stack;
stack = treeNode;
else
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else if (toPush2)
payload(*stack) = toPush2;
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else // nothing to push
Node *nextStack = nextNode(*stack);
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
// free the stack.
while (stack)
Node *nextStack = nextNode(*stack);
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
if (TRACE) std::cout << 'n';
This will get you both memory efficient, with O(1) additional memory, and time efficient, with O(N) time complexity.
For completeness, here is the rest of the Tree class:
class Tree
public:
Tree(int data = 0)
root = new Node(data);
~Tree();
Copy ctor, assignment, move ctor, move assignment
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.release();
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.release();
return;
private:
// owning the root and all descendants recursively
Node* root;
;
Sorry to be so thick, but what does the rest ofTree
look like? How is ownership established? How are child nodes added to the root?
– davidbear
Mar 21 at 23:07
@davidbear added more of Tree to the answer. Ownership is implied in the Tree. Ownership goes recursively from root.
– Michael Veksler
Mar 22 at 0:59
So bottom line is thatstd::unique_ptr
just cannot be effectively used in a binary tree structure where the nodes are "owned" by the tree? Given all the talk that there is no "good reason" to ever usenew
, this surprises me.
– davidbear
Mar 22 at 2:55
@davidbear not quite. The recommended approach is to have unique_ptr for children, but your request was to avoid that. After all, a subtree owns the left and right subtrees. If you insist you can rename Node to Subtree. Also, the stack overflow is non-issue for self balancing trees since even for a billion nodes it is not even 100 levels deep. But if one insists on unbalanced trees, then freening is better done iteratively, on top of unique_ptr
– Michael Veksler
Mar 22 at 7:20
the only reason for my request to avoidstd::unique_ptr
for children pointers was because I was told that that was a poor ownership model by someone on stackoverflow. My code was to solve the problem of wanting to usestd::unique_ptr
and get the ownership model "correct." I appreciate this discourse. Thanks
– davidbear
Mar 22 at 15:30
add a comment |
Using std::unique_ptr for the children is the quick-and-dirty solution, but it does not match the requirement of the question. Putting the pointers into a vector is a bad idea due to the convoluted code, and time complexity involved.
The quick-and-dirty solution is to write a function in the tree, that will recursively delete the nodes. The disadvantage is a potential stack-overflow if the tree is unbalanced (just like with std::unique_ptr
on the children). There are several ways to combat the potential stack-overflow:
The efficient solution, that does not have the stack-overflow, neither the potential of std::bad_alloc
exception. It is a DFS algorithm, using the freed tree nodes as the stack. The Node::left entry will point to the payload (the subtree to be freed), and Node::right will have the role of next
in the DFS stack (a linked list).
static Node * & nextNode(Node & node)
return node.right_child;
static Node * & payload(Node & node)
return node.left_child;
Tree::~Tree()
Node temp;
Node *stack = & temp;
payload(*stack) = root;
nextNode(*stack) = nullptr;
constexpr bool TRACE = false;
while (stack)
Node * treeNode = payload(*stack);
Node * toPush1 = treeNode->left_child;
Node * toPush2 = treeNode->right_child;
if (toPush1)
payload(*stack) = toPush1;
if (toPush2)
payload(*treeNode) = toPush2;
nextNode(*treeNode) = stack;
stack = treeNode;
else
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else if (toPush2)
payload(*stack) = toPush2;
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else // nothing to push
Node *nextStack = nextNode(*stack);
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
// free the stack.
while (stack)
Node *nextStack = nextNode(*stack);
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
if (TRACE) std::cout << 'n';
This will get you both memory efficient, with O(1) additional memory, and time efficient, with O(N) time complexity.
For completeness, here is the rest of the Tree class:
class Tree
public:
Tree(int data = 0)
root = new Node(data);
~Tree();
Copy ctor, assignment, move ctor, move assignment
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.release();
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.release();
return;
private:
// owning the root and all descendants recursively
Node* root;
;
Using std::unique_ptr for the children is the quick-and-dirty solution, but it does not match the requirement of the question. Putting the pointers into a vector is a bad idea due to the convoluted code, and time complexity involved.
The quick-and-dirty solution is to write a function in the tree, that will recursively delete the nodes. The disadvantage is a potential stack-overflow if the tree is unbalanced (just like with std::unique_ptr
on the children). There are several ways to combat the potential stack-overflow:
The efficient solution, that does not have the stack-overflow, neither the potential of std::bad_alloc
exception. It is a DFS algorithm, using the freed tree nodes as the stack. The Node::left entry will point to the payload (the subtree to be freed), and Node::right will have the role of next
in the DFS stack (a linked list).
static Node * & nextNode(Node & node)
return node.right_child;
static Node * & payload(Node & node)
return node.left_child;
Tree::~Tree()
Node temp;
Node *stack = & temp;
payload(*stack) = root;
nextNode(*stack) = nullptr;
constexpr bool TRACE = false;
while (stack)
Node * treeNode = payload(*stack);
Node * toPush1 = treeNode->left_child;
Node * toPush2 = treeNode->right_child;
if (toPush1)
payload(*stack) = toPush1;
if (toPush2)
payload(*treeNode) = toPush2;
nextNode(*treeNode) = stack;
stack = treeNode;
else
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else if (toPush2)
payload(*stack) = toPush2;
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
else // nothing to push
Node *nextStack = nextNode(*stack);
if (TRACE) std::cout << treeNode->data_ << " ";
delete treeNode;
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
// free the stack.
while (stack)
Node *nextStack = nextNode(*stack);
if (stack != &temp)
if (TRACE) std::cout << stack->data_ << " ";
delete stack;
stack = nextStack;
if (TRACE) std::cout << 'n';
This will get you both memory efficient, with O(1) additional memory, and time efficient, with O(N) time complexity.
For completeness, here is the rest of the Tree class:
class Tree
public:
Tree(int data = 0)
root = new Node(data);
~Tree();
Copy ctor, assignment, move ctor, move assignment
void add(int data)
Node *index = root;
while (true)
if (data == index->data_)
std::stringstream ss;
ss << data << " already existsn";
throw std::invalid_argument(ss.str());
if (data < index->data_)
if (index->left_child != nullptr)
index = index->left_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->left_child = temp.release();
return;
if (index->right_child != nullptr)
index = index->right_child;
continue;
std::unique_ptr<Node> temp = std::make_unique<Node>(data);
index->right_child = temp.release();
return;
private:
// owning the root and all descendants recursively
Node* root;
;
edited Mar 22 at 0:57
answered Mar 19 at 16:18
Michael VekslerMichael Veksler
5,3721724
5,3721724
Sorry to be so thick, but what does the rest ofTree
look like? How is ownership established? How are child nodes added to the root?
– davidbear
Mar 21 at 23:07
@davidbear added more of Tree to the answer. Ownership is implied in the Tree. Ownership goes recursively from root.
– Michael Veksler
Mar 22 at 0:59
So bottom line is thatstd::unique_ptr
just cannot be effectively used in a binary tree structure where the nodes are "owned" by the tree? Given all the talk that there is no "good reason" to ever usenew
, this surprises me.
– davidbear
Mar 22 at 2:55
@davidbear not quite. The recommended approach is to have unique_ptr for children, but your request was to avoid that. After all, a subtree owns the left and right subtrees. If you insist you can rename Node to Subtree. Also, the stack overflow is non-issue for self balancing trees since even for a billion nodes it is not even 100 levels deep. But if one insists on unbalanced trees, then freening is better done iteratively, on top of unique_ptr
– Michael Veksler
Mar 22 at 7:20
the only reason for my request to avoidstd::unique_ptr
for children pointers was because I was told that that was a poor ownership model by someone on stackoverflow. My code was to solve the problem of wanting to usestd::unique_ptr
and get the ownership model "correct." I appreciate this discourse. Thanks
– davidbear
Mar 22 at 15:30
add a comment |
Sorry to be so thick, but what does the rest ofTree
look like? How is ownership established? How are child nodes added to the root?
– davidbear
Mar 21 at 23:07
@davidbear added more of Tree to the answer. Ownership is implied in the Tree. Ownership goes recursively from root.
– Michael Veksler
Mar 22 at 0:59
So bottom line is thatstd::unique_ptr
just cannot be effectively used in a binary tree structure where the nodes are "owned" by the tree? Given all the talk that there is no "good reason" to ever usenew
, this surprises me.
– davidbear
Mar 22 at 2:55
@davidbear not quite. The recommended approach is to have unique_ptr for children, but your request was to avoid that. After all, a subtree owns the left and right subtrees. If you insist you can rename Node to Subtree. Also, the stack overflow is non-issue for self balancing trees since even for a billion nodes it is not even 100 levels deep. But if one insists on unbalanced trees, then freening is better done iteratively, on top of unique_ptr
– Michael Veksler
Mar 22 at 7:20
the only reason for my request to avoidstd::unique_ptr
for children pointers was because I was told that that was a poor ownership model by someone on stackoverflow. My code was to solve the problem of wanting to usestd::unique_ptr
and get the ownership model "correct." I appreciate this discourse. Thanks
– davidbear
Mar 22 at 15:30
Sorry to be so thick, but what does the rest of
Tree
look like? How is ownership established? How are child nodes added to the root?– davidbear
Mar 21 at 23:07
Sorry to be so thick, but what does the rest of
Tree
look like? How is ownership established? How are child nodes added to the root?– davidbear
Mar 21 at 23:07
@davidbear added more of Tree to the answer. Ownership is implied in the Tree. Ownership goes recursively from root.
– Michael Veksler
Mar 22 at 0:59
@davidbear added more of Tree to the answer. Ownership is implied in the Tree. Ownership goes recursively from root.
– Michael Veksler
Mar 22 at 0:59
So bottom line is that
std::unique_ptr
just cannot be effectively used in a binary tree structure where the nodes are "owned" by the tree? Given all the talk that there is no "good reason" to ever use new
, this surprises me.– davidbear
Mar 22 at 2:55
So bottom line is that
std::unique_ptr
just cannot be effectively used in a binary tree structure where the nodes are "owned" by the tree? Given all the talk that there is no "good reason" to ever use new
, this surprises me.– davidbear
Mar 22 at 2:55
@davidbear not quite. The recommended approach is to have unique_ptr for children, but your request was to avoid that. After all, a subtree owns the left and right subtrees. If you insist you can rename Node to Subtree. Also, the stack overflow is non-issue for self balancing trees since even for a billion nodes it is not even 100 levels deep. But if one insists on unbalanced trees, then freening is better done iteratively, on top of unique_ptr
– Michael Veksler
Mar 22 at 7:20
@davidbear not quite. The recommended approach is to have unique_ptr for children, but your request was to avoid that. After all, a subtree owns the left and right subtrees. If you insist you can rename Node to Subtree. Also, the stack overflow is non-issue for self balancing trees since even for a billion nodes it is not even 100 levels deep. But if one insists on unbalanced trees, then freening is better done iteratively, on top of unique_ptr
– Michael Veksler
Mar 22 at 7:20
the only reason for my request to avoid
std::unique_ptr
for children pointers was because I was told that that was a poor ownership model by someone on stackoverflow. My code was to solve the problem of wanting to use std::unique_ptr
and get the ownership model "correct." I appreciate this discourse. Thanks– davidbear
Mar 22 at 15:30
the only reason for my request to avoid
std::unique_ptr
for children pointers was because I was told that that was a poor ownership model by someone on stackoverflow. My code was to solve the problem of wanting to use std::unique_ptr
and get the ownership model "correct." I appreciate this discourse. Thanks– davidbear
Mar 22 at 15:30
add a comment |
Of course it's a bad idea to have an vector
of all the allocated nodes in your Tree
class. As you pointed-out, manipulating it to find and erase a Node
is slow (i.e. depends linearly on your tree size), and diminishes all the advantages your tree is supposed to have.
A first suggestion would be using std::unique_ptr<Node>
for your left_child
and right_child
members of your Node
. Then you'll not need the vector
to store all the nodes.
But in your specific implementation is not enough: you do nothing to ballance the tree, hence in worst-case its depth will grow linearly, hence the recursive cleanup will fail (stack overflow). You'll need a hybrid iterative-recursive cleanup.
But you can do this as a next step. First step - just get rid of the vector
.
As I said, my first crack at this problem usedunique_ptr
for both left and right children, but I was told thatunique_ptr
conveyed "ownership." And it was suggested that the tree should do the owning. This specific implementation is just some example code using this ownership model. An AVL-type tree and proper destructors would probably be used in an actual implementation. Thank you for your thoughts.
– davidbear
Mar 19 at 5:41
2
Ok, then don't useunique_ptr
. Instead you'd need to implement the recursive deletion of yourNode
in theTree
class. But in either case usingvector
to store all the nodes just to "own" them is the worst idea.
– valdo
Mar 19 at 5:48
add a comment |
Of course it's a bad idea to have an vector
of all the allocated nodes in your Tree
class. As you pointed-out, manipulating it to find and erase a Node
is slow (i.e. depends linearly on your tree size), and diminishes all the advantages your tree is supposed to have.
A first suggestion would be using std::unique_ptr<Node>
for your left_child
and right_child
members of your Node
. Then you'll not need the vector
to store all the nodes.
But in your specific implementation is not enough: you do nothing to ballance the tree, hence in worst-case its depth will grow linearly, hence the recursive cleanup will fail (stack overflow). You'll need a hybrid iterative-recursive cleanup.
But you can do this as a next step. First step - just get rid of the vector
.
As I said, my first crack at this problem usedunique_ptr
for both left and right children, but I was told thatunique_ptr
conveyed "ownership." And it was suggested that the tree should do the owning. This specific implementation is just some example code using this ownership model. An AVL-type tree and proper destructors would probably be used in an actual implementation. Thank you for your thoughts.
– davidbear
Mar 19 at 5:41
2
Ok, then don't useunique_ptr
. Instead you'd need to implement the recursive deletion of yourNode
in theTree
class. But in either case usingvector
to store all the nodes just to "own" them is the worst idea.
– valdo
Mar 19 at 5:48
add a comment |
Of course it's a bad idea to have an vector
of all the allocated nodes in your Tree
class. As you pointed-out, manipulating it to find and erase a Node
is slow (i.e. depends linearly on your tree size), and diminishes all the advantages your tree is supposed to have.
A first suggestion would be using std::unique_ptr<Node>
for your left_child
and right_child
members of your Node
. Then you'll not need the vector
to store all the nodes.
But in your specific implementation is not enough: you do nothing to ballance the tree, hence in worst-case its depth will grow linearly, hence the recursive cleanup will fail (stack overflow). You'll need a hybrid iterative-recursive cleanup.
But you can do this as a next step. First step - just get rid of the vector
.
Of course it's a bad idea to have an vector
of all the allocated nodes in your Tree
class. As you pointed-out, manipulating it to find and erase a Node
is slow (i.e. depends linearly on your tree size), and diminishes all the advantages your tree is supposed to have.
A first suggestion would be using std::unique_ptr<Node>
for your left_child
and right_child
members of your Node
. Then you'll not need the vector
to store all the nodes.
But in your specific implementation is not enough: you do nothing to ballance the tree, hence in worst-case its depth will grow linearly, hence the recursive cleanup will fail (stack overflow). You'll need a hybrid iterative-recursive cleanup.
But you can do this as a next step. First step - just get rid of the vector
.
edited Mar 22 at 17:46
Michael Veksler
5,3721724
5,3721724
answered Mar 19 at 5:33
valdovaldo
10.1k12956
10.1k12956
As I said, my first crack at this problem usedunique_ptr
for both left and right children, but I was told thatunique_ptr
conveyed "ownership." And it was suggested that the tree should do the owning. This specific implementation is just some example code using this ownership model. An AVL-type tree and proper destructors would probably be used in an actual implementation. Thank you for your thoughts.
– davidbear
Mar 19 at 5:41
2
Ok, then don't useunique_ptr
. Instead you'd need to implement the recursive deletion of yourNode
in theTree
class. But in either case usingvector
to store all the nodes just to "own" them is the worst idea.
– valdo
Mar 19 at 5:48
add a comment |
As I said, my first crack at this problem usedunique_ptr
for both left and right children, but I was told thatunique_ptr
conveyed "ownership." And it was suggested that the tree should do the owning. This specific implementation is just some example code using this ownership model. An AVL-type tree and proper destructors would probably be used in an actual implementation. Thank you for your thoughts.
– davidbear
Mar 19 at 5:41
2
Ok, then don't useunique_ptr
. Instead you'd need to implement the recursive deletion of yourNode
in theTree
class. But in either case usingvector
to store all the nodes just to "own" them is the worst idea.
– valdo
Mar 19 at 5:48
As I said, my first crack at this problem used
unique_ptr
for both left and right children, but I was told that unique_ptr
conveyed "ownership." And it was suggested that the tree should do the owning. This specific implementation is just some example code using this ownership model. An AVL-type tree and proper destructors would probably be used in an actual implementation. Thank you for your thoughts.– davidbear
Mar 19 at 5:41
As I said, my first crack at this problem used
unique_ptr
for both left and right children, but I was told that unique_ptr
conveyed "ownership." And it was suggested that the tree should do the owning. This specific implementation is just some example code using this ownership model. An AVL-type tree and proper destructors would probably be used in an actual implementation. Thank you for your thoughts.– davidbear
Mar 19 at 5:41
2
2
Ok, then don't use
unique_ptr
. Instead you'd need to implement the recursive deletion of your Node
in the Tree
class. But in either case using vector
to store all the nodes just to "own" them is the worst idea.– valdo
Mar 19 at 5:48
Ok, then don't use
unique_ptr
. Instead you'd need to implement the recursive deletion of your Node
in the Tree
class. But in either case using vector
to store all the nodes just to "own" them is the worst idea.– valdo
Mar 19 at 5:48
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f55234146%2fusing-raw-pointers-in-nodes-and-unique-ptr-in-trees%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
2
I came to the conclusion that using smart pointers to implement basic container types is likely as much trouble as it is worth. The container itself is a RAII object and it is probably simpler to write a cleanup constructor than figure out if your nodes contain pointers to nodes or pointers to smart pointers to nodes... or whatever.
– Galik
Mar 19 at 5:32
When people tell you that the tree should own the nodes, they usually mean what Galik suggested. While the
vector
's a good way to make sure the nodes are all freed when the tree is gone, you're no better off in the general case of freeing a node without destroying the tree. If you miss a case, or have a case where you forget to erase, you are almost back to where you started with detritus building up in thevector
. You might as well manuallydelete
.– user4581301
Mar 19 at 5:40