如何在內存中連續分配可變大小的結構？

Question

我使用C++，並且我具有以下結構：

 
struct ArrayOfThese { 
    int a; 
    int b; 
}; 

struct DataPoint { 
    int a; 
    int b; 
    int c; 
}; 

在內存中，我希望有在每個數據點的端部1個或多個ArrayOfThese元件。每個數據點並不總是有相同數量的ArrayOfThese元素。

因爲我有數量可觀的數據點來組裝，然後通過網絡進行流式傳輸，我希望我所有的DataPoints和它們的ArrayOfThese元素都是連續的。浪費固定數量的ArrayOfThese元素的空間是不可接受的。

在C中，我會在DataPoint的末尾創建一個元素，它被聲明爲ArrayOfThese d[0];，爲我的多個ArrayOfThese元素分配了一個DataPoint加足夠的額外字節，並使用虛數組來索引它們。 （當然，ArrayOfThese元素的數量必須位於數據點的某個字段中。）

在C++中，是使用放置new和相同的0長度數組hack的正確方法嗎？如果是這樣，那麼放置新的保證是否保證後續對來自同一內存池的新調用將連續分配？

Answer 1

由於你的結構是POD，所以你可以像在C中一樣做。唯一需要的是演員。假設n是事物來分配數目：

DataPoint *p=static_cast<DataPoint *>(malloc(sizeof(DataPoint)+n*sizeof(ArrayOfThese))); 

放置新的不來爲這樣的事情，如果你的對象有一個不平凡的構造函數。它不保證任何分配，因爲它沒有分配自己，並且需要內存已經被分配。相反，它將傳入的內存塊視爲尚未構造的對象的空間，然後調用正確的構造函數來構造它。如果你要使用它，代碼可能會像這樣。假設DataPoint有ArrayOfThese arr[0]會員，你建議：

void *p=malloc(sizeof(DataPoint)+n*sizeof(ArrayOfThese)); 
DataPoint *dp=new(p) DataPoint; 
for(size_t i=0;i<n;++i) 
    new(&dp->arr[i]) ArrayOfThese; 

什麼被構造必須適應銷燬，所以如果你這樣做，你應該理清析構函數調用了。

（我個人建議使用莢在這種情況下，因爲它消除了任何需要調用構造函數和析構函數，但這樣的事情可以合理安全的，如果你是細心完成。）

Answer 2

你可以使用相同的超類進入類，然後使用你最喜歡的STL容器的選擇，使用超類作爲模板？

Answer 3

之前的C++ 0X，語言有沒有內存模型說到。而用新標準，我不記得任何關於連續性保證的說法。

關於這個特定的問題，聽起來好像你想要的是一個池分配器，其中很多例子都存在。例如，考慮Alexandrescu編寫的Modern C++ Design。小對象分配器的討論是你應該看看的。

Answer 4

我認爲boost::variant可能會做到這一點。我沒有機會使用它，但我相信它是圍繞工會的包裝，所以它們應該是連續的，但是當然每件物品都會佔用兩種尺寸中的較大尺寸，您不能具有不同大小元素的矢量。請參閱comparison of boost::variant and boost::any。

如果你想要每個元素的偏移量依賴於前面元素的組成，你將不得不編寫你自己的分配器和訪問器。

Answer 5

因爲你面對的是有沒有構造簡單的結構，你可以恢復到C的內存管理：

void *ptr = malloc(sizeof(DataPoint) + n * sizeof(ArrayOfThese)); 
DataPoint *dp = reinterpret_cast<DataPoint *>(ptr)); 
ArrayOfThese *aotp = reinterpet_cast<ArrayOfThese *>(reintepret_cast<char *>(ptr) + sizeof(DataPoint)); 

Answer 6

好像它會更簡單分配的指針數組，並與工作，而不是使用安置新。這樣你可以重新分配整個數組到新的大小，而且運行時間很少。另外，如果您使用placement new，則必須顯式調用析構函數，這意味着將非放置和放置在單個數組中是非常危險的。在你做任何事之前閱讀http://www.parashift.com/c++-faq-lite/dtors.html。

Answer 7

兩個問題：

1. ArrayOfThese和DataPoint實數之間的相似性，還是發佈的簡化？即是真正的區別只是一個整數（或任意數量的相同類型的項目）？
2. ArrayOfThese是否與編譯時已知的特定數據點相關聯？

如果第一個是真的，我會考慮簡單地爲一個DataPoint + N ArrayOfThese分配儘可能多的項目數組。然後，我會構建一段代碼來重載operator []，以返回第N + 3項，並重載（），b（）和c（）以返回前三項。

如果第二個是真的，那麼我將基本上建議我看到fnieto剛發佈的內容，所以我不會詳細討論。就新放置而言，它並不能真正保證分配的任何內容 - 事實上，關於放置new的整個想法是它與內存分配完全無關。相反，它允許您在已分配的內存塊中的任意地址創建一個對象（受對齊限制的限制）。

Answer 8

請勿將程序和數據組織中的數據組織混淆爲序列化：它們沒有相同的目標。

