Können Standardcontainervorlagen mit unvollständigen Typen instanziiert werden?

Lesezeit: 5 Minuten

Konnen Standardcontainervorlagen mit unvollstandigen Typen instanziiert werden
Kartoffelklatsche

Manchmal ist es sinnvoll, einen Standardcontainer mit einem unvollständigen Typ zu instanziieren, um eine rekursive Struktur zu erhalten:

struct multi_tree_node { // Does work in most implementations
    std::vector< multi_tree_node > child;
};

struct trie_node { // Does not work in most implementations
    std::map< char, trie_node > next;
};

Dies funktioniert in der Regel, weil Container keine Member vom Typ haben value_type oder Elementfunktionen, die übergeben oder zurückgegeben werden value_type Objekte nach Wert. Der Standard scheint nicht viel über unvollständige Template-Argumente zu sagen, aber es gibt ein Bit unter C++11 §17.6.4.8 [lib.res.on.functions]”Anforderungen an andere Funktionen”:

Insbesondere sind die Auswirkungen in den folgenden Fällen undefiniert: … wenn ein unvollständiger Typ (3.9) als Template-Argument verwendet wird, wenn eine Template-Komponente instanziiert wird, es sei denn, dies ist ausdrücklich für diese Komponente erlaubt.

Macht dies die obigen Konstrukte illegal, obwohl sich die Instanziierungen nicht im Blockbereich befinden? Fällt dies unter “Operationen an Typen, die zum Instanziieren von Standardbibliotheksvorlagenkomponenten verwendet werden” (auch 17.6.4.8)? Oder ist es einer Bibliotheksimplementierung verboten, Template-Instanziierungen hervorzurufen, die bei unvollständigen Typen fehlschlagen könnten, wenn alle speziell erforderlichen Instanziierungen erfolgreich sind?

Bearbeiten: Da nur Funktionen andere Funktionen aufrufen und instanziieren können, scheint die Beschränkung von “Operationen auf Typen …” auf diejenigen im Blockbereich den Inhalt von Elementfunktionen an strengere Anforderungen zu stellen als den Inhalt von Signaturen und Elementklassendefinitionen. Schließlich macht es sicherlich keinen Sinn alles tun mit einer multi_tree_node bis der Typ fertig ist. Und das erstreckt sich auf die std::unique_ptr die explizit ein unvollständiges Typargument unterstützt, auch bei Verwendung im Blockbereich.

Bearbeiten 2: Geschieht mir recht, dass ich mir nicht die Mühe gemacht habe, das zu testen trie_node Beispiel – und ich habe es sogar schon einmal versucht. Es ist dasselbe wie im Beispiel des Einbruchs der Artikel dass @Ise verlinkt ist. Während der Artikel jedoch davon auszugehen scheint, dass „so etwas nicht funktionieren könnte“, erscheint mir die Lösung einfach – std::mapist intern tree_node Die Klasse sollte eine Nicht-Mitglieder-Vorlage sein, keine Mitglieds-Nicht-Vorlagenklasse.

Wie auch immer, dieser Artikel legt die Designabsicht ziemlich gut fest, also denke ich, dass mein Nitpick, unter der Unterüberschrift “Anforderungen an Funktionen” zu stehen, nur genau das ist.

  • Ich sehe keine unvollständigen Typen in dem von Ihnen geposteten Code?

    – Johannes Dibling

    30. November 2011 um 17:03 Uhr

  • @JohnDibling: trie_node ist beim Definieren unvollständig next.

    – Matthias M.

    30. November 2011 um 17:05 Uhr

  • @JohnDibling Im eigenen Bereich einer Klasse ist sie unvollständig.

    – Kartoffelklatsche

    30. November 2011 um 17:05 Uhr

  • Siehe auch: stackoverflow.com/questions/7210286/…

    – Björn Pollex

    30. November 2011 um 17:07 Uhr

  • Übrigens, es ist [17.4.3.6] im C++03-Standard, für alle Interessierten. Fügen Sie in diesem Fall am besten auch das Tag hinzu, unter dem der Absatz steht [lib.res.on.functions].

    – Xeo

    30. November 2011 um 17:08 Uhr


