3

"God Wrote in LISP Code" という歌の中で、彼らは C (または C++) で「神だけが木を作ることができる」と言っています。私は信じ始めました。

free_spaces私はツリークラスの始まりを持っていますが、理由はわかりませんが、私のクラスは破壊時にエラーが my the queue であると言ってセグメンテーション違反を起こします。さらに、ランダムなバグがあちこちに潜んでいるようです。

私はこれまでこのようなテンプレートを使用したことがないので、隠れた悪用が行われている可能性があります。

どんな助けでも大歓迎です。

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;
}
4

2 に答える 2

5

問題は次のコード行にあります。

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

これを置き換えるだけで修正されます：

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

これは最終的に評価の順序に要約されます。問題は、newnode()関数がベクトルの長さを変更することです。これを行うと、拡張std::vector<>するためにメモリの再割り当てが必要になる場合があります (つまり、現在の容量が十分でない場合)。その場合、nodes[parent].left左側の式は、newnode()呼び出しの前に評価されると、潜在的に無効なメモリ位置を指します。

于 2012-12-10T01:18:41.563 に答える
0

Valgrind には次のエラーが表示されます。

==23995== Invalid write of size 4
==23995==    at 0x400F68: AvlTree<int>::grow() (/tmp/header.h:39)
==23995==    by 0x400BC6: main (/tmp/t.cc:5)
==23995==  Address 0x5967770 is 0 bytes inside a block of size 16 free'd
==23995==    at 0x4C29DFD: operator delete(void*) (/coregrind/m_replacemalloc/vg_replace_malloc.c:456)
==23995==    by 0x401FC5: __gnu_cxx::new_allocator<node<int> >::deallocate(node<int>*, unsigned long) (/usr/include/c++/4.4/ext/new_allocator.h:95)
==23995==    by 0x40187B: std::_Vector_base<node<int>, std::allocator<node<int> > >::_M_deallocate(node<int>*, unsigned long) (/usr/include/c++/4.4/bits/stl_vector.h:146)
==23995==    by 0x401743: std::vector<node<int>, std::allocator<node<int> > >::_M_insert_aux(__gnu_cxx::__normal_iterator<node<int>*, std::vector<node<int>, std::allocator<node<int> > > >, node<int> const&) (/usr/include/c++/4.4/bits/vector.tcc:361)
==23995==    by 0x40106B: std::vector<node<int>, std::allocator<node<int> > >::push_back(node<int> const&) (/usr/include/c++/4.4/bits/stl_vector.h:741)
==23995==    by 0x40131A: AvlTree<int>::newnode(int) (/tmp/header.h:24)
==23995==    by 0x400F67: AvlTree<int>::grow() (/tmp/header.h:39)
==23995==    by 0x400BC6: main (/tmp/t.cc:5)

バグを見つけるにはこれで十分です。

于 2012-12-10T01:04:22.247 に答える