vector bad allocation error c++

Question

I have been working on an avl tree that is vector based for quite some time. I'm suppose to take inputs from a file, but on the 4118 th input it gives me a bad_alloc error. I did some research and gathered inputs that I have to reserve space also. But even when I do allocate space, it still gives the same error.

parts of my code:

I call this function:

void insert(T d, unsigned int c = 1);

find(T d) finds the position of newNode in vector<node<T>*> myVector; it will return a position even if it doesn't find newNode. Insert will take care of the returned integer (shown below)

insert is:

template<typename T>
void binaryTree<T>::insert(T d, unsigned int c)
//inserts type T with count c into vector
{
    node<T>* newNode = new node<T>(d,c);

    if(myVector.empty())
    {
        myVector.push_back(newNode);
    }
    else
    {
        int r = find(d);
        total++;
        //if newNode has same data as the data in position r
        if(r < myVector.size() && myVector[r] && *newNode == *myVector[r])
        {
            myVector[r]->data.loc.push_back(newNode->data.loc[0]);
            myVector[r]->count += newNode->count;
            delete newNode;
            return;
        }
        //insert into vector normally
        else
        {
            checkSpace(r);
            myVector[r] = newNode;
            //reParent(r);
        }
    }
}

with checkSpace being:

template<typename T>
void binaryTree<T>::checkSpace(int i)
//resizes the vector if needed
{
    if(i >= myVector.size())
    {
        myVector.resize(rightOi(i),NULL);
    }
}

and void reParent(r) being the main function that does all the rotate and balancing. I commented out reParent(r), and might have isolated the problem to be only in the insert function. I am fairly new to this, and I appreciate any help. Thank you in advance.

rightOi function:

template<typename T>
//return the right position of i
int binaryTree<T>::rightOi(int i)
{
    return i*2 + 2;
}

Answer 1

So i found the problem, which is that, the checkspace() function (which resizes the vector) gets the vector to resize to a huge number. That's why the program kept on giving me error. The fix for that is to resize only when necessary. Which is how I fixed my project.

Answer 2

I may be wrong, and slightly offtopic, but it seems to me, that vector isn't a good idea for dynamic trees, I'd create tree old-fashioned way, like this:

struct Node
{
    T value;
    Node* right;
    Node* left;
}

int main()
{
    Node<int>* root = new Node<int>();
    root->value = 10;
    root->right = NULL;
    root->left = NULL;

    Node<int>* someNode = new Node<int>();
    someNode->value = 5;
    someNode->right = NULL;
    someNode->left = NULL;

    root->left = someNode;
}

So it may be wrapped into functions like AddElement, Rebalance, Traverse, Delete by your rules. Ask if you need more detailed description.