Sind std::vector Elemente garantiert zusammenhängend?

Lesezeit: 2 Minuten

Sind stdvector Elemente garantiert zusammenhangend
Martin Cott

Meine Frage ist einfach: sind std::vector Elemente, die garantiert zusammenhängend sind? Mit anderen Worten, kann ich den Zeiger auf das erste Element von a verwenden std::vector als C-Array?

Wenn ich mich recht erinnere, gab der C++-Standard keine solche Garantie. Allerdings ist die std::vector Anforderungen waren derart, dass es praktisch unmöglich war, sie zu erfüllen, wenn die Elemente nicht zusammenhängend waren.

Kann das jemand klären?

Beispiel:

std::vector<int> values;
// ... fill up values

if( !values.empty() )
{
    int *array = &values[0];
    for( int i = 0; i < values.size(); ++i )
    {
        int v = array[i];
        // do something with 'v'
    }
}

  • Ich weiß, dass du in Schwierigkeiten steckst, wenn du mutierst values darin if Block. Ich kenne die Antwort auf Ihre Frage nicht, also hinterlasse ich nur einen Kommentar. 🙂

    – Gregor D

    11. Mai 2009 um 17:40 Uhr

  • @Greg: Was für Probleme – kannst du ein wenig näher darauf eingehen?

    – Reunanen

    11. Mai 2009 um 17:43 Uhr

  • Ich nehme an, er meinte, dass das Drücken neuer Werte ein “Realloc” auslösen kann, wodurch das Array ungültig wird.

    – Martin Côte

    11. Mai 2009 um 17:52 Uhr

  • Anrufe, die mutieren valuesinsbesondere die ihre Größe ändern (z. B. push_back()), kann eine Neuzuordnung des zugrunde liegenden Vektors veranlassen, die den kopierten Zeiger ungültig macht array. Es ist das gleiche Prinzip hinter der Verwendung eines vector::iterator anstelle eines Zeigers in den Vektor. 🙂

    – Gregor D

    11. Mai 2009 um 17:52 Uhr

  • Ja, ich habe die “s um Werte gesetzt, um klarzustellen, dass ich über die Klasse selbst spreche, nicht über die darin enthaltenen Werte. 🙂 Unglückliche Benennung und all das. Ich glaube nicht, dass es wirklich ein Problem im allgemeinen Fall ist, in dem diese Frage relevant ist – warum sollte jemand einen Zeiger auf den Speicher greifen und dann anfangen, mit dem Vektor herumzuspielen, anstatt den Zeiger zu verwenden? Albernheit.

    – Gregor D

    11. Mai 2009 um 17:58 Uhr

Dies wurde im eigentlichen C++98-Standard übersehen, aber später als Teil eines TR hinzugefügt. Der kommende C++0x-Standard wird dies natürlich als Anforderung enthalten.

Aus n2798 (Entwurf von C++0x):

23.2.6 Klassenschablonenvektor [vector]

1 Ein Vektor ist ein Sequenzcontainer, der Iteratoren mit wahlfreiem Zugriff unterstützt. Darüber hinaus unterstützt es (amortisierte) konstante Einfüge- und Löschvorgänge am Ende; Einfügen und Löschen in der Mitte dauern linear. Die Speicherverwaltung erfolgt automatisch, es können jedoch Hinweise zur Effizienzsteigerung gegeben werden. Die Elemente eines Vektors werden zusammenhängend gespeichert, was bedeutet, dass wenn v ein Vektor ist, bei dem T ein anderer Typ als bool ist, er der Identität &v gehorcht[n] == &v[0] + n für alle 0 <= n < v.size().

  • Dies ist auch in ISO 14882, 2. Ausgabe: Abschnitt 23.2.4 angegeben [lib.vector]: „Die Elemente eines Vektors werden zusammenhängend gespeichert, was bedeutet, dass wenn v ein Vektor ist, wobei T ein anderer Typ als bool ist, dann gehorcht es der Identität &v[n] == &v[0] + n für alle 0 <= n < v.size()."

    – Mike Caron

    11. Mai 2009 um 17:52 Uhr

  • also s,TR,TC, 🙂 Eigentlich heißt C++03 auch C++98-TC1 (technische Korrektur) von dem, was ich gelesen habe

    – Johannes Schaub – litb

    11. Mai 2009 um 18:02 Uhr

  • Was ist mit Vektoren von Vektoren? Innere Vektoren sind direkt nach den inneren Vektoren der letzten Gruppe?

    – huseyin tugrul buyukisik

    4. April 2016 um 20:04 Uhr

  • @huseyin tugrul buyukisik hast du die Antwort darauf gelernt? Ich frage mich auch, wie das funktioniert

    – David Doria

    27. Oktober 2016 um 21:10 Uhr

  • @huseyin tugrul buyukisik Es ist natürlich wahr, aber es sind die Instanzen der Folgestd::vector die zusammenhängend sind. Bsp.: einstd::vector<std::vector<int>> v die Elemente v[0], v[1]… werden nachträglich im Speicher abgelegt, aber das Element v[0].back() und v[1].front() sind nicht garantiert.

    – jarzec

    24. November 2017 um 10:36 Uhr


