C++ populating vectors inside class constructors

Question

I have troubling addressing elements inside objects of Class3, please look at this simplified classes:

class Class1 {
public:
    std::vector<Class2> c2v;
    Class1();
};

class Class2 {
    Class1 *instance;
    int id;
public:
    std::vector<Class3> c3v;
    Class2 ( Class1 *instance, int id );
};

class Class3 {
    Class1 *instance;
    int id;
public:
    Class3 ( Class1 *instance, int id );
};

And their constructors:

Class1::Class1()
{
    for ( int i = 0; i < noi; ++i ) {
        c2v.push_back ( Class2 ( this, i ) );
    }
}

Class2::Class2 ( Class1 *instance, int id )
{
    this->instance = instance;
    this->id = id;

    for ( int k = 0; k < nok; ++k ) {
        c3v.push_back ( Class3 ( this->instance, k ) );
    }
}

In main() an object of Class1 is instantiated with its default constructor. Therefore it creates a vector c2v and fills it with 'noi' objects of Class2.

At the same time, when the objects of Class2 are being put into c2v vector, they're instantiated and each one creates a vector c3v and fills it with 'non' objects of Class3.

The code compiles fine but at runtime when accessing public attributes of Class2 from Class3 objects (via this->instance->c2v[0].getSomeAttribute()) the program stops with a EXC_BAD_ACCESS.

Inspecting with a debugger shows that the pointer to c2v[0] gets corrupted (its value becomes 0x0).

I'm a newbie of C++ I was wondering what is the error when trying to instantiate vectors this way. Should I only declare the vectors and populate them in a separate function called after the creation of all instances of Class2 and Class3 is finished?

