Ist es sicher, ein Element aus demselben Vektor zu push_back?

Lesezeit: 9 Minuten

Ist es sicher ein Element aus demselben Vektor zu push back
Neil Kirk

vector<int> v;
v.push_back(1);
v.push_back(v[0]);

Wenn der zweite push_back eine Neuzuordnung verursacht, ist der Verweis auf die erste Ganzzahl im Vektor nicht mehr gültig. Das ist also nicht sicher?

vector<int> v;
v.push_back(1);
v.reserve(v.size() + 1);
v.push_back(v[0]);

Das macht es sicher?

  • Ein Hinweis: Es gibt derzeit eine Diskussion im Forum für Standardvorschläge. Als Teil davon gab jemand eine Beispielimplementierung von push_back. Noch ein Plakat bemerkte einen Fehler darin, dass es den von Ihnen beschriebenen Fall nicht richtig gehandhabt hat. Soweit ich das beurteilen kann, hat niemand sonst behauptet, dass dies kein Fehler sei. Ich sage nicht, dass das ein schlüssiger Beweis ist, nur eine Beobachtung.

    – Benjamin Lindley

    13. September 13 um 15:33 Uhr

  • Es tut mir leid, aber ich weiß nicht, welche Antwort ich akzeptieren soll, da es immer noch Kontroversen über die richtige Antwort gibt.

    – Neil Kirk

    13. September 13 um 15:35 Uhr

  • Ich wurde gebeten, diese Frage vom 5. Kommentar unter: stackoverflow.com/a/18647445/576911 zu kommentieren. Ich tue dies, indem ich jede Antwort positiv bewerte, die derzeit besagt: Ja, es ist sicher, ein Element aus demselben Vektor zu push_back.

    – Howard Hinnant

    14. September 13 um 3:11 Uhr

  • @BenVoigt: Wenn Sie mit dem, was der Standard sagt, nicht einverstanden sind oder sogar dem Standard zustimmen, aber denken, dass er es nicht klar genug sagt, ist dies immer eine Option für Sie: cplusplus.github.io/LWG/lwg-active.html#submit_issue Ich habe diese Option selbst öfter gewählt, als ich mich erinnern kann. Mal erfolgreich, mal nicht. Wenn Sie diskutieren möchten, was der Standard sagt oder sagen sollte, ist SO kein effektives Forum. Unser Gespräch hat keine normative Bedeutung. Aber Sie können eine Chance auf eine normative Wirkung haben, indem Sie dem obigen Link folgen.

    – Howard Hinnant

    15. September 13 um 3:02 Uhr


  • @Polaris878 Wenn push_back dazu führt, dass der Vektor seine Kapazität erreicht, weist der Vektor einen neuen, größeren Puffer zu, kopiert die alten Daten und löscht dann den alten Puffer. Dann wird das neue Element eingefügt. Das Problem ist, dass das neue Element ein Verweis auf Daten im alten Puffer ist, der gerade gelöscht wurde. Wenn push_back vor dem Löschen keine Kopie des Werts erstellt, ist dies eine schlechte Referenz.

    – Neil Kirk

    19. September 13 um 9:27 Uhr

Es sieht aus wie http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 hat dieses Problem (oder etwas sehr ähnliches) als potenziellen Fehler im Standard angesprochen:

1) Parameter, die von der konstanten Referenz genommen werden, können während der Ausführung der Funktion geändert werden

Beispiele:

Gegeben std::vector v:

v.insert(v.begin(), v[2]);

v[2] kann durch Verschieben von Vektorelementen geändert werden

Der Lösungsvorschlag lautete, dass dies kein Mangel sei:

vector::insert(iter, value) muss funktionieren, da der Standard keine Erlaubnis dafür gibt, dass es nicht funktioniert.

  • Ich finde die Erlaubnis in 17.6.4.9: “Wenn ein Argument für eine Funktion einen ungültigen Wert hat (z. B. einen Wert außerhalb der Domäne der Funktion oder einen Zeiger, der für die beabsichtigte Verwendung ungültig ist), ist das Verhalten undefiniert.” Wenn eine Neuzuweisung auftritt, werden alle Iteratoren und Referenzen auf Elemente ungültig, was bedeutet, dass die an die Funktion übergebene Parameterreferenz ebenfalls ungültig ist.

    – Ben Voigt

    15. September 13 um 0:54 Uhr

  • Ich denke, der Punkt ist, dass die Implementierung für die Neuzuweisung verantwortlich ist. Es obliegt ihm sicherzustellen, dass das Verhalten definiert ist, wenn die Eingabe anfänglich definiert ist. Da die Spezifikationen eindeutig angeben, dass push_back eine Kopie erstellt, müssen Implementierungen, möglicherweise auf Kosten der Ausführungszeit, alle Werte zwischenspeichern oder kopieren, bevor sie die Zuweisung aufheben. Da in dieser speziellen Frage keine externen Referenzen mehr vorhanden sind, spielt es keine Rolle, ob Iteratoren und Referenzen ungültig gemacht werden.

    – OlivierD

    16. September 13 um 21:36 Uhr

  • @NeilKirk Ich denke, dies sollte die maßgebliche Antwort sein, sie wird auch von Stephan T. Lavavej erwähnt auf reddit mit im Wesentlichen den gleichen Argumenten.

    – TemplateRex

    20. September 13 um 12:50 Uhr

  • v.insert(v.begin(), v[2]); kann keine Umverteilung auslösen. Wie beantwortet dies die Frage?

    – Thomas McLeod

    3. März 17 um 16:20 Uhr

  • @ThomasMcLeod: Ja, es kann offensichtlich eine Neuzuweisung auslösen. Sie erweitern die Größe des Vektors, indem Sie ein neues Element einfügen.

    – Violette Giraffe

    23. Juli 19 um 12:11 Uhr

