我正在写一个 skip list .

我有什么:

template<typename T>
struct SkipListNode
{
    T data;
    SkipListNode* next[32];
};

这段代码的问题在于它浪费了空间——它要求所有节点都包含 32 个指针。特别是考虑到在典型的列表中，一半的节点只需要一个指针。

C 语言有一个称为灵活数组成员的巧妙特性可以解决这个问题。如果它存在于 C++ 中(即使对于普通类)，我可以编写如下代码:

template<typename T>
struct SkipListNode
{
    alignas(T) char buffer[sizeof(T)];
    SkipListNode* next[];
};

然后用工厂函数手动创建节点，并在删除元素时销毁它们。

这带来了问题 - 我如何可移植模拟这样的功能，而没有 C++ 中的未定义行为？

我考虑过 malloc 缓冲区，然后手动适本地操作偏移量 - 但它太容易违反对齐要求 - 如果你 malloc(sizeof(char) + sizeof(void *)*5)，指针未对齐。另外，我什至不确定这种手工创建的缓冲区是否可以移植到 C++。

请注意，我不需要确切的语法，甚至不需要易用性 - 这是一个节点类，在跳过列表类内部，它根本不是界面的一部分。

最佳答案

这是我写的实现，based on R. Martinho Fernandes's idea - 它构造了一个恰好在特定位置具有正确大小和对齐方式的缓冲区(AlignmentExtractor 用于提取指针数组的偏移量，以确保缓冲区中的指针具有正确的对齐方式)。然后，placement-new 用于构造缓冲区中的类型。

T不直接用于 AlignmentExtractor因为offsetof需要标准布局类型。

#include <cstdlib>
#include <cstddef>
#include <utility>

template<typename T>
struct ErasedNodePointer
{
    void* ptr;
};

void* allocate(std::size_t size)
{
    return ::operator new(size);
}

void deallocate(void* ptr)
{
    return ::operator delete(ptr);
}

template<typename T>
struct AlignmentExtractor
{
    static_assert(alignof(T) <= alignof(std::max_align_t), "extended alignment types not supported");
    alignas(T) char data[sizeof(T)];
    ErasedNodePointer<T> next[1];
};

template<typename T>
T& get_data(ErasedNodePointer<T> node)
{
    return *reinterpret_cast<T*>(node.ptr);
}

template<typename T>
void destroy_node(ErasedNodePointer<T> node)
{
    get_data(node).~T();
    deallocate(node.ptr);
}

template<typename T>
ErasedNodePointer<T>& get_pointer(ErasedNodePointer<T> node, int pos)
{
    auto next = reinterpret_cast<ErasedNodePointer<T>*>(reinterpret_cast<char*>(node.ptr) + offsetof(AlignmentExtractor<T>, next));
    next += pos;
    return *next;
}

template<typename T, typename... Args>
ErasedNodePointer<T> create_node(std::size_t height, Args&& ...args)
{
    ErasedNodePointer<T> p = { nullptr };
    try
    {
        p.ptr = allocate(sizeof(AlignmentExtractor<T>) + sizeof(ErasedNodePointer<T>)*(height-1));
        ::new (p.ptr) T(std::forward<T>(args)...);
        for(std::size_t i = 0; i < height; ++i)
            get_pointer(p, i).ptr = nullptr;
        return p;
    }
    catch(...)
    {
        deallocate(p.ptr);
        throw;
    }
}

#include <iostream>
#include <string>

int main()
{
    auto p = create_node<std::string>(5, "Hello world");
    auto q = create_node<std::string>(2, "A");
    auto r = create_node<std::string>(2, "B");
    auto s = create_node<std::string>(1, "C");

    get_pointer(p, 0) = q;
    get_pointer(p, 1) = r;
    get_pointer(r, 0) = s;

    std::cout << get_data(p) << "\n";
    std::cout << get_data(get_pointer(p, 0)) << "\n";
    std::cout << get_data(get_pointer(p, 1)) << "\n";
    std::cout << get_data(get_pointer(get_pointer(p, 1), 0)) << "\n";

    destroy_node(s);
    destroy_node(r);
    destroy_node(q);
    destroy_node(p);
}

输出:

Hello world
A
B
C

更长的解释:

这段代码的重点是动态创建一个节点，而不是直接使用类型(类型删除)。此节点存储一个对象，N指针，带有 N运行时变量。

您可以像使用特定类型的内存一样使用任何内存，前提是:

1. 尺寸正确
2. 对齐正确
3. (仅限不可平凡构造的类型)您在使用前手动调用构造函数
4. (仅限不可破坏的类型)您在使用后手动调用析构函数

事实上，每次调用malloc时，您都依赖于此:

// 1. Allocating a block
int* p = (int*)malloc(5 * sizeof *p);
p[2] = 42;
free(p);

在这里，我们处理由 malloc 返回的内存块就好像它是一个整数数组。由于这些保证，这必须有效:

• malloc返回保证对任何对象类型正确对齐的指针。
• 如果你的指针p指向对齐内存，(int*)((char*)p + sizeof(int)) (或 p + 1 ，这是等效的)也是如此。

动态创建的节点必须有足够的大小来包含N ErasedNodePointer s(这里用作句柄)和一个大小为 T 的对象.这可以通过在 create_node 中分配足够的内存来满足。函数 - 它将分配 sizeof(T) + sizeof(ErasedNodePointer<T>)*N字节或更多，但不少于。

这是第一步。第二个是现在我们提取相对于 block 开头的所需位置。那就是AlignmentExtractor<T>进来了。

AlignmentExtractor<T>是我用来确保正确对齐的虚拟结构:

// 2. Finding position
AlignmentExtractor<T>* p = (AlignmentExtractor<T>*)malloc(sizeof *p);
p->next[0].ptr = nullptr;
// or
void* q = (char*)p + offsetof(AlignmentExtractor<T>, next);
(ErasedTypePointer<T>*)q->ptr = nullptr;

我如何得到指针的位置并不重要，只要我遵守指针运算规则即可。

这里的假设是:

• 我可以将任何指针转换为void*并返回。
• 我可以将任何指针转换为char*并返回。
• 我可以对结构进行操作，就好像它是一个大小等于结构大小的字符数组。
• 我可以使用指针运算来指向数组的任何元素。

这些都是C++标准保证的。

现在，在我分配了足够大小的 block 之后，我用 offsetof(AlignmentExtractor<T>, next) 计算偏移量并将其添加到指向 block 的指针。我们“假装”(就像代码“1.分配 block ”假装它有一个整数数组一样)结果指针指向数组的开头。该指针已正确对齐，否则代码“2. 查找位置”无法访问 next。由于访问未对齐而导致的数组。

如果您有一个标准布局类型的结构，则指向该结构的指针与该结构的第一个成员具有相同的地址。 AlignmentExtractor<T>是标准布局。

但这还不是全部 - 要求 1. 和 2. 已得到满足，但我们需要满足要求 3. 和 4. - 节点中的数据不必是微不足道的可构造或可破坏的。这就是为什么我们使用 placement-new 来构造数据 - create_node使用可变参数模板和完美转发将参数转发给构造函数。数据在 destroy_node 中被销毁通过调用析构函数来实现功能。

关于c++ - C++ 中灵活数组成员的可移植仿真？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29682605/