title: Portable emulation of flexible array member in C++?
body: <p>I'm writing a <a href="http://en.wikipedia.org/wiki/Skip_list" rel="noreferrer">skip list</a>.</p>
  
  <p>What I have:</p>
  
  <pre><code>template&lt;typename T&gt;
  struct SkipListNode
  {
      T data;
      SkipListNode* next[32];
  };
  </code></pre>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <pre><code>template&lt;typename T&gt;
  struct SkipListNode
  {
      alignas(T) char buffer[sizeof(T)];
      SkipListNode* next[];
  };
  </code></pre>
  
  <p>and then manually create nodes with a factory function and destroying them when deleting elements. </p>
  
  <p>Which brings the question - how can I emulate such functionality <em>portably</em>, without undefined behaviour in C++?</p>
  
  <p>I considered <code>malloc</code>ing the buffer and then manipulating the offsets appropriately by hand - but it's too easy to violate the alignment requirements - if you <code>malloc(sizeof(char) + sizeof(void*)*5)</code>, the pointers are unaligned. Also, I'm not even sure if such hand-created buffers are portable to C++.</p>
  
  <p>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. </p>