Используйте std :: experimental :: optional для реализации списка

Question

Мне было интересно, можно ли реализовать единственный (и возможный двойной) связанный список, используя std::experimental::optional.

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

В чем преимущества или недостатки такого дизайна? Могут ли новые функции c++1z использоваться для реализации стражей, или избавиться от них alltogether? Будет ли эта шкала до n-ary деревьев?

Answer 1

Невозможно реализовать связанный список таким образом, потому что ваш тип node всегда будет неполным. Вот more complete example, который иллюстрирует этот вопрос:

#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):

шаблона класса опционально накладывают небольшие требования к Т: она должна быть либо именующий ссылочный типом, или полный типа объекта, удовлетворяющие требования разрушаемости.