Правило пяти для класса BST в C++

Question

Я реализую класс двоичного дерева поиска, и мне было интересно, правильно ли реализованы мои конструкторы перемещения / копирования и операторы присваивания. (Кажется, все работает правильно, но я впервые использую эти конструкторы и операторы присваивания, боюсь, что я что-то пропустил.)

Вот код (также в онлайн-компиляторе): EDIT: вот обновленный код, основанный на комментарии @Alex Larionov:

#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() constructor\n";
}

BinarySearchTree::BinarySearchTree(int value) : root{std::make_unique<Node>(value)}, tree_size{1} {
    std::cout << "BinarySearchTree(int value) constructor\n";
}

BinarySearchTree::BinarySearchTree(const BinarySearchTree& other_tree) : root{nullptr}, tree_size{0} {
    std::cout << "Copy constructor\n";
    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 constructor\n";
}

BinarySearchTree& BinarySearchTree::operator=(const BinarySearchTree& other_tree) {
    std::cout << "Copy assignment operator\n";
    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 operator\n";
    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 operator\n";
    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 constructor\n";
    deep_copy_tree(root, other_tree.root);
}

Чтобы пойти дальше, я бы сделал deep_copy_tree return вместо того, чтобы принимать выходной параметр (а также отбрасывать "_tree"; он уже находится в классе "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 constructor\n";
}

В конструкторе перемещения вам не нужно использовать std::exchange. Фактически, дляroot, с помощью std::move(other_tree.root) делает то же самое (переехал из unique_ptrs есть nullptrс).

В операторе присваивания копий вы, вероятно, захотите проверить самоназначение.

if (this != &other_tree)

Вам также не нужен clear в любом из операторов присваивания, поскольку присвоение unique_ptr эффективно разрушает ценность, которую он удерживал.