Use std::experimental::optional to implement a list

Question

I was wondering if it is possible to implement a single (and possible double) linked list using std::experimental::optional.

template <typename T>
struct node {
    std::experimental::optional<node<T>> next;
    T data;
};

What are the advantages/disadvantages of such a design? Could new c++1z features be used to implement sentinels, or getting rid of them alltogether? Would this scale up to n-ary trees as well?

Answer 1

It is not possible to implement a linked list in that way, because your node-type will always be incomplete. Here is a more complete example that illustrates the issue:

#include <iostream>
#include <experimental/optional>

template <typename T>
struct node {
    std::experimental::optional<node<T>> next;
    T data;
};

int main( int, char ** )
{
    std::cout << sizeof( node<int> ) << std::endl;
    return 0;
}

The point is that optional<T> requires T to be complete but at the point where you define next, node is incomplete. The reason why optional<T> needs a complete type is that it stores T directly within the optional object, i.e. it does not allocate memory on the heap. As a result, it has to know the size of T. Internally, it contains a buffer of sizeof( T ). In terms of memory layout, you can think of optional<T> as

template <class T>
struct optional
{
    bool _containsValue;
    char _buffer[ sizeof( T ) ];
};

but in practice, it is more complicated, due to memory alignment requirements.

In your case, in order to know the size of optional<node>, it has to know the size of node and for this it has to know the size of optional<node>.

Answer 2

It's impossible because the optional<T> requires T to be complete.

As per N3672 (the proposal for std::optional):

Class template optional imposes little requirements on T: it has to be either an lvalue reference type, or a complete object type satisfying the requirements of Destructible.