C++BST课程的五条规则

Question

>我正在实现一个二叉搜索树类，想知道我的移动/复制构造函数和赋值运算符是否正确实现。(它似乎工作正常，但这是我第一次实现这些构造函数和赋值运算符，恐怕我可能错过了一些东西。

这是代码(也在在线编译器中(： 编辑：这是基于@Alex拉里奥诺夫评论的更新代码：

#include <memory>
#include <iostream>
class BinarySearchTree {
public:
BinarySearchTree();
BinarySearchTree(int value);
BinarySearchTree(const BinarySearchTree& other_tree);
BinarySearchTree(BinarySearchTree&& other_tree);
BinarySearchTree& operator=(const BinarySearchTree& other_tree);
BinarySearchTree& operator=(BinarySearchTree&& other_tree);
~BinarySearchTree() = default;
void clear();
inline int size() const {
return tree_size;
}
inline bool empty() const {
return tree_size == 0;
}
private:
struct Node {
int val;
std::unique_ptr<Node> left = nullptr;
std::unique_ptr<Node> right = nullptr;
Node(const int value) :
val{value},
left{nullptr},
right{nullptr}
{}
};
std::unique_ptr<Node> root;
int tree_size;
void deep_copy_tree(std::unique_ptr<Node>& dest_node, const std::unique_ptr<Node>& source_node);
};

BinarySearchTree::BinarySearchTree() : root{nullptr}, tree_size{0} {
std::cout << "BinarySearchTree() constructorn";
}
BinarySearchTree::BinarySearchTree(int value) : root{std::make_unique<Node>(value)}, tree_size{1} {
std::cout << "BinarySearchTree(int value) constructorn";
}
BinarySearchTree::BinarySearchTree(const BinarySearchTree& other_tree) : root{nullptr}, tree_size{0} {
std::cout << "Copy constructorn";
if (other_tree.tree_size == 0) return;
tree_size = other_tree.tree_size;
deep_copy_tree(root, other_tree.root);
}
BinarySearchTree::BinarySearchTree(BinarySearchTree&& other_tree) :
root(std::exchange(other_tree.root, nullptr)), tree_size(std::exchange(other_tree.tree_size, 0)) {
std::cout << "Move constructorn";
}
BinarySearchTree& BinarySearchTree::operator=(const BinarySearchTree& other_tree) {
std::cout << "Copy assignment operatorn";
clear();
tree_size = other_tree.tree_size;
deep_copy_tree(root, other_tree.root);
return *this;
}
// EDIT: updated based on @Alex Larionov comment
BinarySearchTree& BinarySearchTree::operator=(BinarySearchTree&& other_tree) {
std::cout << "Move assignment operatorn";
clear();
tree_size = other_tree.tree_size;
other_tree.tree_size = 0;
root = std::move(other_tree.root);
return *this;
}
/*BinarySearchTree& BinarySearchTree::operator=(BinarySearchTree&& other_tree) {
std::cout << "Move assignment operatorn";
clear();
tree_size = other_tree.tree_size;
deep_copy_tree(root, other_tree.root);
other_tree.tree_size = 0;
other_tree.root = nullptr;
return *this;
}*/

void BinarySearchTree::clear() {
root = nullptr;
tree_size = 0;
}
void BinarySearchTree::deep_copy_tree(std::unique_ptr<Node>& dest_node, const std::unique_ptr<Node>& source_node) {
if (!source_node) return;
dest_node = std::make_unique<Node>(source_node->val);
deep_copy_tree(dest_node->left, source_node->left);
deep_copy_tree(dest_node->right, source_node->right);
}

int main()
{
BinarySearchTree myBST1(5);
BinarySearchTree myBST2 = myBST1; // copy constructor
BinarySearchTree myBST3(4);
myBST3 = myBST1; // copy assignment
std::cout << "myBST3.empty() before move: " << myBST3.empty() << 'n';
BinarySearchTree myBST4(std::move(myBST3)); // move constructor
std::cout << "myBST3.empty() after move: " << myBST3.empty() << 'n';
std::cout << "myBST4.empty() before move assignment: " << myBST4.empty() << 'n';
myBST2 = std::move(myBST4); // move assignment
std::cout << "myBST4.empty() after move assignment: " << myBST4.empty() << 'n';

return 0;
}

Answer 1

复制构造函数默认初始化，然后检查other_tree是否为空以避免深层复制它。但是您已经在deep_copy_tree进行了检查。为什么不直接初始化呢？

BinarySearchTree::BinarySearchTree(const BinarySearchTree& other_tree) : tree_size{other_tree.tree_size} {
std::cout << "Copy constructorn";
deep_copy_tree(root, other_tree.root);
}

为了更进一步，我会返回deep_copy_tree而不是采用 out 参数(并删除"_tree";它已经在"树"类中(。

std::unique_ptr<Node> BinarySearchTree::deep_copy(const std::unique_ptr<Node>& source_node) {
if (!source_node) return nullptr;
auto dest_node = std::make_unique<Node>(source_node->val);
dest_node->left = deep_copy(source_node->left);
dest_node->right = deep_copy(source_node->right);
return dest_node;
}

这样，您也可以在初始值设定项列表中初始化root。

BinarySearchTree::BinarySearchTree(const BinarySearchTree& other_tree) : root(deep_copy_tree(other_tree.root)), tree_size{other_tree.tree_size} {
std::cout << "Copy constructorn";
}

在移动构造函数中，不需要使用std::exchange。事实上，对于root，使用std::move(other_tree.root)做同样的事情(从unique_ptr移动是nullptrs(。

在复制分配运算符中，您可能希望检查自我分配。

if (this != &other_tree)

您也不需要任一赋值运算符中的clear，因为分配给unique_ptr实际上会破坏它所持有的值。