jeudi 16 avril 2015

Portable emulation of flexible array member in C++?

I'm writing a skip list.


What I have:



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


The problem with this code is that it wastes space - it requires all nodes to contain 32 pointers. Especially considering that in typical list, half of the nodes will only need one pointer.


The C language has a neat feature called flexible array member that could solve that problem. Had it existed in C++ (even for trivial classes), I could write code like this:



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


and then manually create nodes with a factory function and destroying them when deleting elements.


Which brings the question - how can I emulate such functionality portably, without undefined behaviour in C++?


I considered mallocing the buffer and then manipulating the offsets appropriately by hand - but it's too easy to violate the alignment requirements - if you malloc(sizeof(char) + sizeof(void*)*5), the pointers are unaligned. Also, I'm not even sure if such hand-created buffers are portable to C++.


Note that I don't require the exact syntax, or even ease of use - this is a node class, internal to the skip list class, which won't be a part of the interface at all.


Aucun commentaire:

Enregistrer un commentaire