重新定位可變數組大小的內存

Question

假設我們有一系列村莊。陣列方面，每個村莊都是獨一無二的。一個村莊可以有多個商店。問題是你只有有限的（動態）內存，並且不能魯莽地初始化你不會使用的內存。因此，如果你在一個村莊建立一個新的商店，你將需要將你的村莊遷往另一個不同的地方，因爲這個村莊的規模已經擴大了。如果你增加一個新的村莊，你將不得不搬遷以積累額外的規模。

的問題是，你不能簡單地使用：

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

這是因爲您將創建包含每村1個店X村莊的記憶。由於現有的村莊可能有多個商店，內存分配將失敗並可能覆蓋您不應觸摸的內存！

我的例如C++代碼是這樣的：

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; 
} 

我的問題，問題是：

什麼是動態放大 對象的自定義的數組，如果不是所有的對象都具有正確的方法相同的大小，或者如果此數組中現有的對象增長（新的商店在一個村莊）？當添加

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

不幸的是，：

我先前創建下面的函數：

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

我試圖使用它在下面的函數來定位在鄉村對象的存儲陣列一個新的村莊，一切都與記憶錯誤！

Answer 1

C/C++中有兩種類型的數組：靜態和動態。 不幸的是，即使後者暗示可以通過像realloc()這樣的調用來「容易地調整」大小，但事實是，總是重新分配數組中的所有對象以增加1的大小是很乏味的，因此應該避免。但是有一個解決方法！

如果我正確理解你的問題，你想爲不同大小的對象動態分配內存。這樣做的偶然方法是通過鏈接列表。最基本的鏈表會是這個樣子：

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; 
      } 
     } 

     //... 
}; 

如果你不想實現自己的，你應該看看標準模板庫的std::vector。 有關鏈接列表的更多詳細信息，請參閱Stackoverflow - Linked Lists in C++或Wikipedia - Linked Lists，或獲得STL的std::vector的詳細說明，請參閱cpluslus.com - std::vector。

希望我能幫助，歡呼！
lindebear

PS：您也可以嵌套鏈接列表，請參閱here。