Implementieren eines std::vector ähnlichen Containers ohne undefiniertes Verhalten

Lesezeit: 5 Minuten

Implementieren eines stdvector ahnlichen Containers ohne undefiniertes Verhalten
Oliv

Es mag einige Programmierer überraschen, und so überraschend es auch sein mag, es ist nicht möglich, es zu implementieren std::vector ohne nicht standardmäßige Unterstützung der Compiler. Das Problem beruht im Wesentlichen auf der Fähigkeit, Zeigerarithmetik auf einem Rohspeicherbereich durchzuführen. Das Papier, p0593: Implizite Erstellung von Objekten für Objektmanipulation auf niedriger Ebenedas in der Antwort von @ShafikYaghmour erscheint, macht die Problematik deutlich und schlägt eine Änderung des Standards vor, um die Implementierung von vektorähnlichen Container- und anderen Programmiertechniken auf Rechtsebene zu vereinfachen.

Trotzdem habe ich mich gefragt, ob es keine Arbeit gibt, um einen entsprechenden Typ zu implementieren std::vector Verwenden Sie nur das, was von der Sprache bereitgestellt wird, ohne die Standardbibliothek zu verwenden.

Das Ziel besteht darin, Vektorelemente einzeln in einem Rohspeicherbereich zu konstruieren und mithilfe eines Iterators auf diese Elemente zugreifen zu können. Dies wäre äquivalent zu einer Folge von push_back auf einem std::vector.

Um eine Vorstellung von dem Problem zu bekommen, folgt eine Vereinfachung der Operationen, die bei der Implementierung von durchgeführt werden std::vector in der libc++ oder libstdc++:

void access_value(std::string x);

std::string s1, s2, s3;
//allocation
auto p=static_cast<std::string*>(::operator new(10*sizeof(std::string)));

//push_back s1
new(p) std::string(s1);
access_value(*p);//undefined behavior, p is not a pointer to object

//push_back s2
new(p+1) std::string(s2);//undefined behavior
        //, pointer arithmetic but no array (neither implicit array of size 1)
access_value(*(p+1));//undefined behavior, p+1 is not a pointer to object

//push_back s2
new(p+2) std::string(s3);//undefined behavior
        //, pointer arithmetic but no array
access_value(*(p+2));//undefined behavior, p+2 is not a pointer to object

Meine Idee ist es, eine Union zu verwenden, die ihr Mitglied niemals initialisiert.

//almost trivialy default constructible
template<class T>
union atdc{
  char _c;
  T value;
  atdc ()noexcept{ }
  ~atdc(){}
};

Der Rohspeicher wird mit einem Array dieses Vereinigungstyps initialisiert, und die Zeigerarithmetik wird immer auf diesem Array ausgeführt. Dann werden bei jedem push_back Elemente auf dem inaktiven Mitglied der Union konstruiert.

std::string s1, s2, s3;
auto p=::operator new(10*sizeof(std::string));
auto arr = new(p) atdc<std::string>[10];
//pointer arithmetic on arr is allowed

//push_back s1
new(&arr[0].value) std::string(s1); //union member activation
access_value(arr[0].value);

//push_back s2
new(&arr[1].value) std::string(s2);
access_value(arr[1].value);

//push_back s2
new(&arr[2].value) std::string(s2);
access_value(arr[2].value);

Gibt es ein undefiniertes Verhalten in diesem obigen Code?

  • Was ist Jura-Programmierung???

    – Yunfei Chen

    29. Juni 2020 um 17:25 Uhr

  • @YunfeiChen In C++, wenn Sie fast nur Sprachprimitive verwenden. High-Level-Programmierung ist, wenn Sie nur ausgearbeitete abstrakte Bibliotheken verwenden

    – Oliv

    29. Juni 2020 um 17:28 Uhr

Implementieren eines stdvector ahnlichen Containers ohne undefiniertes Verhalten
Shafik Yaghmur

Dies ist ein Thema, das aktiv diskutiert wird, wir können dies im Vorschlag sehen p0593: Implizite Erstellung von Objekten für Objektmanipulation auf niedriger Ebene. Dies ist eine ziemlich solide Diskussion der Probleme und warum sie nicht ohne Änderungen behoben werden können. Wenn Sie unterschiedliche Ansätze oder starke Ansichten zu den in Betracht gezogenen Ansätzen haben, können Sie sich an die Verfasser der Vorschläge wenden.

