如何在内存中连续分配可变大小的结构？

Question

我正在使用 C++，并且具有以下结构：

struct ArrayOfThese {
  int a;
  int b;
};

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

在内存中，我希望在每个 DataPoint 的末尾有 1 个或多个 ArrayOfThese 元素。每个 DataPoint 的 ArrayOfThese 元素数量并不总是相同。

因为我有大量的数据点需要组装然后通过网络进行流式传输，所以我希望所有的数据点及其 ArrayOfThese 元素都是连续的。为固定数量的 ArrayOfThese 元素浪费空间是不可接受的。

在 C 中，我会在 DataPoint 末尾创建一个元素，将其声明为 ArrayOfThese d[0];，为我拥有的 ArrayOfThese 元素分配一个 DataPoint 加上足够的额外字节，并使用用于索引它们的虚拟数组。 （当然，ArrayOfThese 元素的数量必须位于 DataPoint 的字段中。）

在 C++ 中，使用放置 new 和相同的 0 长度数组 hack 是正确的方法吗？如果是这样，放置 new 是否能保证后续从同一内存池调用 new 会连续分配？

Answer 1

由于您正在处理没有构造函数的普通结构，因此您可以恢复到 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 2

由于您的结构体是 POD，因此您也可以像在 C 中一样进行操作。您唯一需要的就是强制转换。假设 n 是要分配的事物的数量：

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

如果您的对象有一个不平凡的构造函数，则放置 new 确实会遇到这种情况。但它不保证任何分配，因为它不分配自身，并且要求内存已经以某种方式分配。相反，它将传入的内存块视为尚未构造的对象的空间，然后调用正确的构造函数来构造它。如果您要使用它，代码可能会像这样。假设 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;

构造的内容必须被破坏，因此如果您这样做，您也应该整理析构函数的调用。

（我个人建议在这种情况下使用 POD，因为它消除了调用构造函数和析构函数的任何需要，但如果您小心的话，这种事情可以相当安全地完成。）

Answer 3

正如阿德里安在他的回答中所说，你在内存中所做的事情不一定与你在流媒体中所做的事情相同通过网络。事实上，明确划分这一点甚至可能会更好，因为如果您以后需要重构数据，那么依赖于以特定方式设计的数据的通信协议会产生巨大的问题。

C++ 连续存储任意数量的元素的方式当然是std::vector。既然你甚至没有考虑到这一点，我认为有一些东西使得这种情况变得不可取。 （您是否只有少量的 ArrayOfThese 并担心与 std::vector 相关的空间开销？）

虽然过度分配零长度数组的技巧可能是不能保证有效，并且从技术上讲可能会引发可怕的未定义行为，这是一种广泛传播的行为。你在什么平台？在 Windows 上，这是在 Windows API 中完成的，因此很难想象供应商提供的 C++ 编译器不支持此功能。

如果可能的 ArrayOfThese 元素数量有限，您还可以使用 fnieto 的技巧指定这几个数字，然后根据运行时编号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 4

在 C++0X 之前，该语言没有内存模型可言。对于新标准，我不记得有任何关于连续性保证的讨论。

关于这个特定问题，听起来好像您想要的是一个池分配器，存在很多这样的例子。例如，现代 C++ 设计，作者：Alexandrescu。小对象分配器讨论是您应该关注的内容。

Answer 5

我认为 boost::variant 可能会实现这一点。我还没有机会使用它，但我相信它是联合的包装器，因此它们的 std::vector 应该是连续的，但当然每个项目都会占用更大的空间在这两种大小中，您不能拥有具有不同大小元素的向量。

看一下比较boost::variant 和 boost::any。

如果您希望每个元素的偏移量取决于前面元素的组成，则必须编写自己的分配器和访问器。

Answer 6

似乎分配一个指针数组并使用它比使用新的放置更简单。这样你就可以将整个数组重新分配到新的大小，而运行时成本却很小。另外，如果使用新的放置，则必须显式调用析构函数，这意味着在单个数组中混合非放置和放置是危险的。阅读 http://www.parashift.com/c++-faq-lite/dtors .html 在你做任何事情之前。

Answer 7

不要混淆程序内部的数据组织和序列化数据组织：它们没有相同的目标。

对于通过网络进行流式传输，您必须考虑通道的两侧，即发送方和接收方：接收方如何区分 DataPoint 和 ArrayOfThese ？接收方如何知道在 DataPoint 之后附加了多少个 ArrayOfThese ？ （还要考虑：每一侧的字节顺序是什么？数据类型在内存中的大小是否相同？）

就我个人而言，我认为您需要一个不同的结构来流式传输数据，在其中添加要发送的 DataPoint 的数量以及每个 DataPoint 之后的 ArrayOfThese 数量。我也不关心数据在我的程序中已经组织的方式，并重新组织/重新格式化以适合我的协议而不是我的程序。之后编写一个用于发送的函数和另一个用于接收的函数就不是什么大问题了。

Answer 8

为什么不让 DataPoint 包含 ArrayOfThese 项目的可变长度数组？这适用于 C 或 C++。如果任一结构体包含非基本类型，则会出现一些问题，

但对结果使用 free() 而不是 delete：

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 知道它的长度：

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

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

Answer 9

您能否将它们制作成具有相同超类的类，然后使用您最喜欢的选择的 stl 容器，并使用超类作为模板？

Answer 10

两个问题：

1. ArrayOfThese 和 DataPoint 之间的相似性是真实的，还是发布的简化？即真正的区别只是一个整数（或任意数量的相同类型的项目）？
2. 与特定 DataPoint 关联的 ArrayOfThese 数量在编译时是否已知？

如果第一个是正确的，我会认真考虑简单地为一个 DataPoint+N ArrayOfThese 分配一个包含尽可能多的项目的数组。然后，我将构建一段快速代码来重载operator[]以返回项目N+3，并重载a()、b()和c()以返回前三个项目。

如果第二个是真的，我基本上会建议我看到 fnieto 刚刚发布的内容，所以我不会详细说明。

就放置新而言，它并不能真正保证有关分配的任何信息 - 事实上，放置新的整个想法是它与内存分配完全无关。相反，它允许您在已分配的内存块中的任意地址（受对齐限制）创建对象。

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