Sind std::vector Elemente garantiert zusammenhängend?

Question 1

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

Question 2

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().

Question 3

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.

Question 4

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.

Question 5

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

Question 6

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.

Question 7

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.

Question 8

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