破坏时的神秘分割故障

Question

在歌曲"上帝在LISP代码中写道"中,他们说"只有上帝才能在C(或C++)中创造一棵树"; 我开始相信了.

我有一个树类的开头,但是我的类在破坏时发生了段错误,说错误是我的队列free_spaces,虽然我不明白为什么.此外,随机错误似乎潜伏在这里和那里.

我之前从未使用过这样的模板,所以也许会有一些隐藏的滥用行为.

任何帮助,将不胜感激.

header.h

#include<vector>
#include<queue>
#include<iostream>
using namespace std;

template <class T>
class node {
    public:
        int leftChild,parent;
        bool empty;
        T data;
        node() : leftChild(-1), parent(-1), empty(true) {}
};

template <class T>
class AvlTree {
    private:
        vector< node<T> > nodes;
        queue<int> free_spaces;
        int root;

        int newnode(int parent){
            int index=nodes.size();
            nodes.push_back(node<T>());
            nodes[index].parent=parent;
            return index;
        }

    public:
        AvlTree(){
            nodes.push_back(node<T>());
            root=0;
        }

        void grow(){
            nodes[root].leftChild=newnode(root);
        }
};

main.h

#include "header.h"

int main(){
    AvlTree<int> bob;
    bob.grow();
    cerr<<"Made it to end."<<endl;
}

Answer 1

问题在于以下代码行:

nodes[parent].leftChild=newnode(parent);

只需将其替换为此修复它:

int left = newnode(parent);
nodes[parent].left = left;

这最终归结为评估的顺序.问题是该newnode()函数修改了向量长度.这样做可能会强制std::vector<>重新分配内存以便增长(即,如果当前容量不够).如果您遇到这种情况,nodes[parent].left左侧的表达式(如果在newnode()调用之前进行评估)将指向可能无效的内存位置.