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;








0















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.










share|improve this question

















  • 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 the vector. You might as well manually delete.

    – user4581301
    Mar 19 at 5:40

















0















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.










share|improve this question

















  • 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 the vector. You might as well manually delete.

    – user4581301
    Mar 19 at 5:40













0












0








0








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.










share|improve this question














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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










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 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












  • 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 the vector. You might as well manually delete.

    – 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












2 Answers
2






active

oldest

votes


















1














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;
;





share|improve this answer

























  • 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











  • 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












  • 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


















0














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.






share|improve this answer

























  • 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





    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











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
);



);













draft saved

draft discarded


















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









1














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;
;





share|improve this answer

























  • 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











  • 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












  • 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















1














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;
;





share|improve this answer

























  • 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











  • 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












  • 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













1












1








1







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;
;





share|improve this answer















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;
;






share|improve this answer














share|improve this answer



share|improve this answer








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 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











  • 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












  • 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

















  • 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











  • 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












  • 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
















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













0














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.






share|improve this answer

























  • 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





    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















0














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.






share|improve this answer

























  • 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





    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













0












0








0







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.






share|improve this answer















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.







share|improve this answer














share|improve this answer



share|improve this answer








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 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





    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

















  • 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





    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
















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

















draft saved

draft discarded
















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Kamusi Yaliyomo Aina za kamusi | Muundo wa kamusi | Faida za kamusi | Dhima ya picha katika kamusi | Marejeo | Tazama pia | Viungo vya nje | UrambazajiKuhusu kamusiGo-SwahiliWiki-KamusiKamusi ya Kiswahili na Kiingerezakuihariri na kuongeza habari

SQL error code 1064 with creating Laravel foreign keysForeign key constraints: When to use ON UPDATE and ON DELETEDropping column with foreign key Laravel error: General error: 1025 Error on renameLaravel SQL Can't create tableLaravel Migration foreign key errorLaravel php artisan migrate:refresh giving a syntax errorSQLSTATE[42S01]: Base table or view already exists or Base table or view already exists: 1050 Tableerror in migrating laravel file to xampp serverSyntax error or access violation: 1064:syntax to use near 'unsigned not null, modelName varchar(191) not null, title varchar(191) not nLaravel cannot create new table field in mysqlLaravel 5.7:Last migration creates table but is not registered in the migration table

은진 송씨 목차 역사 본관 분파 인물 조선 왕실과의 인척 관계 집성촌 항렬자 인구 같이 보기 각주 둘러보기 메뉴은진 송씨세종실록 149권, 지리지 충청도 공주목 은진현