Использование интеллектуальных указателей для двоичного дерева поиска С++

Я реализовал двоичное дерево поиска в С++. Вместо того, чтобы использовать указатели на указатели на дочерние узлы, я использовал std::shared_ptr. Узлы дерева реализованы следующим образом:

struct treeNode;
typedef std::shared_ptr<treeNode> pTreeNode;

struct treeNode {
    T key;
    pTreeNode left;
    pTreeNode right;
    treeNode(T key) : key(key), left(nullptr), right(nullptr) {}
};

При удалении node из BST один из случаев - когда node имеет только один ребенок. node просто заменяется этим дочерним элементом, как показано ниже:

             |        remove node                  
            node      --------->     |
               \                    right 
              right

В подобной реализации Java это может быть закодировано как:

node = node.getRight();

В моей реализации на С++ это:

node = node->right;

где node имеет тип pTreeNode.

При вызове оператора = на pTreeNode (std::shared_ptr<TreeNode>) будет вызываться деструктор node. Количество общих указателей, указывающих на базовый TreeNode, равно 1, поэтому TreeNode уничтожается, освобождая его память. Когда вызывается деструктор TreeNode (по умолчанию), каждый из его членов уничтожается. Это, несомненно, приведет к уничтожению члена pTreeNode right. Проблема в том, что node->right - это то, что присваивается node. При тестировании моего BST он работает нормально, без ошибок/утечек памяти.

  • Что я делаю небезопасно?
  • Если это небезопасно, что я могу сделать, чтобы обойти эту проблему?

"Хак", который, как я полагал, может работать, будет заключаться в том, чтобы сделать еще один указатель, чтобы увеличить счетчик ссылок. Будет ли это адекватным решением?

//increase reference to node->right by 1 so it doesn't get destroyed
pTreeNode temp(node->right);
node = node->right;

Ответы

Ответ 1

Вы, по-видимому, предполагаете, что в

node = right;
Оператор присваивания

shared_ptr может уменьшить счетчик node до завершения чтения из right (или до увеличения количества ссылок, используемого right). Однако, согласно cppreference, используя

template<typename T>
template<typename U>
std::shared_ptr<T> &std::shared_ptr<T>::operator =(const std::shared_ptr<U> &);

а

node = right; // std::shared_ptr<treeNode>

эквивалентно

std::shared_ptr<treeNode>(right).swap(node);

что безопасно, потому что right копируется до того, как старое значение node будет уничтожено. В стороне я сам реализовал общий указатель, и я увидел, что "очистка" старого значения - это последнее, что я делаю внутри operator =, чтобы избежать таких проблем.

Ответ 2

  • Что я делаю небезопасно?

Нет, это безопасно, насколько я могу видеть. Экземпляры left или right node будут сохранены до тех пор, пока их количество ссылок не упадет до нуля.

  • Если это небезопасно, что я могу сделать, чтобы обойти эту проблему?

Единственное, что вам нужно знать, это не раздавать любые узлы как shared_ptr вне реализации дерева. Они должны быть std::weak_ptr или необработанные указатели.