Ist es sicher, ein Element aus demselben Vektor zurückzuschieben?

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

Wenn der zweite push_back eine Neuzuweisung 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?

Neil Kirk
quelle
4
Ein Hinweis: Derzeit wird im Forum für Standardvorschläge diskutiert. Als Teil davon gab jemand eine Beispielimplementierung vonpush_back . Ein anderes Poster bemerkte einen Fehler darin , dass es den von Ihnen beschriebenen Fall nicht richtig behandelte. Soweit ich das beurteilen kann, hat niemand anders argumentiert, dass dies kein Fehler war. Das heißt nicht, dass dies ein schlüssiger Beweis ist, sondern nur eine Beobachtung.
Benjamin Lindley
9
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
4
Ich wurde gebeten, diese Frage durch den 5. Kommentar unter: stackoverflow.com/a/18647445/576911 zu kommentieren . Dazu stimme ich jeder Antwort zu, die derzeit lautet: Ja, es ist sicher, ein Element aus demselben Vektor zurückzuschieben.
Howard Hinnant
2
@BenVoigt: <Achselzucken> Wenn Sie mit den Aussagen des Standards nicht einverstanden sind oder auch wenn Sie mit dem Standard einverstanden sind, aber nicht der Meinung sind, dass er dies 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 darüber diskutieren möchten, was der Standard sagt oder was er sagen sollte, ist SO kein effektives Forum. Unser Gespräch hat keine normative Bedeutung. Sie können jedoch eine Chance auf eine normative Auswirkung haben, indem Sie dem obigen Link folgen.
Howard Hinnant
2
@ Polaris878 Wenn push_back bewirkt, 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 eine Referenz auf Daten im alten Puffer ist, die gerade gelöscht wurden. Sofern push_back vor dem Löschen keine Kopie des Werts erstellt, handelt es sich um eine fehlerhafte Referenz.
Neil Kirk

Antworten:

31

Es sieht so aus, als ob http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 dieses Problem (oder etwas sehr Ähnliches) als potenziellen Fehler in der Norm angesprochen hat:

1) Parameter, die von const reference übernommen 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

Die vorgeschlagene Lösung war, dass dies kein Mangel war:

vector :: insert (iter, value) ist erforderlich, um zu funktionieren, da der Standard keine Berechtigung dafür gibt, dass er nicht funktioniert.

Nate Kohl
quelle
Ich finde die Berechtigung 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 erfolgt, werden alle Iteratoren und Verweise auf Elemente ungültig, was bedeutet, dass die an die Funktion übergebene Parameterreferenz ebenfalls ungültig ist.
Ben Voigt
4
Ich denke, der Punkt ist, dass die Implementierung für die Neuzuweisung verantwortlich ist. Es obliegt ihm sicherzustellen, dass das Verhalten definiert wird, wenn die Eingabe anfänglich definiert wird. Da in den Spezifikationen eindeutig angegeben ist, dass push_back eine Kopie erstellt, müssen Implementierungen auf Kosten der Ausführungszeit möglicherweise alle Werte zwischenspeichern oder kopieren, bevor die Zuordnung aufgehoben wird. Da in dieser speziellen Frage keine externen Referenzen mehr vorhanden sind, spielt es keine Rolle, ob Iteratoren und Referenzen ungültig sind.
OlivierD
3
@NeilKirk Ich denke, dies sollte die maßgebliche Antwort sein, es wird auch von Stephan T. Lavavej auf Reddit mit im Wesentlichen den gleichen Argumenten erwähnt.
TemplateRex
v.insert(v.begin(), v[2]);kann keine Neuzuweisung auslösen. Wie beantwortet dies die Frage?
ThomasMcLeod
@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
21

Ja, es ist sicher, und Standardbibliotheksimplementierungen springen durch die Rahmen, um dies zu erreichen.

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.drdobbs.com/cpp/copying-container-elements-from-the-c-li/240155771

Die Überprüfung der Implementierungen von libc ++ und libstdc ++ zeigt, dass sie auch sicher sind.

Sebastian Redl
quelle
9
Eine gewisse Unterstützung würde hier wirklich helfen.
Chris
3
Das ist interessant, ich muss zugeben, ich hatte den Fall nie in Betracht gezogen, aber es scheint tatsächlich ziemlich schwierig zu sein, ihn zu erreichen. Gilt es auch für vec.insert(vec.end(), vec.begin(), vec.end());?
Matthieu M.
2
@MatthieuM. Nein: In Tabelle 100 heißt es: "pre: i und j sind keine Iteratoren in a".
Sebastian Redl
2
Ich stimme jetzt zu, da dies auch meine Erinnerung ist, aber eine Referenz wird benötigt.
Bames53
3
Ist 23.2 / 11 in der von Ihnen verwendeten Version "Sofern nicht anders angegeben (entweder explizit oder durch Definieren einer Funktion in Bezug auf andere Funktionen), werden durch Aufrufen einer Containerelementfunktion oder Übergeben eines Containers als Argument an eine Bibliotheksfunktion Iteratoren nicht ungültig zu oder Ändern der Werte von Objekten in diesem Container. " ? Aber vector.push_backgibt es anders an. "Verursacht eine Neuzuweisung, wenn die neue Größe größer als die alte Kapazität ist." und (at reserve) "Neuzuweisung macht alle Referenzen, Zeiger und Iteratoren ungültig, die sich auf die Elemente in der Sequenz beziehen."
Ben Voigt
13

