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