對於通過網絡進行流式傳輸，您必須考慮信道的兩端，發送端和接收端：接收端如何區分DataPoint和ArrayOfThese？接收方如何知道在DataPoint之後追加了多少個ArrayOfThese？ （也要考慮：每邊的字節順序是什麼？數據類型的內存大小是否相同？）

個人來說，我認爲你需要一個不同的數據流結構，在其中添加數您要發送的DataPoint以及每個DataPoint之後的ArrayOfThese的數量。我也不會在乎數據在我的程序中的組織方式，並重新組織/重新格式化以適應我的協議而不是我的程序。之後寫一個函數發送和另一個接收不是什麼大不了的事情。

Answer 9

爲什麼沒有數據點包含的ArrayOfThese項的可變長度數組？這將以C或C++工作。有一些擔憂，如果任一結構中包含非原始類型

但使用免費（）而不是在結果上刪除：

struct ArrayOfThese { 
    int a; 
    int b; 
}; 


struct DataPoint { 
    int a; 
    int b; 
    int c; 
    int length; 
    ArrayOfThese those[0]; 
}; 

DataPoint* allocDP(int a, int b, int c, size_t length) 
{ 
    // There might be alignment issues, but not for most compilers: 
    size_t sz = sizeof(DataPoint) + length * sizeof(ArrayOfThese); 
    DataPoint dp = (DataPoint*)calloc(sz); 
    // (Check for out of memory) 
    dp->a = a; dp->b = b; tp->c = c; dp->length = length; 
} 

然後你就可以在一個循環中使用「正常」其中數據點知道它的長度：

DataPoint *dp = allocDP(5, 8, 3, 20); 

for(int i=0; i < dp->length; ++i) 
{ 
    // Initialize or access: dp->those[i] 
} 

Answer 10

阿德里安在his answer說，你在內存中做什麼並不一定是一樣的，你什麼流在網絡上。事實上，清楚地劃分它可能會更好，因爲如果您以後需要重構數據，那麼依賴於以特定方式設計數據的通信協議會造成巨大的問題。

連續存儲任意數量元素的C++方式當然是std::vector。由於你甚至沒有考慮到這一點，我認爲有些事情會導致這種不合需要。 （難道你只有ArrayOfThese小數字，怕與std::vector相關的空間開銷？）

雖然與過度分配一個長度爲零的數組可能是不能保證工作和可能，在技術上，調用害怕的絕招未定義的行爲，這是一個廣泛傳播的行爲。你在哪個平臺上？在Windows上，這是在Windows API中完成的，因此很難想象一個供應商提供的C++編譯器不支持這一點。

如果有可能ArrayOfThese元素計數的數量有限，你也可以使用fnieto's trick指定的那幾個號碼，然後將得到的模板實例new之一，這取決於運行時數：

struct DataPoint { 
    int a; 
    int b; 
    int c; 
}; 

template <std::size_t sz> 
struct DataPointWithArray : DataPoint { 
    ArrayOfThese array[sz]; 
}; 

DataPoint* create(std::size_t n) 
{ 
    switch(n) { 
    case 1: return new DataPointWithArray[1]; 
    case 2: return new DataPointWithArray[2]; 
    case 5: return new DataPointWithArray[5]; 
    case 7: return new DataPointWithArray[7]; 
    case 27: return new DataPointWithArray[27]; 
    default: assert(false); 
    } 
    return NULL; 
} 

Answer 11

這裏是我寫的代碼：

#include <iostream> 
#include <cstdlib> 
#include <cassert> 
using namespace std; 

struct ArrayOfThese { 
    int e; 
    int f; 
}; 

struct DataPoint { 
    int a; 
    int b; 
    int c; 
    int numDPars; 
    ArrayOfThese d[0]; 

    DataPoint(int numDPars) : numDPars(numDPars) {} 

    DataPoint* next() { 
    return reinterpret_cast<DataPoint*>(reinterpret_cast<char*>(this) + sizeof(DataPoint) + numDPars * sizeof(ArrayOfThese)); 
    } 

    const DataPoint* next() const { 
    return reinterpret_cast<const DataPoint*>(reinterpret_cast<const char*>(this) + sizeof(DataPoint) + numDPars * sizeof(ArrayOfThese)); 
    } 
}; 

int main() { 
    const size_t BUF_SIZE = 1024*1024*200; 

    char* const buffer = new char[BUF_SIZE]; 
    char* bufPtr = buffer; 

    const int numDataPoints = 1024*1024*2; 
    for (int i = 0; i < numDataPoints; ++i) { 
    // This wouldn't really be random. 
    const int numArrayOfTheses = random() % 10 + 1; 

    DataPoint* dp = new(bufPtr) DataPoint(numArrayOfTheses); 

    // Here, do some stuff to fill in the fields. 
    dp->a = i; 

    bufPtr += sizeof(DataPoint) + numArrayOfTheses * sizeof(ArrayOfThese); 
    } 

    DataPoint* dp = reinterpret_cast<DataPoint*>(buffer); 
    for (int i = 0; i < numDataPoints; ++i) { 
    assert(dp->a == i); 
    dp = dp->next(); 
    } 

    // Here, send it out. 

    delete[] buffer; 

    return 0; 
}