Verwenden Sie std :: experimental :: optional, um eine Liste zu implementieren

Question

Ich frage mich, ob es möglich ist, eine einzelne (und mögliche doppelte) verkettete Liste mit std::experimental::optional zu implementieren.

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

Was sind die Vor- und Nachteile eines solchen Designs? Könnten neue Funktionen c++1z verwendet werden, um Sentinels zu implementieren oder sie insgesamt loszuwerden? Würde dies auch auf n-stufige Bäume skalieren?

Answer 1

Es ist nicht möglich, eine verkettete Liste auf diese Weise zu implementieren, da Ihr node-Typ immer unvollständig ist. Hier ist ein more complete example, die das Problem veranschaulicht:

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

Der Punkt ist, dass optional<T>T vollständig sein erfordert aber an dem Punkt, wo Sie next definieren, node ist unvollständig. Der Grund, warum optional<T> einen vollständigen Typ benötigt, besteht darin, dass T direkt innerhalb des optional-Objekts gespeichert wird, d. H. Speicher auf dem Heap wird nicht zugewiesen. Als Ergebnis muss es die Größe T kennen. Intern enthält es einen Puffer von sizeof(T). In Bezug auf die Speicherlayout können Sie denken optional<T> als

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

aber in der Praxis ist es komplizierter ist, aufgrund von Speicherausrichtungsanforderungen.

In Ihrem Fall, um die Größe von optional<node> zu kennen, muss es die Größe von node kennen und dafür muss es die Größe von optional<node> kennen.

Answer 2

Es ist unmöglich, weil die T erfordert, um abgeschlossen zu sein.

Per N3672 (Vorschlag für std::optional):

Vorlage Klasse optional erlegt wenig Anforderungen an T: Er hat entweder ein L-Wert Referenztyp oder ein kompletter Objekttyp, das die Anforderungen von Destructible sein.