C++ — вопрос об ошибке GDB

Я работаю над двоичным деревом поиска на С++. Я получаю следующие сообщения об ошибках после запуска gdb (я получаю segfault) в моей программе:

#0  0x08049058 in searchTree::tree_node<int>::getLeft (this=0x0) at bst.hxx:75
#1  0x08048ed8 in searchTree::bst_iter<int>::operator++ (this=0xbffff4b4) at bst.hxx:586
#2  0x08048a72 in main () at projectmain.cxx:29

Ошибка #0 относится к моей функции getLeft(), которая выглядит следующим образом:

    template <typename T>
    inline tree_node<T>* tree_node<T>::getLeft() const
    {
        return tree_node<T>::left_; //note that left_ is of type tree_node<T>*
    }

Ошибка № 1 относится к моему оператору ++, определенному в моих итераторах, который выглядит следующим образом:

        bst_iter<T>& operator++()
        { //note that s is a stack of tree_node<T>*
            tree_node<T> *p = pos_->getRight();
            s.push(p);
            for(p=p->getLeft(); p!=NULL; p=p->getLeft())
            {
                s.push(p);
            }
            pos_ = s.top();
            s.pop();
            return *this;
        }

Ошибка № 2 относится к моей основной программе, в которую я включаю файл, содержащий мои определения для tree_node, binaryTree, bst_iter и bst_citer (которого на данный момент не существует, так что это не проблема).

                            bst_iter<int> i = treeTime.begin(); //treeTime is our tree
            bst_iter<int> iEnd = treeTime.end();
                            for(; i != iEnd ;++i) //crash
            {
                cout<<*i<<" ";
            }

        template <typename T>
        inline bst_iter<T> binaryTree<T>::begin()
         {

             return bst_iter<T>(root_);
         }

        template <typename T>
        inline bst_iter<T> binaryTree<T>::end()
         {
            return bst_iter<T>(0);
         }

Я не совсем уверен, что вызывает ошибку. Я считаю, что ++() пытается получить доступ к области, которая не была определена, но я не совсем уверен, почему он это делает или как это остановить... Я пытался сдержать код, так как код содержит почти 800 строк, но если потребуется дополнительная информация, дайте мне знать...


c++ iterator binary-search-tree
person muttley91    schedule 05.04.2011    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Как вы инициализируете свой итератор цикла for i? Если это недействительно с самого начала, тогда это все объясняет.

person nsanders    schedule 05.04.2011
comment
поэтому, когда вы делаете p->getRight().... вы проверяете, что правильный дочерний элемент не равен нулю? В вашем коде, вставленном выше, вы просто стреляете прямо в его использование. Другая идея состоит в том, чтобы ткнуть в свой стек, чтобы посмотреть, что там происходит. - person nsanders; 05.04.2011

arrow_upward
0
arrow_downward

Это может произойти, если pos_->getRight() возвращает нулевой указатель.

Поскольку вы вызываете getLeft для результата, не проверяя его на нуль, вы получаете указатель this, который равен нулю.

person xDD    schedule 05.04.2011

arrow_upward
0
arrow_downward

Как видно из обратной трассировки gdb, в конечном итоге вы вызываете getLeft() для указателя NULL. то есть его указатель this равен NULL.

В вашем цикле внутри operator++ вы вызываете getLeft() на p без предварительной проверки, является ли он NULL. т. е. если getRight() возвращает NULL, произойдет сбой.

Вы, вероятно, хотите сделать что-то вроде этого:

bst_iter<T>& operator++()
    { //note that s is a stack of tree_node<T>*
        tree_node<T> *p = pos_->getRight();
        if (p == NULL) p = pos_;
        else s.push(p);
        for(p=p->getLeft(); p!=NULL; p=p->getLeft())
        {
            s.push(p);
        }
        // TODO: what if s is empty?
        pos_ = s.top();
        s.pop();
        return *this;
    }

Однако это не полное исправление. Это немного зависит от того, каким должно быть ваше end() состояние итератора.

Однако, похоже, есть более эффективные и интуитивно понятные способы реализации operator++. Например, STL позволяет вам удалять записи в дереве и аннулировать только итераторы, указывающие на этот узел. В вашем случае все итераторы должны быть признаны недействительными.

person Arvid    schedule 05.04.2011
comment
Внесение этого изменения немного исправило ошибку, но теперь я нашел другую в pos_ = s.top() ближе к концу. Используя gdb, я получил следующую информацию для s.top(): $1 = (class searchTree::tree_node‹int› *&) @0x1fc: ‹переменная ошибки чтения› - person muttley91; 05.04.2011
comment
кажется, что вы проходите только по левому поддереву на всех узлах. Я предполагаю, что намерение состоит в том, чтобы сначала выполнить поиск в глубину через ваши узлы, но затем вам также нужно пройти вниз вправо. Кроме того, я бы посоветовал вместо создания стека внутри оператора ++ привязываться к листовым узлам. Следуйте простому порядку поиска в глубину и прыгайте между листьями вашего дерева. - person Arvid; 05.04.2011