使用std :: experimental :: optional来实现列表

Question

我想知道是否可以使用实现单个(和可能的双重)链表std::experimental::optional.

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

这种设计有哪些优点/缺点？可以使用新c++1z功能来实现哨兵,还是完全摆脱它们？这会扩大到n-ary树吗？

Answer 1

以这种方式实现链接列表是不可能的,因为您的node-type将始终不完整.这是一个更完整的示例,说明了该问题:

#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;
}

关键是optional<T>要求T完整,但在您定义的地方next,node是不完整的.optional<T>需要完整类型的原因是它T直接存储在optional对象中,即它不在堆上分配内存.结果,它必须知道的大小T.在内部,它包含一个缓冲区sizeof( T ).在内存布局方面,您可以将其optional<T>视为

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

但实际上,由于内存对齐要求,它更复杂.

在你的情况,才能知道的大小optional<node>,它必须知道的大小node,为此它必须知道的大小optional<node>.

Answer 2

这是不可能的,因为optional<T>要求T是完整的.

根据N3672(提案std::optional):

类模板可选对T施加很少的要求:它必须是左值引用类型,或满足Destructible要求的完整对象类型.