关于 std::堆栈推送的分段错误的问题

Question

我正在研究八叉树遍历算法。当前的实现为此目的使用std::queue，完美运行。但是，我想使用这种遍历std::stack，因为深度优先搜索将提供更好的性能，避免测试不需要的节点。

但是，当从一种结构更改为另一种结构时，我开始在push()函数上出现分段错误。以下是来自gdb的堆栈报告：

0x00005555555ae28d in __gnu_cxx::new_allocator<voxelizer::Node*>::construct<voxelizer::Node*, voxelizer::Node* const&> (this=0x7fffffffd7f0, __p=0x5555559abde8, __args#0=<error reading variable>)
at /usr/include/c++/7/ext/new_allocator.h:136
136     { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
(gdb) up
#1  0x00005555555acd1c in std::allocator_traits<std::allocator<voxelizer::Node*> >::construct<voxelizer::Node*, voxelizer::Node* const&> (__a=..., __p=0x5555559abde8, __args#0=<error reading variable>)
at /usr/include/c++/7/bits/alloc_traits.h:475
475     { __a.construct(__p, std::forward<_Args>(__args)...); }
(gdb) up
#2  0x00005555555ab63e in std::deque<voxelizer::Node*, std::allocator<voxelizer::Node*> >::push_back (this=0x7fffffffd7f0, __x=<error reading variable>) at /usr/include/c++/7/bits/stl_deque.h:1547
1547            _Alloc_traits::construct(this->_M_impl,
(gdb) up
#3  0x00005555555aa29f in std::stack<voxelizer::Node*, std::deque<voxelizer::Node*, std::allocator<voxelizer::Node*> > >::push (this=0x7fffffffd7f0, __x=<error reading variable>)
at /usr/include/c++/7/bits/stl_stack.h:226
226       { c.push_back(__x); }

我无法理解为什么，所以我创建了一个最小的、可验证的示例，我可以摆脱由系统的任何其他部分引起的可能错误。我重现了 cotree 节点结构，并创建了一个小树来遍历：

#include <iostream>
#include <stack>
#include <utility>
using namespace std;
// ==============================================================
class TestClass
{
public:
// Default constructor
TestClass()
: d(0)
, children(nullptr)
{
}
// Depth based constructor
TestClass(int d_)
: d(d_)
, children(nullptr)
{
if(d > 0)
{
children = new TestClass*[8];
for(int i = 0; i < 8; i++)
{
children[i] = new TestClass(d - 1);
}
}
}
// Copy  constructor
TestClass(const TestClass & other_)
: d(0)
, children(nullptr)
{
_copy(other_);
}
// Move constructor
TestClass(TestClass && other_)
: d(0)
, children(nullptr)
{
_move(std::move(other_));
}
// Destructor
~TestClass()
{
_clearChildren();
}
// Copy assignment operator
TestClass & operator= (const TestClass & other_)
{
_copy(other_);
return *this;
}
// Move assignment operator
TestClass & operator= (TestClass && other_)
{
_move(std::move(other_));
return *this;
}
int depth()
{
return d;
}
TestClass ** getChildren()
{
return children;
}
private:
void _clearChildren()
{
if(children != nullptr)
{
for(int i = 0; i < 8; i++)
{
delete children[i];
}
delete[] children;
children = nullptr;
}
}
void _copy(const TestClass & other_)
{
d = other_.d;
_clearChildren();
if(other_.children != nullptr)
{
children = new TestClass*[8];
for(int i = 0; i < 8; i++)
{
children[i] = new TestClass(*(other_.children[i]));
}
}
}
void _move(TestClass && other_)
{
d = other_.d;
_clearChildren();
children = std::move(other_.children);
}
private:
int d;
TestClass ** children;
};
// ==============================================================
typedef TestClass * TestClassPtr;
// ==============================================================
int main(int argc, char ** argv)
{
TestClassPtr test = new TestClass(5);
stack<TestClassPtr> s;
s.push(test);
while(!s.empty())
{
TestClassPtr & next = s.top();
s.pop();
cout << "On depth " << next->depth() << endl;
if(next->getChildren() != nullptr)
{
std::cout << "Adding children" << std::endl;
for(int i = 0; i < 8; i++)
{
if(next->getChildren()[i]->getChildren() != nullptr)
{
s.push(next->getChildren()[i]);
}
}
}
}
cout << "Done" << endl;
return 0;
}

通过运行它，我也能够以push()方法重现问题：

On depth 5
Adding children
On depth 3
Adding children
On depth 1
Adding children
Segmentation fault

所以我继续修改文档。请注意，我使用的是 C++11。默认std::stack的要求可以从使用std::deque的要求继承而来，因为它是使用的默认容器。从 C++11 开始，主要要求是完整的类型和可擦除的我确保析构函数是可访问的。此外，为了安全证明，我实现了默认构造函数、复制构造函数、移动构造函数、复制赋值和移动赋值。

所以我相信我的课程是可擦除的，但也许不完整。通过修改示例中的遍历循环并添加"安全证明线"，如果：

if(next->getChildren() != nullptr)
{
std::cout << "Adding children" << std::endl;
for(int i = 0; i < 8; i++)
{
// SAFE PROOF LINE
if(next->getChildren()[i]->getChildren() != nullptr)
{
s.push(next->getChildren()[i]);
}
}
}

我能够摆脱分段错误。此行丢弃的节点是叶节点，它没有子节点，因此它们的children变量是nullptr。

我的问题：

• 这是否意味着nullptr指针使类型不完整？

• 使用这个原始内存双指针的重点是尽可能安全 尽可能记住，无论如何我可以让它工作而没有 将其替换为堆栈数组或std::vector？

谢谢。

Answer 1

似乎从一开始就出错了

while(!s.empty())
{
TestClassPtr & next = s.top();
s.pop();

next是对堆栈顶部对象的引用，但下一行会删除该对象，因此引用将变为无效。

简单的答案是不使用引用，只需复制堆栈的顶部。

while(!s.empty())
{
TestClassPtr next = s.top();
s.pop();

Answer 2

gdb 表示push参数无效：

push (this=0x7fffffffd7f0, __x=<error reading variable>)