-1

So I'm trying to write a function that places all of the values of a binary tree into a vector, which will later be used to recreate it. But when I try to call this function, I get an error:

Error in `./bst': double free or corruption (fasttop):

This is the function I'm using. The vector itself is a private variable containing nodes. size() returns the size of the tree and is working.

void BST::swapvector()
{
    Node *ptr = m_root;
    while (size() != 0)
    {
        if (ptr->m_left != NULL) {
            ptr = ptr->m_left;
        } else if (ptr->m_right != NULL) {
            ptr = ptr->m_right;
        } else {
            Node *temp = ptr;
            myvector.push_back(ptr); //starting from root, we traverse until we reach the bottom and then add ptr to the vector
            ptr = m_root;
            delete temp; //once we're finished, we delete temp
        }
    }
}

Does anyone know why this isn't working? Thanks!

4
  • 2
    How is myvector defined? Apr 25, 2018 at 20:12
  • Is it okay that myvector contains a list of deleted pointers? If you delete the pointers in myvector later, you essentially delete them twice. Apr 25, 2018 at 20:20
  • 1
    1) You should store the data that the tree represents in the vector, not the pointers. The pointers are just an implementation detail of the BST, it should have nothing to do with the vector. 2) The BST should have a clear() or similar function to get rid of all the pointers -- this would prevent the need of deleting the pointers one-by-one in the swap function. Apr 25, 2018 at 20:29
  • In addition to the other comments, it's well worth learning to use valgrind or your compiler's address sanitizer to diagnose this sort of error.
    – Useless
    Apr 25, 2018 at 21:06

2 Answers 2

4

It's obvious why this isn't working.

    } else {
        Node *temp = ptr;
        myvector.push_back(ptr); //starting from root, we traverse until we reach the bottom and then add ptr to the vector
        ptr = m_root;
        delete temp; //once we're finished, we delete temp
    }

You're storing a pointer to Node into vector and then deleting that Node with delete temp. After that pointer stored into vector points to garbage or non-existent memory.

"...a function that places all of the values of a binary tree into a vector..." No, you're not storing binary tree values, you're storing pointers to binary tree values (Node objects).

There are two things you can do:

  • If the binary tree will not be freed nor changed for the lifetime of myvector then you can just remove the delete temp; line.
  • If assumption in the first case is not true, then you need to store Node elements into vector, not pointers to them. So, define myvector as vector<Node> myvector; instead of vector<Node *> myvector; and change myvector.push_back(ptr); to myvector.push_back(*ptr);.
2
  • 1
    Yup. That's how it's done. Though I still hate it that people use c-style pointers. Apr 25, 2018 at 20:31
  • 2
    In addition, I don't think the way the data is being stored in the vector actually represents the binary tree correctly. The code should do a breadth-first traversal, storing each node's data into the vector as it's encounterd. Apr 25, 2018 at 20:39
1

You cannot delete temp after you place it a vector. Also, how is your vector defined? There might be problem there.

Also you should use iterators instead of push_back() function. It doesn't work well with pointers.

And, why does everyone insist on using c-style pointers. Use shared or unique pointers. Please?

Type of error usually signifies that a pointer being freed twice.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.