Sind stdvector Elemente garantiert zusammenhangend
Bill Lynch

Wie andere Antworten darauf hingewiesen haben, ist der Inhalt eines Vektors garantiert kontinuierlich (mit Ausnahme der Verrücktheit von bool).

Der Kommentar, den ich hinzufügen wollte, ist, dass, wenn Sie den Vektor einfügen oder löschen, was dazu führen könnte, dass der Vektor seinen Speicher neu zuweist, alle Ihre gespeicherten Zeiger und Iteratoren ungültig werden.

  • Die Elemente würden immer noch in einem zusammenhängenden Speicherblock gespeichert, sie wären nur an einer anderen Stelle. Die Frage bezog sich speziell auf die Kontiguität.

    – Dima

    11. Mai 2009 um 17:52 Uhr

  • Aber die vorhandenen Zeiger und Iteratoren würden ungültig gemacht.

    – Bill Lynch

    11. Mai 2009 um 18:49 Uhr

  • Guter Punkt. Sie sollten das in Ihre Antwort aufnehmen, um zu verdeutlichen, was Sie meinen.

    – Dima

    13. Mai 2009 um 22:33 Uhr

  • Jetzt weiß ich, warum mein Programm gestern einen Segfaulting hatte, als ich es in einer Doppelschleife durchlief und bestimmte Elemente entfernte 🙂 Danke!

    – Benutzer2891462

    30. Juli 2015 um 15:29 Uhr

  • @iaomw: 1. vector.push_back(3) ist eine Einfügung, sodass Iteratoren ungültig werden. 2. Ich würde nicht erwarten swap(vector[3], vector[4]) um Iteratoren ungültig zu machen, da kein neuer Speicher zugewiesen wird, aber ich habe keine Referenz, um dies zu sichern. 3. swap(vector_1, vector_2) ist interessant. Ich würde den Iteratoren danach wahrscheinlich nicht mehr vertrauen, aber ich weiß nicht genau, ob sie weiterhin gültig sind.

    – Bill Lynch

    12. November 2021 um 15:45 Uhr

Sind stdvector Elemente garantiert zusammenhangend
Motti

Tatsächlich garantiert die Norm, dass a vector ist kontinuierlich im Gedächtnis und das &a[0] kann an a weitergegeben werden C Funktion, die ein Array erwartet.

Die Ausnahme von dieser Regel ist vector<bool> die nur ein Bit pro verwendet bool Obwohl es einen kontinuierlichen Speicher hat, kann es nicht als verwendet werden bool* (Dies wird allgemein als falsche Optimierung und Fehler angesehen).

Übrigens, warum verwendest du keine Iteratoren? Dafür sind sie da.

  • > Übrigens, warum verwendest du keine Iteratoren? Dafür sind sie da. Vielleicht hat er das neue Papier von Alexanrescu zum Thema gelesen: boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/…

    – Nemanja Trifunovic

    11. Mai 2009 um 18:06 Uhr

  • Danke für den Link, ich werde es in meine Leseliste aufnehmen (ich versuche, Alexandresus Artikel nicht zu verpassen)

    – Motti

    11. Mai 2009 um 18:22 Uhr

  • Mwahaha, jeder scheint heutzutage über diese Präsentation zu sprechen. Schauen Sie, die Diskussion darüber ist immer noch heiß: groups.google.com/group/comp.lang.c++.moderated/browse_thread/…

    – Johannes Schaub – litb

    11. Mai 2009 um 18:25 Uhr

  • Wenn Sie es sorgfältig lesen, sagt Alexandrescus Artikel nicht wirklich “Verwenden Sie keine Iteratoren in C++”, sondern “Check out D”. Der Ansatz, den er in diesem Artikel beschreibt, ist auffallend ähnlich zu allen bestehenden Sprachen und Frameworks, die das funktionale Erbe übernommen haben (List, Scheme, Haskell), und ich bezweifle ernsthaft, ob eine weitere C-basierte Syntax ein idealer Ausgangspunkt für Besseres ist Listenbehandlung. Irgendwann letztes Jahr habe ich kurz versucht, ihn zu überreden, seine beträchtlichen Talente stattdessen der Verbesserung einer bereits etablierten Sprache wie C# zu widmen, aber ich fürchte, ohne Erfolg! 🙂

    – Daniel Earwicker

    18. Februar 2010 um 8:23 Uhr