I'm adding some actual code, hope it won't be too long to read (please understand I've omitted some forward declarations and preprocessor directives):

// global variables
extern char *filename; //not used
extern int nodes;
extern int numProdotti;
extern int classe; //not used
extern int maxNumRange; //not used
extern int *numRanges;
extern int *list ;
extern int *typeProdMarket;
extern int totalQtyDemand; //not used
extern int totNumRanges; //not used

extern struct product {
    int     qty;
    int     cost;
} **prodMarket;

extern struct range {
    int     discount;
    int     startOfRange;
} **rangeMarket; //not used

int main ( int argc, char *argv[] )
{
    Ctqd instance;
    instance.runOpt();
}

class Ctqd {
    void greedySimple();
    void greedySimpleReverse();
    void greedyFromY();
    void greedyByNiceness1();
    void greedyByNiceness2();
    void greedyByStepTier1();
    void greedyByStepTier2();
    void randomLocalSearch1();
    void LocalSearch2opt();
public:
    std::vector<Item> items;
    std::vector<Supplier> suppliers;
    Solution *solution;
    Ctqd();
    ~Ctqd();
    void runOpt();
};

class Supplier {
    Ctqd *instance;
    int id;
    int refTotQty;
    int refDiscount;
    int refDiscountTier;
    double refTotPrice;
    double refUnitPrice;
    double niceness;
    int purTotQty;
    int purDiscount;
    int purDiscountTier;
public:
    std::vector<Offer> offers;
    Supplier ( Ctqd *instance, int id );
    int getId();
    int getRefTotQty();
    int getRefDiscount();
    int getRefDiscountTier();
    double getRefTotPrice();
    double getRefUnitPrice();
    double getNiceness();
    int getPurTotQty();
    int getPurDiscount();
    int getPurDiscountTier();
    void updateStats();
};

class Offer {
    Supplier *supplier;
    int id;
    int refQty;
    double refPrice;
    double niceness;
    int purQty;
public:
    Offer ( Supplier *supplier, int id );
    int getId();
    int getRefQty();
    double getRefPrice();
    double getNiceness();
    int getPurQty();
    void setPurQty ( int qty );
    int remainingQty();
};

Ctqd::Ctqd()
{
    // constructing items vector
    for ( int k = 0; k < numProdotti; ++k ) {
        items.push_back ( Item ( this, k ) );
    }

    // constructing suppliers vector
    for ( int i = 0; i < nodes; ++i ) {
        suppliers.push_back ( Supplier ( this, i ) );
    }

    // building solution
    solution = new Solution ( this );
}

Supplier::Supplier ( Ctqd *instance, int id )
{
    this->instance = instance;
    this->id = id;
    // computing total reference quantity
    refTotQty = 0;

    for ( int k = 0; k < numProdotti ; ++k ) {
        refTotQty += std::min ( list[ k ] , prodMarket[ this->id ][ k ].qty );
    }

    // computing reference discount coefficients
    refDiscount = 0;
    refDiscountTier = 0;

    for ( int r = 0; r < numRanges[ this->id ]; ++r ) {
        if ( refTotQty < rangeMarket[ this->id ][ r ].startOfRange ) {
            break;
        }
        else {
            refDiscount = rangeMarket[ this->id ][ r ].discount;
            refDiscountTier = r;
        }
    }

    //computing total reference price
    refTotPrice = 0;

    for ( int k = 0; k < numProdotti ; ++k ) {
        refTotPrice += prodMarket[ this->id ][ k ].cost * std::min ( list[ k ] , prodMarket[ this->id ][ k ].qty );
    }

    refTotPrice = refTotPrice * ( 1.000 - refDiscount / 100.000 );
    //computing reference unit price
    refUnitPrice = refTotPrice / refTotQty;
    //computing supplier niceness
    niceness = refTotQty / refUnitPrice;
    purTotQty = 0;
    purDiscount = 0;
    purDiscountTier = 0;

    // building offers vector
    for ( int k = 0; k < numProdotti; ++k ) {
        offers.push_back ( Offer ( this, k ) );
    }
}

Offer::Offer ( Supplier *supplier, int id )
{
    this->supplier = supplier;
    this->id = id;
    // computing reference quantity
    refQty = std::min ( list[ this->id ] , prodMarket[ this->supplier->getId() ][ this->id ].qty );
    // computing reference price
    refPrice = prodMarket[ this->supplier->getId() ][ this->id ].cost * ( 1.000 - this->supplier->getRefDiscount() / 100.000 );
    // computing niceness of the offer
    niceness = refQty / ( ( prodMarket[ this->supplier->getId() ][ this->id ].cost + refPrice ) / 2 );
    // init purQty to 0
    purQty = 0;
}

This is where I get the EXC_BAD_ACCESS:

int Offer::remainingQty()
{
    return prodMarket[ supplier->getId() ][ id ].qty - purQty;
}

I've done some experiments: Changed the vectors in the Ctqd class and in the Supplier class to vectors of pointer to objects. Problem was solved only partially. Still had a EXC_BAD_ACCESS when constructing the offers objects.

The constructor for Offer class needs data from the Supplier object that created it. I thought that accessing that data while the suppliers vector was still being populated could lead to problems, so I created a little initialize() function in the supplier:

void Supplier::initialize()
{
    // constructing offers vector
    for ( int k = 0; k < numProdotti; ++k ) {
        offers.push_back ( new Offer ( this->instance, id, k ) );
    }
}

And added this at the end of the Ctqd class constructor:

// init newly built objects
for ( int i = 0; i < nodes; ++i ) {
    suppliers[i]->initialize();
}

Now things seem to be working fine. But i still didn't figure out what the problem exactly was.

Answer 1

By far the easiest (and best) fix for this is to use std::deque instead of std::vector. You do not need to use pointers; you can stick with your original plan of pushing objects.

With a deque, push_back is guaranteed not to invalidate references to its elements. Same for push_front, actually. And it still supports constant-time random access (foo[n]).

A deque is usually what you want when incrementally building a container full of objects.

As a general rule, std::deque is probably the best data structure you have never used.

Answer 2

You're not obeying the rule of 3. You should implement a destructor, copy constructor and assignment operator for all your classes.

Consider the line:

c2v.push_back ( Class2 ( this, i ) );

This will create a temporary object, make a copy of it and put it in the vector. The copy and the temporary object will point via the instance member to the same location. However, when the temporary object is destroyed (right before the next line), that memory is freed and available to use. So now you will have inside your vector an object of type Class2 with an invalid field.

This is just my guess. Please post the code in main if this doesn't help.

Answer 3

Change

std::vector<Class2> c2v;

to

std::vector<Class2 *> c2v;

and

std::vector<Class3> c3v;

to

std::vector<Class3*> c3v;

The problem is that you are taking adresses of local objects inside vector. When vector need more space it reallocates his memory and therefore Class2 and Class3 objects having their adresse changed.

class Class1 {
public:
    std::vector<Class2 *> c2v;
    Class1();
};

class Class2 {
    Class1 *instance;
    int id;
public:
    std::vector<Class3 *> c3v;
    Class2 ( Class1 *instance, int id );
};

class Class3 {
    Class1 *instance;
    int id;
public:
    Class3 ( Class1 *instance, int id );
};


Class1::Class1()
{
    for ( int i = 0; i < noi; ++i ) {
        c2v.push_back ( new Class2 ( this, i ) );
    }
}

Class2::Class2 ( Class1 *instance, int id )
{
    this->instance = instance;
    this->id = id;

    for ( int k = 0; k < nok; ++k ) {
        c3v.push_back ( new Class3 ( this->instance, k ) );
    }
}

And don't forget to cleanup in Class1' and Class2' destructors.

EDIT: Why such strange behaviour occured:

Step 1

Ctqd::Ctqd()
{
    for ( int i = 0; i < nodes; ++i ) {
        suppliers.push_back ( Supplier ( this, i ) ); // <-- Supplier's constructor is invoked here
                                                // to construct automatic object of Supplier class
    }
}

Step 2. We are inside of the automatic object's constructor:

Supplier::Supplier ( Ctqd *instance, int id )
{
    for ( int k = 0; k < numProdotti; ++k ) {
        offers.push_back ( Offer ( this, k ) ); // consider that we are passing this to 
                                               // Offer's constructor. this is a pointer to
                                              // automatic variable
    }
}

Step 3. Back to step 1. But now we have automatic object Supplier created

Ctqd::Ctqd()
{
    for ( int i = 0; i < nodes; ++i ) {
        suppliers.push_back ( Supplier ( this, i ) ); // <-- automatic object of class Supplier
                                                     // is created. Now as long as push_back() taking
                                                    // parameter by value yo are passing copy of
                                                   // automatic object to push_back();
                                                  // as long as you didn't define copy constructor
                                                 // for Supplier compiler adds default for you.
    }
}

Step 4. Copy of automatic object is saved to suppliers vector. New object (copy of automatic object) has vector offers with exactly same values as our automatic object had (thx to vector's copy constructor). So each object has member supplier that points to... (geass what :)) correct! they all point to automaic object.

Ctqd::Ctqd()
{
    for ( int i = 0; i < nodes; ++i ) {
        suppliers.push_back ( Supplier ( this, i ) ); // <-- magic here
    }
}

Step 5. Automatic object has been destructed(remember how you passed point to this object to Offer's constructor?). Oops you say.

Ctqd::Ctqd()
{
    for ( int i = 0; i < nodes; ++i ) {
        suppliers.push_back ( Supplier ( this, i ) ); 
                                                      // <-- automatic doesn't exist no more
    }
}

So what will happen if one of the supplier's methods gonna try to access Supplier object via supplier member (that we, smart kids, know points to dead object... so sad... QQ). Guess. I believe it will die by realising he sees dead object first time in his life ;).

Answer 4

For starters, your code won't compile: when the compiler encounters the declaration of Class1::c2v, Class2 is an unknown symbol. If I add the forward declarations (and a definition of noi), it still contains undefined behavior, and doesn't compile with g++, at least not with the usual options. It's illegal to instantiate a standard template with an incomplete type. Since your types have a cyclic dependency, you're going to have to use pointers somewhere.

Also, what happens to the pointers in Class2 and Class3 when the objects are copied (and std::vector will copy). From the comment you made (Class2 represents suppliers, and Class3 represents offers), these classes should probably be noncopyable. This depends a lot on the design, but in most cases, entity classes, which model the problem domain, should be noncopyable. This too leads to using pointers to them, rather than copies. (Reference semantics, rather than value semantics.)

Of course, using pointers does introduce issues of object lifetime. You'll have to decide when and how suppliers and offers come into existence, and when they cease to exist. This should be part of your design.

Answer 5

Whereas the relocation of the vector's contents and the copying of Class2 or Class3 objects shouldn't give any problems (in contrast to what other answers may state), the problem arises when you create a local object of Class1 and copy this around. When you now try to access the original Class1 object by one of the instance pointers, this object may already have been destroyed and therefore the access to one of its members causes a segfault.