Der Standard garantiert, dass auch Ihr erstes Beispiel sicher ist. Zitieren von C ++ 11

[sequence.reqmts]

3 In den Tabellen 100 und 101 Xbezeichnet ... eine Sequenzcontainerklasse , abezeichnet einen Wert, der XElemente vom Typ enthält T, ... tbezeichnet einen l-Wert oder einen konstanten Wert vonX::value_type

16 Tabelle 101 ...

Ausdruck a.push_back(t) Rückgabetyp void operationale Semantik Hängt eine Kopie t. benötigt: T wird sein CopyInsertablein X. Container basic_string , deque, list,vector

Auch wenn dies nicht gerade trivial ist, muss die Implementierung sicherstellen, dass die Referenz bei der Ausführung nicht ungültig wird push_back.

Angew ist nicht mehr stolz auf SO
quelle
7
Ich sehe nicht ein, wie dies die Sicherheit garantiert.
Jrok
4
@Angew: Es macht absolut ungültig t, die einzige Frage ist, ob vor oder nach dem Erstellen der Kopie. Dein letzter Satz ist sicherlich falsch.
Ben Voigt
4
@BenVoigt Da tdie aufgeführten Voraussetzungen erfüllt sind, ist das beschriebene Verhalten garantiert. Eine Implementierung darf eine Vorbedingung nicht ungültig machen und diese dann als Entschuldigung dafür verwenden, sich nicht wie angegeben zu verhalten.
Bames53
8
@BenVoigt Der Kunde ist nicht verpflichtet, die Vorbedingungen während des gesamten Anrufs aufrechtzuerhalten. Nur um sicherzustellen, dass es bei der Einleitung des Anrufs erfüllt wird.
Bames53
6
@BenVoigt Das ist ein guter Punkt, aber ich glaube, dass der an übergebene Funktor for_eacherforderlich ist, um die Iteratoren nicht ungültig zu machen. Ich kann keine Referenz für finden for_each, aber ich sehe auf einigen Algorithmen Text wie "op und binary_op sollen Iteratoren oder Unterordnungen nicht ungültig machen".
Bames53
7

Es ist nicht offensichtlich, dass das erste Beispiel sicher ist, da die einfachste Implementierung push_backdarin besteht, den Vektor bei Bedarf zuerst neu zuzuweisen und dann die Referenz zu kopieren.

Zumindest scheint es mit Visual Studio 2010 sicher zu sein. Durch die Implementierung von push_backwird der Fall speziell behandelt, 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
                    ...
        }
    }
Johan Råde
quelle
8
Ich würde gerne wissen, ob die Spezifikation dies erfordert, um sicher zu sein.
Nawaz
1
Nach dem Standard ist es nicht erforderlich, sicher zu sein. Es ist jedoch möglich, es auf sichere Weise umzusetzen.
Ben Voigt
2
@ BenVoigt Ich würde sagen, es ist erforderlich, sicher zu sein (siehe meine Antwort).
Angew ist nicht mehr stolz auf SO
2
@BenVoigt Zum Zeitpunkt der Übergabe der Referenz ist sie gültig.
Angew ist nicht mehr stolz auf SO
4
@Angew: Das reicht nicht aus. Sie müssen eine Referenz übergeben, die für die Dauer des Anrufs gültig bleibt, und dies ist nicht der Fall.
Ben Voigt
3

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

Diestd::vector::push_back Aufrufe von libc ++,__push_back_slow_path wenn Speicher neu zugewiesen werden 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.
}
Nate Kohl
quelle
Die Kopie muss nicht nur vor der Freigabe des vorhandenen Speichers erstellt werden, sondern auch vor dem Verschieben aus den vorhandenen Elementen. Ich nehme an, dass das Verschieben vorhandener Elemente in erfolgt __swap_out_circular_buffer. In diesem Fall ist diese Implementierung tatsächlich sicher.
Ben Voigt
@ BenVoigt: Guter Punkt, und Sie haben in der Tat Recht, dass die Bewegung im Inneren geschieht __swap_out_circular_buffer. (Ich habe einige Kommentare hinzugefügt, um das zu beachten.)
Nate Kohl
1

Die erste Version ist definitiv NICHT sicher:

