如何在一次分配中分配多个不同类型的数组？

Question

我正在编写一个探测哈希集，它在内部维护一个槽数组以及一个单独的槽元数据数组：

template <typename T, typename Hasher = std::hash<T>, typename Allocator = std::allocator<T>>
class HashSet {
    T *slots;              // Array of slots
    uint8_t *metadata;     // Array of metadata (each slot has a single byte of metadata)
    Allocator allocator;
    /* ... */
}

现在，在我当前的实现中，

slots

和

metadata

数组使用单独的分配。特别是，我对 slots 使用

placement new/delete

（通过

std::allocator_traits

）以避免不必要地调用

T

的默认构造函数。然而，对于

metadata

，我只是使用常规的

new[]/delete[]

，因为无论如何元数据总是需要在开始时初始化。因此，我的代码如下所示（以我的

reserve

函数为例）：

// Inside `class HashSet`
void reserve(size_t new_capacity) {
    if (curr_capacity >= new_capacity) return;

    // Allocate new slots and metadata arrays separately
    auto new_slots = std::allocator_traits<Allocator>::allocate(allocator, new_capacity);
    auto new_metadata = new uint8_t[new_capacity];

    /* Rehash all elements, and move them to `new_slots`... */

    // Deallocate the old `slots` and `metadata` arrays
    if (slots) std::allocator_traits<Allocator>::deallocate(allocator, slots, curr_capacity);
    delete[] metadata;

    /* Set `slots` and `metadata` to `new_slots` and `new_metadata`, and update `curr_capacity`... */
}

现在，我意识到在“单个”分配中分配两个数组将提高引用的局部性。但是，我不确定如何做到这一点。特别是，我非常确定简单地分配一个大的 char* 缓冲区并将其视为连接到元数据数组的元素数组会违反内存对齐规则。同时，我担心我使用不同的策略来管理插槽和元数据（放置新/删除与常规新/删除）；我一直在考虑只对所有内容使用放置新/删除。

总的来说，我的问题是：

如何在单个连续分配中创建两个不同类型的数组

，以提高缓存局部性？ 我所知道的唯一与此类似的事实是，

std::make_shared

在一次分配中同时分配了值和引用计数器。但是，我不知道这是如何实现的。

Answer 1

struct

，其中包含 1 个

T

和 1 个

uint8_t

，然后分配 1 个以该结构体作为其元素类型的数组。否则，您必须分配一个足够大的

char[]

缓冲区来容纳两个数组以及它们之间的对齐填充，然后使用

placement-new

在部分内存中创建

uint8_t

元素，并使用

T

剩余内存中的元素。