Darin enthalten ist diese Diskussion:

2.3. Dynamische Konstruktion von Arrays

Betrachten Sie dieses Programm, das versucht, einen Typ wie std::vector zu implementieren (wobei viele Details der Kürze halber weggelassen wurden):

….

In der Praxis funktioniert dieser Code in einer Reihe vorhandener Implementierungen, aber gemäß dem C++-Objektmodell tritt an den Punkten #a, #b, #c, #d und #e undefiniertes Verhalten auf, da sie versuchen, Zeigerarithmetik auszuführen ein Bereich mit zugewiesenem Speicher, der kein Array-Objekt enthält.

An den Stellen #b, #c und #d wird die Arithmetik an einem char* durchgeführt, und an den Stellen #a, #e und #f wird die Arithmetik an einem T* durchgeführt. Idealerweise würde eine Lösung dieses Problems beiden Berechnungen ein definiertes Verhalten verleihen.

  1. Sich nähern

Die obigen Ausschnitte haben ein gemeinsames Thema: Sie versuchen, Objekte zu verwenden, die sie nie erstellt haben. Tatsächlich gibt es eine Familie von Typen, für die Programmierer davon ausgehen, dass sie keine expliziten Objekte erstellen müssen. Wir schlagen vor, diese Typen zu identifizieren und sorgfältig Regeln auszuarbeiten, die die Notwendigkeit beseitigen, solche Objekte explizit zu erstellen, indem sie sie stattdessen implizit erstellen.

Der Ansatz mit der adc union hat das Problem, dass wir erwarten, über einen Pointer auf die enthaltenen Daten zugreifen zu können T* dh über std::vector::data. Zugriff auf die Gewerkschaft als T* würde gegen die strengen Aliasing-Regeln verstoßen und wäre daher ein undefiniertes Verhalten.

  • Und glauben Sie nicht, dass der von mir vorgeschlagene Trick das Problem der Zeigerarithmetik auf zugewiesenem Speicher umgeht, oder gibt es ein undefiniertes Verhalten, das ich übersehen habe?

    – Oliv

    25. Oktober 2018 um 20:24 Uhr

  • @Oliv Ich glaube, Sie haben strenge Aliasing-Probleme, da das zugrunde liegende des Vektors als gespeicherter Datentyp zugänglich sein sollte, dh über data() Methode

    – Shafik Yaghmour

    25. Oktober 2018 um 20:42 Uhr

  • Als die ersten C- und C++-Standards geschrieben wurden, hatten die Autoren keinen Grund zu der Annahme, dass sich irgendjemand darum kümmern würde, ob sie tatsächlich das Verhalten von Konstrukten definierten, die offensichtlich nützlich waren und einhellig unterstützt wurden. Sie übernahmen daher Verhaltensmodelle, die nur „praktikabel“ gemacht werden können, indem sie die Tatsache ignorieren, dass bestimmte notwendige Operationen als UB gebrandmarkt werden. Leider hat der Standard die Sprache fragmentiert, indem er nicht explizit anerkennt, dass verschiedene Implementierungen für verschiedene Zwecke verwendet werden, von denen einige Unterstützung für mehr Operationen erfordern als andere.

    – Superkatze

    26. Oktober 2018 um 21:12 Uhr

  • …in zwei Kategorien von Dialekten, von denen einer für Zwecke der Low-Level-Programmierung ungeeignet ist und der andere nur eine begrenzte Optimierung unterstützt. Gemäß der C-Rationale beinhaltet der Spirit of C das Prinzip „Hid den Programmierer nicht daran, das zu tun, was getan werden muss“. Die Optimierung auf der Grundlage der Idee, dass ein Programmierer X nicht tun wird, ist nur in den Fällen hilfreich, in denen der Programmierer X nicht tun muss. Leider verlieren die meisten Argumente über definierte Verhaltensweisen dies vollständig aus den Augen.

    – Superkatze

    26. Oktober 2018 um 21:20 Uhr

842970cookie-checkImplementieren eines std::vector ähnlichen Containers ohne undefiniertes Verhalten

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

Privacy policy