Resizing a Vector Throws a bad_alloc

[Carl]

What are the reasons a bad_alloc would be thrown when I resize a vector? I know it means that new memory could not be allocated, but what can I do to prevent that from happening?

To be more specific, I have a class-member vector of vectors that is initialized to size 0x0. I resize it to 22x0, then begin incrementally resizing it to 22x2, like this:

Steps = 20;
theExtendedTree.resize(Steps+2);
    
    theExtendedTree[0].resize(1);
    theExtendedTree[0][0].first = Spot;



    for (unsigned long i=1; i <=Steps + 1; i++)
    {
        theExtendedTree[i].resize(2);
        theExtendedTree[i][0].first = theExtendedTree[i-1][0].first * upFactor;

        if ( i >1)
            theExtendedTree[i][1].first = theExtendedTree[i-1][1].first * downFactor;
        else if (i==1)
            theExtendedTree[i][1].first = theExtendedTree[0][0].first * downFactor;
    }

at i=2, a bad_alloc is thrown at resize. This happens on both my desktop and laptop. It only happens when other class-members (which are vectors of vectors) are resized before this. If I don't resize the other vector of vectors, then everything is fine.


I've amateurishly tried using vector::reserve, but the same problem arises.
Any ideas?

 

[Carl]

To try to narrow the problem down further, I put similar code in main(), right before I would normally call the class-member function that has been giving me problems. I hoped that this way I could narrow it down to possibly an error in how I coded my class, or structured the inheritance.

main()

//...stuff...

//where function call normally would be, I've replaced it with the below code
    vector<vector< pair<double,double> > > *tryToCrash;
    tryToCrash = new vector<vector< pair<double,double> > >;
    tryToCrash->resize(22);
    (*tryToCrash)[1].resize(2);
    (*tryToCrash)[2].resize(2);

But, a bad_alloc is still thrown at the last line.

I hate bad_alloc.:wall

 

[doug reich]

What about the memory access above there?

I believe bad_alloc is usually thrown when you try to do memory operations AFTER a violation has already occurred. So you should look higher up in your program for bad memory operations.

 

[alain]

Carl, I need more details. I took that piece of code and it compiles and executes without problems on g++ (I don't have VC++ at work) in windows.

 

[Carl]

Do you have Joshi's book on hand, Alain?

I set up my tree classes like he shows in chapter 8.

The only difference is that I created a parent class (TrinomialTree) that SimpleTrinomialTree is derived from.

Everything seems pretty straightforward. I don't need to worry about memory management because all classes that use pointers have been bridged.

I added a member-function TrinomialTree::setSteps so I could readjust the size of the tree. All it essentially does is resize the vector of vectors. That seemed to work fine, except after I do that, if I resize another vector of vectors in the object (the extended tree) then things crash.


Here are the two classes. I edited out irrelevant simple variables and member-functions

class TrinomialTree
{

public:
    TrinomialTree(...);
                  

    virtual double GetThePrice(const TreeProduct& TheProduct);
  
    virtual void setSteps(const unsigned long stepNumNew);


    virtual     void buildStockTree(); 
    virtual    void buildOptionTree(const TreeProduct& TheProduct) =0; 
    virtual    void buildExtendedTree(const TreeProduct& TheProduct)=0;
        //extends tree backwards 2 time steps, filling in stock
        //and option values

protected:
  
    bool stockTreeBuilt;
    bool optionTreeBuilt;
    bool extendedTreeBuilt;
  
    std::vector<std::vector<std::pair<double, double> > > TheTree;
    std::vector<std::vector<std::pair<double, double> > > theExtendedTree;
    MJArray Discounts;
};


class SimpleTrinomialTree    : public TrinomialTree
{

public:
    SimpleTrinomialTree(...);
                  
    virtual void buildOptionTree(const TreeProduct& TheProduct); 
    virtual void buildExtendedTree(const TreeProduct& TheProduct);
        //extends tree backwards 2 time steps, filling in stock
        //and option values

private:

};

 

[doug reich]

To clarify what I said earlier, if you access data out of array bounds, you may not see the error until the array is deconstructed or another memory operation occurs. (Don't I know from debugging my matrix class)

 

[Carl]

Doug, that brings back many nightmares.

I will check to see if that is the case.


Edit- I'm also having some problems where my code will crash in release mode, but not in debug mode. I haven't investigated it yet though.

 

[doug reich]

My recollection is that those are all the same symptoms of out of bounds problems.

Nightmares, indeed.

 

[Carl]

I just went thew all of the code involving the vectors of vectors, and changed [] to .at(). I still get a bad_alloc thrown in the same circumstances as before.

If it was an out-of-range problem, wouldn't I get an out_of_range thrown?

At this point, I've abandoned the idea of changing the size of the array after it is has been initialized. I wanted to use it so I could use loops to obtain all of the values needed in HW one for PDEs, but new and delete work fine, so I've used those instead.

 

[Roger Trimble]

This might be a moot point, but to follow up on what Doug suggested, is it possible that somewhere in your normal tree routine you have an index off by one in some container? In other words, your normal ( on-tree ) values might compute fine even though you are violating the heap there. Then, when you run the extended tree the error occurs.

I've run into this problem at times with my vector and matrix classes. When this has happened, the error is sporadic, but occurs often.

 

[Stefan Zota]

I just went thew all of the code involving the vectors of vectors, and changed [] to .at(). I still get a bad_alloc thrown in the same circumstances as before.

If it was an out-of-range problem, wouldn't I get an out_of_range thrown?

At this point, I've abandoned the idea of changing the size of the array after it is has been initialized. I wanted to use it so I could use loops to obtain all of the values needed in HW one for PDEs, but new and delete work fine, so I've used those instead.

The snippet you have included is fine. The problem is somewhere else.
Another option can be that you are trying to access a location that was already deleted. This can be done if some destructor code is executed in an unexpected place.

A couple of comments though (maybe it helps):
1. vector class is a solution for storing an array however access time is not the best. The fastest solution is contiguous memory (simple array). This was discussed in a few other previous threads.
2. resize is not needed in this case. After input is provided (value N), size of the tree is known and fixed. The extended tree is really a separate tree with N+2 or N+1 size.
In general, I try to avoid resizing or re-allocating memory unless absolutely needed. We can just create an array with bigger size and drop the initial one ...

 

[Carl]

I found the problem. It was Joshi's array. I threw it in for future purposes, assumed none of my code touched it, and then just discovered that I was wrong. :smt119

Thanks for the help, guys. :smt073