1644072669 712 Ist es sicher ein Element aus demselben Vektor zu push back
Sebastian Redl

Ja, es ist sicher, und Implementierungen von Standardbibliotheken springen durch die Reifen, um es so zu machen.

Ich glaube, dass Implementierer diese Anforderung irgendwie auf 23.2/11 zurückführen, aber ich kann nicht herausfinden, wie, und ich kann auch nichts Konkreteres finden. Das Beste, was ich finden kann, ist dieser Artikel:

http://www.drdobs.com/cpp/copying-container-elements-from-the-c-li/240155771

Die Untersuchung der Implementierungen von libc++ und libstdc++ zeigt, dass sie ebenfalls sicher sind.

  • Etwas Rückendeckung würde hier wirklich helfen.

    – Chris

    13. September 13 um 14:32 Uhr

  • Das ist interessant, ich muss zugeben, dass ich den Fall nie in Betracht gezogen habe, aber es scheint tatsächlich ziemlich schwierig zu erreichen zu sein. Gilt auch für vec.insert(vec.end(), vec.begin(), vec.end()); ?

    – Matthias M.

    13. September 13 um 14:32 Uhr

  • @MatthieuM. Nein: Tabelle 100 sagt: “pre: i und j are not iterators into a”.

    – Sebastian Redl

    13. September 13 um 14:34 Uhr

  • Ich stimme jetzt hoch, da dies auch meine Erinnerung ist, aber eine Referenz ist erforderlich.

    – Namen53

    13. September 13 um 14:55 Uhr


  • Ist 23.2/11 in der Version, die Sie verwenden “Wenn nicht anders angegeben (entweder explizit oder durch Definition einer Funktion in Bezug auf andere Funktionen), werden Iteratoren durch das Aufrufen einer Container-Member-Funktion oder das Übergeben eines Containers als Argument an eine Bibliotheksfunktion nicht ungültig Objekte innerhalb dieses Containers ändern oder deren Werte ändern.” ? Aber vector.push_back Gibt etwas anderes an. “Verursacht eine Neuzuweisung, wenn die neue Größe größer als die alte Kapazität ist.” und (bei reserve) “Die Neuzuweisung macht alle Verweise, Zeiger und Iteratoren ungültig, die sich auf die Elemente in der Sequenz beziehen.”

    – Ben Voigt

    13. September 13 um 19:07 Uhr

1644072669 307 Ist es sicher ein Element aus demselben Vektor zu push back
Angew ist nicht mehr stolz auf SO

Der Standard garantiert, dass selbst Ihr erstes Beispiel sicher ist. C++11 zitieren

[sequence.reqmts]

3 In den Tabellen 100 und 101 … X bezeichnet eine Sequenzcontainerklasse, a bezeichnet einen Wert von X enthält Elemente vom Typ T, … t bezeichnet einen lvalue oder einen const rvalue von X::value_type

16 Tabelle 101 …

Ausdruck a.push_back

Auch wenn es nicht gerade trivial ist, muss die Implementierung garantieren, dass die Referenz dabei nicht ungültig wird push_back.

  • Ich sehe nicht, wie dies garantiert, dass dies sicher ist.

    – jrok

    13. September 13 um 15:03 Uhr

  • @Angew: Es macht absolut ungültig t, die Frage ist nur, ob vor oder nach dem Kopieren. Dein letzter Satz ist sicher falsch.

    – Ben Voigt

    13. September 13 um 15:06 Uhr

  • @BenVoigt Seit t die aufgeführten Voraussetzungen erfüllt, ist das beschriebene Verhalten gewährleistet. Einer Implementierung ist es nicht gestattet, eine Vorbedingung ungültig zu machen und diese dann als Entschuldigung dafür zu verwenden, sich nicht wie angegeben zu verhalten.

    – Namen53

    13. September 13 um 15:06 Uhr

  • @BenVoigt Der Client ist nicht verpflichtet, die Vorbedingung während des gesamten Anrufs aufrechtzuerhalten; nur um sicherzustellen, dass es bei der Initiierung des Anrufs erfüllt wird.

    – Namen53

    13. September 13 um 15:08 Uhr

  • @BenVoigt Das ist ein guter Punkt, aber ich glaube, dass der Funktor an ihn übergeben wurde for_each ist erforderlich, um die Iteratoren nicht ungültig zu machen. Ich kann keine Referenz für finden for_each, aber ich sehe bei einigen Algorithmen Text wie "op und binary_op sollen Iteratoren oder Unterbereiche nicht ungültig machen".

    – Namen53

    13. September 13 um 15:25 Uhr


