堆内存中的 C++ 向量导致分段错误
C++ Vector in Heap Memory results in Segmentation Fault
我是 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,然后再返回值?
提前致谢!
你的 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
=],如果你打算拥有这样的东西。
正如@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++ 的新手,我相信这个问题一定很容易处理,但我想我错过了一些主要概念。在代码中,实现了一个二叉树,我们被要求确定该二叉树中的节点数。在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,然后再返回值?
提前致谢!
你的 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
=],如果你打算拥有这样的东西。
正如@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;
}