Relocating memory for variable array size

Question

Let's say we have got an array of villages. Each village is unique with regards to the array. A village can have multiple stores. The problem is that you only have limited (dynamic) memory and cannot recklessly initialise memory that you will not use. Therefore, If you create a new store in a village, you will need to relocate your village to a different place in the memory since the size of the village has grown. If you add a new village, you will have to relocate as well in order to accumulate for the extra size.

The problem is that you cannot simply use the following:

 pVillage = (Village *)realloc( pVillage, ++MAX_VILLAGE * sizeof(Village));

This is because you will create memory for x villages containing 1 store per village. Since it could be the case that existing villages have multiple stores, the memory allocation will fail and could possibly overwrite memory which you shouldn't touch!

My example c++ code is as such:

class Store
{
    char* m_pStoreName;
    int m_nAmountOfProducts;

public:
    Store(char* name, int number);
    Store();
};

Store::Store(char* name, int number)
{
    char *m_pStoreName = new char[10];
    strcpy( m_pStoreName, name );
    m_nAmountOfProducts = number;
}

Store::Store()
{

}

int nMaxStore = 1;
class Village
{

    int m_nAmountOfStores;
    Store *m_pStoreDb = (Store *)malloc( nMaxStore * sizeof(Store) );

public:
    char* m_pVillageName;
    Village(char* name);
    Village();
    addStore(Store* st);

};

Village::Village(char* name)
{
    char *m_pVillageName = new char[10];
    strcpy(m_pVillageName, name);
    m_nAmountOfStores = 0;
}

Village::Village()
{

}

Village::addStore(Store* st)
{
    if ( m_nAmountOfStores == nMaxStore )
    {
        //Need more memory
        m_pStoreDb = (Store *)realloc( m_pStoreDb, ++nMaxStore * sizeof(Store) ); //Realocate and copy memory
    }

    //Add to db
    *( m_pStoreDb + m_nAmountOfStores++ ) = *st;
}

int nAmountVillages = 0;
int nMaxVillages = 1;
Village *pVillageDB = (Village *)malloc( nMaxVillages * sizeof(Village) );

int main()
{
    addNewVillage("Los Angeles", new Store("Store 1", 20));
    addNewVillage("San Fransisco", new Store("Store 1", 10 ));
    addNewVillage("New York", new Store("Store 1", 15));
    addNewVillage("Los Angeles", new Store("Store 2", 12));
    addNewVillage("Los Angeles", new Store("Store 3", 22));
    addNewVillage("Amsterdam", new Store("Store 1", 212));
    addNewVillage("Los Angeles", new Store("Store 4", 2));

    return 0;
}

void addNewVillage(char* villageName, Store *store)
{
    for ( int x = 0; x < nAmountVillages; x++ )
    {
        Village *pVil = (pVillageDB + x);
        if ( !strcmp(pVil->m_pVillageName, villageName) )
        {
            //Village found, now add store
            pVil->addStore( store );
            return;
        }
    }

    //Village appears to be new, add new one after expanding memory

    if ( nAmountVillages == nMaxVillages )
    {
        //Need more memory
        pVillageDB = (Village *)realloc( pVillageDB, ++nMaxVillages * sizeof(Village) ); //Realocate and copy memory
    }

    //Create new village and add store to village
    Village *pNewVil = new Village( villageName );
    pNewVil->addStore( store );

    //Add village to DB
    (pVillageDB + nAmountVillages++ ) = pNewVil;
}

My problem, question is:

What is the correct way to dynamically enlarge an array of custom objects if not all objects have the same size, or if an existing object in this array grows in size (new stores in a village)?

I have previously created the following function:

int Village::calculateStoreSize()
{
    int nSize = 0;
    for ( int x = 0; x < m_nAmountOfStores; x++ )
    {
        Store *pStore = ( m_pStoreDb + x );
        nSize += sizeof(*pStore);
    }
    return nSize;
}

I tried using it in the following function to relocate the store array in a village object:

   m_pStoreDb = (Store *)realloc( m_pStoreDb, Village::calculateStoreSize() + sizeof(Store) );

Unfortunately, when adding a new village, everything goes wrong with memory!

Answer 1

There are two types of arrays in C/C++: Static and Dynamic. Unfortunately even though the latter one suggests that the size can be "easily adjusted" via calls like realloc(), the truth is, always reallocating all the objects of an array just to increase the size by 1 is tedious and should thus be avoided. However there is a workaround!

If I understand your question correctly, you want to dynamically allocate memory for objects of varying size. The casual way to do so is via linked lists. The most basic linked list would look something like this:

struct store {
    char* name;
    int products;
    store* next;
};

class MyLinkedList {
    private:
        store* first;

    public:
        //Constructor
        MyLinkedList();
        //Destructor: iterate through the list and call delete on all elements.
        ~MyLinkedList();

        void Add(const char* name, int products) {
            if(this->first == NULL) {
                store* new_store = new store;
                new_store->name = new char[30];

                strcpy(new_store->name, name);
                new_store->products = products;
                new_store->next = NULL;

                this->first = new_store;
            } else {
                store* iter = this->first;
                while(iter->next != NULL) {
                    iter = iter->next; 
                }
                //Now iter points at the last element within the linked list.
                store* new_store = new store;
                new_store->name = new char[30];

                strcpy(new_store->name, name);
                new_store->products = products;
                new_store->next = NULL;

                iter->next = new_store;
            }
        }

        //...
};

If you don't want to implement your own, you should have a look at the Standard Template Library's std::vector. See Stackoverflow - Linked Lists in C++ or Wikipedia - Linked Lists for more detail on linked lists, or to get a good description of the STL's std::vector see cpluslus.com - std::vector.

Hope I could help, cheers!
lindebear

PS: You can also nest linked lists, see here.