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

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?

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.

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.

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.

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
                    ...
        }
    }

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.
}

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.

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.

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.

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.