Von welchem Typ ist der Vector?

Computer: Software & Programmierung C/C++
#1

Guten Tag,
ich rätsel gerade darüber von welchem Typ denn der STL Vector sein könnte.

Bis vor kurzem ging ich davon aus, dass dieser eine (einfach) verkettete Liste sei. Nachdem ich nun aber entdeckt habe, dass der Vector die Iteratoren rbegin und rend bietet um „reverse“ durch einen Vector durch zu itterieren, bin ich der Meinung, dass er eine doppelt verkettete Liste sein muss.
Eine doppelt verkettete Liste stellt aber meines Wissens schon der list Typ dar. Also macht diese Theorie auch wieder keinen Sinn…

Google war in der Hinsicht leider auch keine große Hilfe und die Frage lässt mich auch nicht mehr los. Also was ist er denn nun wirklich?

Mit freundlichen Grüßen

G-Fire

#2

Hallo,

ich rätsel gerade darüber von welchem Typ denn der STL Vector
sein könnte.

Vom Typ Vector :smile:

Bis vor kurzem ging ich davon aus, dass dieser eine (einfach)
verkettete Liste sei.

Damit wäre das Zugreifen auf einen Index extrem langsam.

Der Standard schreibt (soweit ich weiss) nicht vor, wie ein Vector implementiert sein soll, aber ich glaube, die meisten Implementierungen setzen es intern als Array um. Kann man einfach indizieren, vorwärts und rückwärts iterieren.

Zum vergrößern braucht man dann ein realloc() oder so, ist also nicht immer billig.

Grüße,
Moritz

#3

Hi Moritz,

Der Standard schreibt (soweit ich weiss) nicht vor, wie ein
Vector implementiert sein soll, aber ich glaube, die meisten

jein, es steht zu lesen:

"The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0