堆内存中的 C++ 向量导致分段错误

Question

我是 C++ 的新手，我相信这个问题一定很容易处理，但我想我错过了一些主要概念。在代码中，实现了一个二叉树，我们被要求确定该二叉树中的节点数。在Node class中可以看到，一个Node有两个成员指针：left指向左边的Node，right指向左边的Node指向右侧的节点。输入是根节点。无论如何，我找到了这样的解决方案：

制作一个节点向量，我在代码中将其命名为nodes，并附加根节点，并将节点数（代码中的howManyNodes）设置为1。
虽然节点不为空（一开始我们添加了根节点），检查它是否有left和right指针。如果它们可用（即不是 nullptr），将这些指针添加到节点向量（我使用 insert）。同时，将节点数（代码中的howManyNodes）增加一个。
检查特定节点是否具有左右指针后，我从列表中删除该节点，为此我使用 pop_back() 函数。
最后，向量将为空，我将获得 howManyNodes 作为答案。

代码如下，我只实现了计数功能。其余来自模板。

#include <iostream>
#include <vector>


class Node {
public:
  Node *left, *right;
  Node() { left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

// I implement this part
int count(Node *n) {

    int howManyNodes = 1;
    std::vector<Node> *nodes = new std::vector<Node>;
    nodes->push_back(*n);

    while (!nodes->empty()){

      Node* trial = new Node(nodes->back());
      if (trial->left){
          std::cout << trial->left << std::endl;
          nodes->insert(nodes->begin(), *trial->left);
          howManyNodes += 1;
      }
      if (trial->right){
          std::cout << trial->right << std::endl;
          nodes->insert(nodes->begin(), *trial->right);
          howManyNodes += 1;
      }
      nodes->pop_back();
  }
  return howManyNodes;
}
// I implement this part.


int main() {

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  // This should print a count of six nodes
  std::cout << count(n) << std::endl;

  // Deleting n is sufficient to delete the entire tree
  // because this will trigger the recursively-defined
  // destructor of the Node class.
  delete n;
  n = nullptr;

  return 0;
}

问题是，我永远无法摆脱分段错误。正如我搜索的那样，当代码试图访问它不应该访问的内存时，就会发生这种情况。我的代码可能很容易修复，但我有以下问题：

如果std::vector为其成员使用堆内存，为什么我需要在这里定义一个新的向量？ main函数里（不是我写的）都是new写的，然后我想我也应该尽可能使用new，但我不明白背后的逻辑。
在我的代码中，我想使用引用，因为我只想访问节点的指针而不是修改它们 - 我了解到使用对象本身需要制作副本并减慢进程，所以不是可取的 - .我的代码的哪一部分试图修改任何指针？
既然我定义了一个新的vector，我是否也应该删除它并使它等于nullptr，然后再返回值？

提前致谢！

Answer 1

你的 Node class 的问题在于它不遵循 the rule of 3/5/0 并且每当你制作 Node 的副本并且你正在制作很多副本，你有麻烦，因为一旦复制的对象超出范围，left right 节点将被删除，然后当你自己调用 delete 时再次删除。

count 实施中的错误简短摘要：

int count(Node *n) {
    int howManyNodes = 1;
    // doesn't make sense to allocate vector dynamically
    // also you forgot to delete it
    std::vector<Node> *nodes = new std::vector<Node>;
    // keeping nodes as value will copy them, which leeds to double free
    nodes->push_back(*n);
    while (!nodes->empty()){
      // another copy - thus another problem, but this time "only" a memory leak since you don't delete it
      Node* trial = new Node(nodes->back());
      if (trial->left){
          std::cout << trial->left << std::endl;
          // another copy
          nodes->insert(nodes->begin(), *trial->left);
          howManyNodes += 1;
      }
      if (trial->right){
          std::cout << trial->right << std::endl;
          // another copy
          nodes->insert(nodes->begin(), *trial->right);
          howManyNodes += 1;
      }
      nodes->pop_back();
  }
  return howManyNodes;
}

如何在不复制任何对象的情况下实现它：

void count(Node* n, int& numNodes)
{
  numNodes++;
  Node* left = n->left;
  Node* right = n->right;
  if (left) count(left, numNodes);
  if (right) count(right, numNodes);
}

int main() {

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();
  int numNodes{0};
  count(n, numNodes);
  std::cout << numNodes << std::endl;
  delete n;
  return 0;
}

这是一种递归方法，因此可能不是最好的方法。如果您真的需要手动实现某种树，请使用 std::unique_ptr，显式删除副本 constructor/assignment，并在 Tree [=31] 中实现方法 count =]，如果你打算拥有这样的东西。

Answer 2

正如@pptaszni 所解释的，在我的代码中，我正在制作实例的副本，这导致了问题。 @pptaszni 建议的递归方法更容易和更可取，这是我以前想不到的。我还通过传递指针而不是值来纠正我的方法。这有效：

#include <iostream>
#include <vector>


class Node {
public:
  Node *left, *right;
  Node() { left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};


int count(Node *n) {

    int howManyNodes = 1;
    std::vector<Node*> nodes = {};
    nodes.push_back(n);

    while (!nodes.empty()){

      Node* trial = nodes.back();
      if (trial->left){
          nodes.insert(nodes.begin(), trial->left);
          howManyNodes += 1;
      }
      if (trial->right){
          nodes.insert(nodes.begin(), trial->right);
          howManyNodes += 1;
      }
      nodes.pop_back();
  }

  // Implement count() here.

  return howManyNodes;
}

int main() {

  
  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  // This should print a count of six nodes
  std::cout << count(n) << std::endl;

  // Deleting n is sufficient to delete the entire tree
  // because this will trigger the recursively-defined
  // destructor of the Node class.
  delete n;
  n = nullptr;

  return 0;
}

堆内存中的 C++ 向量导致分段错误

C++ Vector in Heap Memory results in Segmentation Fault

c++

new-operator

heap-memory

stdvector