Konnen Standardcontainervorlagen mit unvollstandigen Typen instanziiert werden
Kerrek SB

Hier mein Deutungsversuch:

Der Standard sagt einfach, dass Sie dies nicht tun dürfen, obwohl eine bestimmte konkrete Implementierung möglicherweise kein Problem damit hat, eine solche Konstruktion zu unterstützen. Aber stellen Sie sich zum Beispiel vor, jemand wollte eine „kleine Vektor“-Optimierung schreiben, bei der ein Vektor immer Platz für, sagen wir, fünf Elemente enthält. Sofort wären Sie in Schwierigkeiten, weil Sie ein selbstbezogener Typ wären. Dies wäre selbst dann ein Problem, wenn der Vektor abhängig von der Größe des Wertetyps eine Art statische Verzweigung verwendet.

Um Implementierungen nicht daran zu hindern, solche Konstruktionen aufzunehmen, sagt der Standard daher einfach, dass Sie nur vollständige Typen verwenden dürfen. Mit anderen Worten, die Tatsache, dass die meisten Container nur Referenzen oder Zeiger auf den Werttyp enthalten, ist eher ein Implementierungsdetail als eine Standardanforderung.

Nur um dies zu verdeutlichen: Wenn Sie Ihre definieren eigen -Klassenvorlage ist es durchaus möglich, sie so zu gestalten, dass sie unvollständige Typen explizit unterstützt. Ein Beispiel aus dem Standard ist std::unique_ptrdie mit dem unvollständigen Typparameter vollkommen zufrieden ist T[] (oder auch void).

  • +1 großartiges Beispiel, aber ich werde auf eine Standardinterpretation ab initio warten … mein Code verstößt sicherlich gegen die zitierte Anforderung, aber der andere Teil der Frage ist, ob oder wie die Anforderung außerhalb eines Funktions- / Blockbereichs gilt. (Da nur Funktionen andere Funktionen aufrufen und instanziieren können, scheint dies den Inhalt von Elementfunktionen auf einem anderen Standard zu halten als den Inhalt von Signaturen und Elementklassendefinitionen.)

    – Kartoffelklatsche

    30. November 2011 um 17:23 Uhr


  • “kleiner Vektor” ist kein gutes Beispiel; dass die Optimierung vom Standard nicht erlaubt ist.

    – TC

    7. März 2015 um 3:39 Uhr


Mir persönlich gefällt die Formulierung Instanziieren in 17.6.4.8/2 ist etwas mehrdeutig, aber gem
Dieser Beitragscheint die Absicht des Standards keine rekursiven Datentypen mit Standardcontainern zuzulassen.

In diesem Zusammenhang gibt VC2005 einen Fehler für aus
class C { std::deque< C > x; };während es kompiliert
class C { std::vector< C > x; };
Allerdings dient diese Einschränkung nach meinem Verständnis nur dazu, die Freiheit bei der Implementierung von Standardcontainern zu erweitern. So wie Kerrek SB erwähnt, kann es Container geben, die eine rekursive Datenstruktur zulassen, und
Boost.Container
scheint diese Möglichkeit zu bieten.

Im Allgemeinen ist die Verwendung eines unvollständigen Typs als Vorlagenparameter für eine Standardbibliothekskomponente UB. Hier ist die Hinweis:

Wenn ein unvollständiger Typ ([basic.types]) wird als Vorlagenargument verwendet, wenn eine Vorlagenkomponente instanziiert oder ein Konzept ausgewertet wird, es sei denn, dies ist ausdrücklich für diese Komponente erlaubt.

Beachten Sie, dass seit c++17 eine explizite Berechtigung erteilt wurde std::vector um unvollständige Typen zuzulassen. Hier ist die Hinweis:

Ein unvollständiger Typ T kann beim Instanziieren eines Vektors verwendet werden, wenn der Zuordner die Vollständigkeitsanforderungen des Zuordners erfüllt. T muss vollständig sein, bevor auf irgendein Mitglied der resultierenden Spezialisierung von Vektor verwiesen wird.

Also in deinem Beispiel multi_tree_node ist gut geformt, aber trie_node ist U.B.

923390cookie-checkKönnen Standardcontainervorlagen mit unvollständigen Typen instanziiert werden?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy