Sind std :: vector Elemente garantiert zusammenhängend?

Question

Meine Frage ist einfach: Sind std :: vector Elemente garantiert zusammenhängend? Kann ich den Zeiger auf das erste Element eines std :: vectors als C-Array benutzen?

Wenn mir mein Gedächtnis gut tut, hat der C++ - Standard keine solche Garantie gegeben. Die std :: vector-Anforderungen waren jedoch so, dass es praktisch unmöglich war, sie zu erfüllen, wenn die Elemente nicht zusammenhängend waren.

Kann jemand das 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' 
    } 
} 

Answer 1

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

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

23.2.6 Klasse Schablonenvektor [Vector]

1 Ein Vektor ist eine Folge Behälter, der Direktzugriffs Iteratoren unterstützt. Darüber hinaus unterstützt es (amortisiert) konstante Zeit Einfügen und Löschen von Operationen am Ende; Einfügen und Löschen in der Mitte nehmen lineare Zeit. Storage Verwaltung wird automatisch behandelt, obwohl Hinweise gegeben werden können, um die Effizienz zu verbessern. Die Elemente eines Vektors werden zusammenhängend gespeichert, was bedeutet, dass, wenn v ein Vektor ist, wo T ein anderer Typ als ist, dann die Identität & v [0] + 0 für alle 0 < = n < v.größe().

Answer 2

Ja, die Elemente einer std :: vector garantiert zusammenhängend sein.

Answer 3

Der Standard garantiert tatsächlich, dass vector kontinuierlich im Speicher ist und dass &a[0] an eine C Funktion übergeben werden kann, die ein Array erwartet.

Die Ausnahme von dieser Regel ist vector<bool>, die nur so einen Bit pro bool verwendet, obwohl es sich kontinuierlich Speicher hat nicht als bool* verwendet werden (dies ist allgemein eine falsche Optimierung und einen Fehler betrachtet).

BTW, warum verwenden Sie keine Iteratoren? Dafür sind sie da.

Answer 4

cplusplus.com:

Vector Behälter werden als dynamische Arrays implementiert; Genauso wie reguläre Arrays haben Vektorcontainer ihre Elemente in zusammenhängenden Speicherorten gespeichert, was bedeutet, dass auf ihre Elemente nicht nur mit Iteratoren zugegriffen werden kann, sondern auch Offsets für reguläre Zeiger auf Elemente verwendet werden können.

Answer 5

Wie andere Antworten darauf hingewiesen haben, ist der Inhalt eines Vektors garantiert kontinuierlich (mit Ausnahme von Bools Verrücktheit). Der Kommentar, den ich hinzufügen wollte, ist, dass wenn Sie eine Einfügung oder eine Löschung auf dem Vektor vornehmen, was dazu führen könnte, dass der Vektor seinen Speicher neu zuweist, dann werden alle gespeicherten Zeiger und Iteratoren ungültig gemacht .

Answer 6

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

Es gibt jedoch eine Ausnahme !!

vector<bool> hat eine spezielle Implementierung, die entworfen wurde, um Platz zu sparen, so dass jede Bool nur ein Bit verwendet. Das zugrunde liegende Array ist kein zusammenhängendes Array von Bool und Arithmetik auf vector<bool> funktioniert nicht wie vector<T> würde.

(Ich nehme an, es ist auch möglich, dass dies für jede Spezialisierung von Vektor gilt, da wir immer eine neue implementieren können. std::vector<bool> ist jedoch die einzige, Fehler, Standard-Spezialisierung, auf die einfache Zeigerarithmetik nicht funktioniert .)

Answer 7

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

Ich lerne, wie Vertexpuffer Objekte in OpenGL verwenden. Ich habe eine Wrapper-Klasse erstellt, die die Pufferlogik enthält, also muss ich nur ein Array von Floats und ein paar Konfigurationswerte übergeben, um den Puffer zu erstellen. Ich möchte in der Lage sein, basierend auf einer Benutzereingabe einen Puffer aus einer Funktion zu generieren, so dass die Länge zur Kompilierzeit nicht bekannt ist. so etwas wie dies 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 den Vektor der Schwimmer als Array zu OpenGL-Puffer-bezogene Funktionen übergeben. Dies beseitigt auch die Notwendigkeit für sizeof, um die Länge des Arrays zu bestimmen.

Dies ist viel besser als das Zuweisen eines riesigen Arrays zum Speichern der Floats und hofft, dass ich es groß genug gemacht habe, oder mein eigenes dynamisches Array mit zusammenhängendem Speicher zu machen.