C++ - GDB Error Question

I'm working on a Binary Search Tree in C++. I'm getting the following errors reported after running gdb (I'm receiving a segfault) on my program:

#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

The #0 error refers to my getLeft() function, which is as follows:

    template <typename T>
    inline tree_node&l开发者_运维知识库t;T>* tree_node<T>::getLeft() const
    {
        return tree_node<T>::left_; //note that left_ is of type tree_node<T>*
    }

The #1 error refers to my operator++ defined in my iterators, which is as follows:

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

The #2 error refers to my main program, in which I am including the file that contains my definitions for tree_node, binaryTree, bst_iter, and bst_citer (which does not exist at this point, so not an issue).

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

I'm not entirely sure what's causing the error. I believe that ++() is trying to access an area that has not been defined, but I'm not really sure why it's doing that or how to stop it...I tried to hold back on the code, as the code is almost 800 lines long, but if more information is required, let me know...

How are you initializing your for loop iterator i? If it's invalid to begin with, then that would explain things.

This could happen if pos_->getRight() returns a null pointer.

Since you are calling getLeft on the result without checking it for null, you end up with a this pointer that is null.

As you can see in the gdb back trace, you end up calling getLeft() on a NULL pointer. i.e. its this pointer is NULL.

In your loop inside the operator++, you call getLeft() on p without first checking if it's NULL. i.e. if getRight() returns NULL, you'll crash.

You probably want to do something like this:

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

This is not a complete fix though. It depends a bit on what your end() state of the iterator is supposed to be.

However, it seems like there are more efficient and more intuitive ways of implementing operator++. STL for instance lets you delete entries in a tree and only invalidating iterators pointing to that node. In your case, all iterators would have to be invalidated.