了解 clang-tidy "DeadStores" 和 "NewDeleteLeaks" 警告

Question

我对 C++ 编程比较陌生，尤其是在处理 OOP 和指针时。

我正在尝试实现二叉搜索树，这是我的代码

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;

  TreeNode() : val(0), left(NULL), right(NULL){};
  TreeNode(int v) : val(v), left(NULL), right(NULL){};
  TreeNode(int v, TreeNode* l, TreeNode* r) : val(v), left(l), right(r){};
};

void insert(TreeNode* root, TreeNode* v) {
  // inserts v into root, assuming values distinct
  if (root == NULL) {
    root = v; // L52
    return;
  }
  if (v == NULL) {
    return;
  }

  // traverse through tree using structure of BST
  TreeNode* cur = root;
  while (cur != NULL) {
    if (cur->val <= v->val) {
      if (cur->right == NULL) {
        cur->right = new TreeNode(v->val);
        break;
      }
      cur = cur->right;
    } else if (cur->val >= v->val) {
      if (cur->left == NULL) {
        cur->left = new TreeNode(v->val);
        break;
      }
      cur = cur->left;
    }
  }
}

void insert(TreeNode* root, int v) {
  insert(root, new TreeNode(v)); // L78
}

现在，我有两个个问题。

我发现上面标注的L52不行。例如，如果我做 TreeNode* node = new TreeNode(5); TreeNode* empty = NULL; insert(empty, node);，它就不会起作用。我不确定如何解决这个问题，所以任何帮助都会很棒。
运行 clang-tidy 在我的代码上，我收到以下稍微令人困惑的警告：

./main.cpp:78:69: warning: Potential memory leak [clang-analyzer-cplusplus.NewDeleteLeaks]
void insert(TreeNode* root, int v) { insert(root, new TreeNode(v)); }
                                                                    ^
./main.cpp:132:3: note: Calling 'insert'
  insert(node, 3);
  ^
./main.cpp:78:51: note: Memory is allocated
void insert(TreeNode* root, int v) { insert(root, new TreeNode(v)); }
                                                  ^
./main.cpp:78:69: note: Potential memory leak
void insert(TreeNode* root, int v) { insert(root, new TreeNode(v)); }
                                                                    ^

我不确定这意味着什么，也不知道它是否有任何危险。我从 LLVM 文档中找到了 this，似乎临时 new TreeNode(v) 导致了问题。什么是实现我想要的更好的方法？如果我能阅读任何进一步的解释或资源，那就太好了。

当然，对我糟糕的编码风格的任何改进也会很棒 ;) 格式化程序挽救了这一天。

谢谢！

Answer 1

Q1：如何插入二叉树？

片段的主要问题：

void insert(TreeNode* root, TreeNode* v) {
  // inserts v into root, assuming values distinct
  if (root == NULL) {
    root = v; // L52
    return;
  }

是，虽然你为root设置了一个新值，root是insert函数的一个参数，因此当insert returns.

解决此问题的一种方法是 return 新值：

TreeNode*             // <-- changed return type
    insert(TreeNode* root, TreeNode* v) {
  // inserts v into root, assuming values distinct
  if (root == NULL) {
    root = v; // L52
    return root;      // <---- changed to return a value
  }

每一处insertreturns（包括末尾），return的值为root.

然后当您调用 insert 时，保存 returned 值：

TreeNode* root = ...;       // some existing tree
root = insert(root, 5);     // insert 5 and save the result

现在，root 的新值指向包含插入值的树。

Q2：clang-tidy抱怨什么？

调用new分配内存。它最终必须被释放，否则（如果这种情况持续发生）您的程序最终将使用所有可用内存。参见问题 When should I use the new keyword in C++?。特别注意这个建议：“每次你键入 new，键入 delete。”

现在，在目前的代码中，问题实际上不是缺少 delete，而是未能 return 更新 root。 clang-tidy 意识到，因为更新的 root 永远不会 returned，所以你最终不可能 delete 它，所以抱怨。一旦您开始 return 使用该值，clang-tidy 将等着看您接下来要做什么。

至于下一步怎么办，一种简单的做法是将TreeNode视为拥有其children，即有义务delete 他们被摧毁时。比如先在TreeNode:

中添加一个destructor方法

struct TreeNode {
  ...
  ~TreeNode() {        // <--- this is the destructor
    delete left;       // free left child (if not NULL)
    delete right;      // free right child
  }
};

然后在你操作树的代码中，记得 delete 完成后的根节点：

TreeNode* root = NULL;
root = insert(root, 1);
root = insert(root, 2);
delete root;            // <--- free entire tree

关于智能指针的说明

我上面的建议使用了一种非常直接的文字风格的内存管理，在需要的地方明确使用 new 和 delete。但是，很容易忘记使用 delete，并且在出现异常时很难正确使用它。通常首选的替代方法是使用 smart pointers。但这是一个有点高级的话题，所以刚开始时，我建议首先熟悉显式 new 和 delete，但请记住，当你准备好时，还有更好的方法。

了解 clang-tidy "DeadStores" 和 "NewDeleteLeaks" 警告

Understanding clang-tidy "DeadStores" and "NewDeleteLeaks" warnings

c++

clang-format

clang-tidy

Q1：如何插入二叉树？

Q2：clang-tidy抱怨什么？

关于智能指针的说明