Должен ли я переместить unique_pointer или я должен отправить указатель на unique_pointer? - PullRequest
Новая
       49

Должен ли я переместить unique_pointer или я должен отправить указатель на unique_pointer?

0 голосов
/ 06 января 2019

Я пишу реализацию языка BST на c ++, используя std :: unique_ptr.

Я программист-любитель. Первоначально я написал функцию вставки, используя вспомогательную функцию и передавая указатель, используя семантику перемещения, но это заставило меня вернуть unique_ptr. Затем я рассмотрел передачу указателя на unique_ptr. Я даже рассмотрел использование unique_ptr :: get () и отправку указателя на binaryNode, но я прочитал, что эту функцию следует использовать только при взаимодействии с унаследованными функциями (реализация не показана). 

template<class K, class V = char>
struct binaryNode
{
    using nodePtr = std::unique_ptr<binaryNode<K, V>>;
    using keyType = K;
    using valueType = V;

    binaryNode(keyType key, valueType val) : _key(key), _value(val) {};
    binaryNode(const binaryNode& n) = delete;
    ~binaryNode() = default;

    keyType _key = keyType();
    valueType _value = valueType();
    nodePtr l_node = nullptr;
    nodePtr r_node = nullptr;
};

template<class K, class V = char>
class BSTree
{
public:
    using nodePtr = std::unique_ptr<binaryNode<K, V>>;
    using keyType = K;
    using valueType = V;

    BSTree() {}
    void insert(const keyType & key, const valueType & value);
    void insert2(const keyType & key, const valueType & value);

private:
    nodePtr insertHelper(nodePtr && root, const K & key, const V & value);
    void insertHelper2(nodePtr * root, const K & key, const V & value);

    nodePtr _root = nullptr;
};

template<class K, class V>
void BSTree<K, V>::insert(const keyType & key)
{
    _root = insertHelper(std::move(_root), key);
    if (!isBalanced(_root)) _root = rebalance(std::move(_root));
}

template<class K, class V>
typename BSTree<K, V>::nodePtr BSTree<K, V>::insertHelper(nodePtr && root, const keyType & key, const valueType & value)
{
    if (root == nullptr) return std::make_unique<binaryNode<K, V>>(std::move(binaryNode<K, V>(key)));

    if (key < root->_key) root->l_node = insertHelper(std::move(root->l_node), key, value);
    if (key > root->_key) root->r_node = insertHelper(std::move(root->r_node), key, value);

    return std::move(root);
}

template<class K, class V>
void BSTree<K, V>::insert2(const keyType & key, const valueType & value)
{
    insertHelper2(&_root, key, value);
    if (!isBalanced(_root)) _root = rebalance(std::move(_root));
}

template<class K, class V>
void BSTree<K, V>::insertHelper2(nodePtr * root, const K & key, const V & value)
{
    if (*root == nullptr) *root = std::make_unique<binaryNode<K, V>>(std::move(binaryNode<K, V>(key, value)));

    if (key < (*root)->_key) insertHelper(&((*root)->l_node), key, value);
    if (key > (*root)->_key) insertHelper(&((*root)->r_node), key, value);
}

Функционально эти два подхода дают одинаковые древовидные структуры. Я не пробовал выбрать время для двух подходов, но мне любопытно, какой из этих подходов считается «правильным»? Или есть лучший подход, о котором я не думал?

РЕДАКТИРОВАТЬ: опечатки исправлены

...