c++ - 在 C++ 中访问过度分配的内存

Question

我有一棵巨大的树，可以占用数 GB 的空间。节点结构如下。您会注意到我将最后一个成员设为大小为 1 的数组。这样做的原因是我可以过度分配 Node。具有灵活的尺寸。类似于 C native 支持的灵活数组成员。我可以使用 std::unique_ptr<T[]>或 std::vector<T>相反，但问题是每个树节点都有双重动态分配、双重间接和额外的缓存未命中。在我上次的测试中，这使我的程序花费了大约 50% 的时间，这对于我的应用程序来说是完全不能接受的。

template<typename T>
class Node
{
public:
  Node<T> *parent;
  Node<T> *child;

  /* ... */

  T &operator[](int);
private;
  int size;
  T array[1];
};

最简单的实现方式operator[]会是这个。

template<typename T>
T &Node::operator[](int n)
{
  return array[n];
}

它应该在大多数理智的 C++ 实现中都能正常工作。但由于 C++ 标准允许疯狂的实现进行数组边界检查，据我所知，这在技术上调用了未定义的行为。那我可以这样做吗？

template<typename T>
T &Node::operator[](int n)
{
  return (&array[0])[n];
}

我在这里有点困惑。 []原始类型的运算符只是 * 的语法糖.因此 (&array[0])[n]相当于(&*(array + 0))[n] ，我认为可以清理为 array[n] ，使一切都与第一个相同。好的，但我仍然可以这样做。

template<typename T>
T &Node::operator[](int n)
{
  return *(reinterpret_cast<T *>(reinterpret_cast<char *>(this) + offsetof(Node<T>, array)) + n);
}

我希望我现在可以摆脱可能的未定义行为。也许内联汇编会更好地显示我的意图。但我真的必须走这么远吗？有人可以向我澄清一下吗？

顺便说一句T始终是 POD 类型。整体Node也是POD。

Answer 1

首先，除了微不足道的情况外，实现可以自由地对类成员进行重新排序。您的案例并不简单，因为它具有访问说明符。除非你制作你的类 POD，或者它在 C++11 中被调用的任何东西(琐碎的布局？)你不能保证你的数组实际上是最后布局的。

当然，C++ 中不存在灵活成员。

然而，一切并没有丢失。分配一 block 足够大的内存来容纳你的类和你的数组，然后在开始时放置-new你的类，并将对象之后的部分(加上任何 paddibg 以确保正确对齐)解释为数组。

如果你有this，那么数组可以用

访问

reinterpret_cast<T*>(
 reinterpret_cast<char*>(this) +
 sizeof(*this) + padding))

其中选择 adfing 使得 sizeof(T) 除 sizeof(*this) + padding。

要获得灵感，请查看 std::make_shared`。它还将两个对象打包到一个分配的内存块中。