1644072669 3 Ist es sicher ein Element aus demselben Vektor zu push back
Johan Rade

Es ist nicht offensichtlich, dass das erste Beispiel sicher ist, da die einfachste Implementierung von push_back wäre, den Vektor bei Bedarf zuerst neu zuzuweisen und dann die Referenz zu kopieren.

Aber zumindest scheint es mit Visual Studio 2010 sicher zu sein. Seine Implementierung von push_back behandelt den Fall speziell, wenn Sie ein Element im Vektor zurückschieben. Der Code ist wie folgt aufgebaut:

void push_back(const _Ty& _Val)
    {   // insert element at end
    if (_Inside(_STD addressof(_Val)))
        {   // push back an element
                    ...
        }
    else
        {   // push back a non-element
                    ...
        }
    }

1644072670 503 Ist es sicher ein Element aus demselben Vektor zu push back
Nat Kohl

Dies ist keine Garantie des Standards, aber als weiterer Datenpunkt, v.push_back(v[0]) ist sicher für libc++ von LLVM.

libc++s std::vector::push_back Anrufe __push_back_slow_path wenn es Speicher neu zuweisen muss:

void __push_back_slow_path(_Up& __x) {
  allocator_type& __a = this->__alloc();
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), 
                                                  size(), 
                                                  __a);
  // Note that we construct a copy of __x before deallocating
  // the existing storage or moving existing elements.
  __alloc_traits::construct(__a, 
                            _VSTD::__to_raw_pointer(__v.__end_), 
                            _VSTD::forward<_Up>(__x));
  __v.__end_++;
  // Moving existing elements happens here:
  __swap_out_circular_buffer(__v);
  // When __v goes out of scope, __x will be invalid.
}

  • Die Kopie muss nicht nur erstellt werden, bevor der vorhandene Speicher freigegeben wird, sondern auch, bevor die vorhandenen Elemente verschoben werden. Ich nehme an, das Verschieben bestehender Elemente ist abgeschlossen __swap_out_circular_buffer, in diesem Fall ist diese Implementierung tatsächlich sicher.

    – Ben Voigt

    13. September 13 um 17:47 Uhr

  • @BenVoigt: Guter Punkt, und Sie haben in der Tat Recht, dass der Umzug im Inneren stattfindet __swap_out_circular_buffer. (Ich habe einige Kommentare hinzugefügt, um dies zu vermerken.)

    – Nate Kohl

    13. September 13 um 19:08 Uhr


Die erste Version ist definitiv NICHT sicher:

Operationen an Iteratoren, die durch Aufrufen eines Standardbibliothekscontainers oder einer Zeichenfolgenmitgliedsfunktion erhalten werden, können auf den zugrunde liegenden Container zugreifen, dürfen ihn jedoch nicht ändern. [ Note: In particular, container operations that invalidate iterators conflict with operations on iterators associated with that container. — end note ]

aus Abschnitt 17.6.5.9


Beachten Sie, dass dies der Abschnitt über Datenrennen ist, an den die Leute normalerweise in Verbindung mit Threading denken ... aber die eigentliche Definition beinhaltet "passiert vor" Beziehungen, und ich sehe keine Ordnungsbeziehung zwischen den mehreren Nebenwirkungen von push_back hier im Spiel, nämlich die Referenzinvalidierung scheint in Bezug auf die Kopierkonstruktion des neuen Schwanzelements nicht als geordnet definiert zu sein.

  • Die Kopie muss nicht nur erstellt werden, bevor der vorhandene Speicher freigegeben wird, sondern auch, bevor die vorhandenen Elemente verschoben werden. Ich nehme an, das Verschieben bestehender Elemente ist abgeschlossen __swap_out_circular_buffer, in diesem Fall ist diese Implementierung tatsächlich sicher.

    – Ben Voigt

    13. September 13 um 17:47 Uhr

  • @BenVoigt: Guter Punkt, und Sie haben in der Tat Recht, dass der Umzug im Inneren stattfindet __swap_out_circular_buffer. (Ich habe einige Kommentare hinzugefügt, um dies zu vermerken.)

    – Nate Kohl

    13. September 13 um 19:08 Uhr


Es ist absolut sicher.

In Ihrem zweiten Beispiel haben Sie

v.reserve(v.size() + 1);

was nicht benötigt wird, denn wenn der Vektor seine Größe überschreitet, wird dies impliziert reserve.

Vector ist für diese Dinge verantwortlich, nicht Sie.

.

784440cookie-checkIst es sicher, ein Element aus demselben Vektor zu push_back?

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

Privacy policy