Wie andere schon gesagt haben, vector verwendet intern ein zusammenhängendes Array von Objekten. Zeiger auf dieses Array sollten immer dann als ungültig behandelt werden, wenn eine nicht konstante Elementfunktion IIRC aufgerufen wird.

Es gibt jedoch eine Ausnahme!!

vector<bool> verfügt über eine spezielle Implementierung, die darauf ausgelegt ist, Platz zu sparen, sodass jede bool nur ein Bit verwendet. Das zugrunde liegende Array ist kein zusammenhängendes Array aus bool und Array-Arithmetik vector<bool> funktioniert nicht wie vector<T> möchten.

(Ich nehme an, es ist auch möglich, dass dies für jede Spezialisierung von Vektoren gilt, da wir immer eine neue implementieren können. std::vector<bool> ist die einzige, ähm, Standardspezialisierung, bei der einfache Zeigerarithmetik nicht funktioniert.)

Ich habe diesen Thread gefunden, weil ich einen Anwendungsfall habe, bei dem Vektoren mit zusammenhängendem Speicher von Vorteil sind.

Ich lerne, wie man Vertex-Buffer-Objekte in OpenGL verwendet. Ich habe eine Wrapper-Klasse erstellt, die die Pufferlogik enthält, also muss ich nur ein Array von Gleitkommazahlen und ein paar Konfigurationswerte übergeben, um den Puffer zu erstellen. Ich möchte in der Lage sein, einen Puffer aus einer Funktion basierend auf Benutzereingaben zu generieren, sodass die Länge zur Kompilierzeit nicht bekannt ist. So etwas zu tun wäre die einfachste Lösung:

void generate(std::vector<float> v)
{
  float f = generate_next_float();
  v.push_back(f);
}

Jetzt kann ich die Floats des Vektors als Array an die pufferbezogenen Funktionen von OpenGL übergeben. Dadurch entfällt auch die Notwendigkeit, dass sizeof die Länge des Arrays bestimmt.

Dies ist weitaus besser, als ein riesiges Array zum Speichern der Floats zuzuweisen und zu hoffen, dass ich es groß genug gemacht habe, oder mein eigenes dynamisches Array mit zusammenhängendem Speicher zu erstellen.

  • Diese Funktion macht für mich keinen Sinn. Wollen Sie eine Referenz oder einen Zeiger auf übergeben v eher, als v selbst? weil vorbei v allein bewirkt, dass innerhalb der Funktion eine Kopie erstellt wird, die nach dem Ende der Funktion nicht mehr existiert. Sie schieben also etwas auf den Vektor, nur um den Vektor zu löschen, wenn die Funktion endet.

    – Johannesbäcker

    5. April 2013 um 0:31 Uhr

1647136212 374 Sind stdvector Elemente garantiert zusammenhangend
Igor

cplusplus.com:

Vektorcontainer werden als dynamische Arrays implementiert; Genau wie bei regulären Arrays werden die Elemente von Vektorcontainern an zusammenhängenden Speicherorten gespeichert, was bedeutet, dass auf ihre Elemente nicht nur mit Iteratoren zugegriffen werden kann, sondern auch mit Offsets auf regulären Zeigern auf Elemente.

  • Diese Funktion macht für mich keinen Sinn. Wollen Sie eine Referenz oder einen Zeiger auf übergeben v eher, als v selbst? weil vorbei v allein bewirkt, dass innerhalb der Funktion eine Kopie erstellt wird, die nach dem Ende der Funktion nicht mehr existiert. Sie schieben also etwas auf den Vektor, nur um den Vektor zu löschen, wenn die Funktion endet.

    – Johannesbäcker

    5. April 2013 um 0:31 Uhr

Ja, die Elemente eines std::vector sind garantiert zusammenhängend.

995600cookie-checkSind std::vector Elemente garantiert zusammenhängend?

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

Privacy policy