Operationen an Iteratoren, die durch Aufrufen eines Standardbibliothekscontainers oder einer Zeichenfolgenelementfunktion erhalten werden, können auf den zugrunde liegenden Container zugreifen, dürfen ihn jedoch nicht ändern. [Hinweis: Insbesondere stehen Containeroperationen, die Iteratoren ungültig machen, in Konflikt mit Operationen an Iteratoren, die diesem Container zugeordnet sind. - Endnote]

ab Abschnitt 17.6.5.9


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

Ben Voigt
quelle
1
Es sollte verstanden werden, dass dies eine Notiz ist, keine Regel, also erklärt es eine Konsequenz der vorstehenden Regel ... und die Konsequenzen sind für Referenzen identisch.
Ben Voigt
5
Das Ergebnis von v[0]ist kein Iterator, ebenfalls push_back()kein Iterator. Aus Sicht eines Sprachrechtsanwalts ist Ihr Argument also nichtig. Es tut uns leid. Ich weiß, dass die meisten Iteratoren Zeiger sind und der Punkt, an dem ein Iterator ungültig gemacht wird, fast der gleiche ist wie bei Referenzen, aber der Teil des Standards, den Sie zitieren, ist für die jeweilige Situation irrelevant.
cmaster
-1. Es ist ein völlig irrelevantes Zitat und beantwortet es sowieso nicht. Das Komitee sagt, x.push_back(x[0])ist sicher.
Nawaz
0

Es ist völlig sicher.

In Ihrem zweiten Beispiel haben Sie

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

Dies wird nicht benötigt, da ein Vektor, der seine Größe überschreitet, das impliziert reserve.

Vector ist für dieses Zeug verantwortlich, nicht Sie.

Zaffy
quelle
-1

Beide sind sicher, da push_back den Wert und nicht die Referenz kopiert. Wenn Sie Zeiger speichern, ist dies für den Vektor immer noch sicher, aber Sie müssen nur wissen, dass zwei Elemente Ihres Vektors auf dieselben Daten zeigen.

Abschnitt 23.2.1 Allgemeine Containeranforderungen

16
  • a.push_back (t) Hängt eine Kopie von t an. Benötigt: T muss CopyInsertable in X sein.
  • a.push_back (rv) Hängt eine Kopie von rv an. Benötigt: T muss MoveInsertable in X sein.

Implementierungen von push_back müssen daher sicherstellen, dass eine Kopie von v[0] eingefügt wird. Wenn beispielsweise eine Implementierung angenommen wird, die vor dem Kopieren neu zugewiesen wird, wird eine Kopie v[0]der Spezifikationen nicht sicher angehängt und verstößt somit gegen die Spezifikationen.

OlivierD
quelle
2
push_backDie Größe des Vektors wird jedoch ebenfalls geändert , und in einer naiven Implementierung wird dadurch die Referenz ungültig, bevor das Kopieren erfolgt. Wenn Sie dies nicht durch ein Zitat aus dem Standard belegen können, halte ich es für falsch.
Konrad Rudolph
4
Mit "dies" meinen Sie das erste oder das zweite Beispiel? push_backkopiert den Wert in den Vektor; Aber (soweit ich sehen kann) kann dies nach der Neuzuweisung passieren. Ab diesem Zeitpunkt ist die Referenz, von der kopiert werden soll, nicht mehr gültig.
Mike Seymour
1
push_backerhält sein Argument durch Bezugnahme .
Bames53
1
@OlivierD: Es müsste (1) neuen Speicherplatz zuweisen (2) das neue Element kopieren (3) verschieben - die vorhandenen Elemente konstruieren (4) die verschobenen Elemente zerstören (5) den alten Speicher freigeben - in DIESER Reihenfolge - damit die erste Version funktioniert.
Ben Voigt
1
@BenVoigt Warum sollte ein Container sonst verlangen, dass ein Typ CopyInsertable ist, wenn diese Eigenschaft trotzdem vollständig ignoriert wird?
OlivierD
-2

Vom 23.3.6.5/1: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

Da wir am Ende einfügen, werden keine Referenzen ungültig, wenn die Größe des Vektors nicht geändert wird. Wenn der Vektor also capacity() > size()funktioniert, funktioniert er garantiert, andernfalls handelt es sich garantiert um undefiniertes Verhalten.

Mark B.
quelle
Ich glaube, dass die Spezifikation tatsächlich garantiert, dass dies in beiden Fällen funktioniert. Ich warte jedoch auf eine Referenz.
Bames53
In der Frage werden Iteratoren oder Iteratorsicherheit nicht erwähnt.
OlivierD
3
@OlivierD Der Iterator-Teil ist hier überflüssig: Ich interessiere mich für den referencesTeil des Zitats.
Mark B
2
Es ist tatsächlich garantiert sicher (siehe meine Antwort, Semantik von push_back).
Angew ist nicht mehr stolz auf SO