jeudi 1 janvier 2015

unique_ptr in class how to work with them

I am implementing AVL tree in C++ and using unique_ptr for children.



struct Node
{
const int key;
std::unique_ptr<Node> left, right;
std::size_t height; ///< for avl tree.
Node(const int key) : key(key), height(0) {}
};

class AVL
{
std::unique_ptr<Node> root;
public:
AVL(int rootKey) : root(std::unique_ptr<Node>(new Node(rootKey))) {
}

void insert(std::unique_ptr<Node> newNode) {
std::unique_ptr<Node> & node = root;
std::weak_ptr<Node> parentWeak;
while(node.get()) {
parentWeak = node->parent;
if (node->key == newNode->key)
throw std::runtime_error("Key already present");
if (node->key < newNode->key)
node = node->right;
else
node = node->left;
}

std::unique_ptr<Node> & parent = parentWeak.lock();
const int key = newNode->key;

if (parent == nullptr) {
// there is no root
root = std::move(newNode);
} else {
if (parent->key < newNode->key) {
assert(NULL == parent->right.get());
parent->right = std::move(newNode);
} else {
assert(NULL == parent->left.get());
parent->left = std::move(newNode);
}
}

// Now increment the height upto down.
incrementHeight(key);
// balance starting from parent upwards untill we find some dislanace in height
balance(parent, key);
}
};


I am getting compiler errors on line node = node->right;. Which is right because it can be possible with only std::move semantics. but that would be wrong because i want to just iterate over the tree, otherwise it would just remove them from the child-list.


However, i need the unique_ptr also, as it would passed in function balance as it would modify the pointers and re-balance the tree.


If i use shared_ptr it would all work. However, i do not need to share the ownership with others. Or am i misunderstanding ownership ?


Aucun commentaire:

Enregistrer un commentaire