Programmieren in C/C++: Array
Der Datentyp Array ist einer der ältesten Datentypen. Die Aufgabe der ersten Computer war oftmals, stupide mathematische Berechnungen mit unterschiedlichen Eingabewerte zu berechnen (bspw. Berechnung von ballistischen Tabellen durch die ENIAC ENIAC). Sowohl die Eingabedaten als auch die Ausgabedaten wurden hintereinander im Speicher (in Arrays) gespeichert. Zur einfacheren Adressierung der Elemente in den Arrays wurden u.A. die Index-Register eingeführt. Mit der Entwicklung der ersten höheren Programmiersprachen wurde dieses Konzept im Datentyp Array abgebildet.
Grundlagen
[Bearbeiten]Arrays (Syntax: Datentyp [size_t DIM1][size_t DIM2]OPT…) entsprechen Variablen, wobei anstatt Speicherplatz nur für ein Element Speicherplatz für die Aufnahme 'aller' Elemente reserviert wird (Speicherplatzgröße ergibt sich aus der Multiplikationen aller Dimensionen DIMx multipliziert mit der Größe des Datentyps).
Bei eindimensionalen Arrays werden die Elemente hintereinander im Speicher angeordnet:
//Eindimensional //Anordnung im Speicher
short arr1[10]; //arr1[0] arr1[1]…arr1[9]
Mehrdimensionale Arrays entsprechen einem Array eines Arrays (und nicht einem Zeiger auf einen Zeiger, wie es fälschlicherweise oft gesagt wird):
int matrix[12][10];
//kann wie folgt dargestellt werden
typedef int vector[10]; //Alias für ein Int-Array bestehend aus 10 Elementen
vector matrix1[12]; //Eindimensionales Array des Datentyps vector
//und damit ein eindimensionales Arrays eines
//eindimensionalen Arrays -> Zweidimensionales Array
//matrix1[0..11] Dereferenzierter Datentyp -> vector resp. int(*)
//matrix1[0..11][0..9] Dereferenzierter Datentyp -> int
Bei mehrdimensionalen Arrays erfolgt die Anordnung der Elemente im Speicher beginnend vom rechten Index:
//Zweidimensional //Anordnung im Speicher
char arr2[4][3]; //arr2[0][0] arr2[0][1] arr2[0][2] arr2[1][0]
//arr2[1][1] arr2[1][2] arr2[2][0] …. arr2[3][2]
Der Arrayname zeigt auf die Startadresse des ersten Elementes des Arrays. Aus Datentypsicht ist der Arrayname ein Zeiger auf ein Array (Syntax: Datentyp (*) [DIM1]…). Die Dereferenzierung dieses Zeigers erfolgt über []-Klammern. Da die Elemente des Arrays strukturiert im Speicher angeordnet sind, bedeutet ein Zugriff auf ein Array-Element der Zugriff auf einen Speicherbereich, dessen Adresse sich aus der Startadresse ergänzt um den aus den Indexen ergebenden Offset ergibt.
Bei einem eindimensionalen Array sieht die Berechnung wie folgt aus:
short arr1[10];
arr1[index] = 2; // *( arr1 + index )=2;
arr1[index] = 2; // *(short *)((char *)arr1 + (index * sizeof(short)))=2;
Den Zugriff auf ein Element des zweidimensionalen Arrays setzt der Compiler in folgende Rechenvorschrift um:
int arr2[12][10]
arr2[idx1][idx2]=2; // * ( arr2 + idx1 * 10 + idx2 )=2;
// *(int *)((char *)arr2 + idx1 * 10*4 + idx2 * 4)=2;
Allgemein gilt folgende Rechenvorschrift für den Zugriff auf ein Array Element:
int arr3...[DIM3][DIM2][DIM1];
arr3...[i3][i2][i1]
//* ( arr4 + i1+(i2*DIM1)+(i3*DIM1*DIM2)+... )
//*(int*)((char *)arr4 + (i1+(i2*DIM1)+(i3*DIM1*DIM2)+...)*sizeof(int))Zur Berechnung des Offsets nutzt der Compiler die Dimensionsangaben und den Datentyp des Arrays aus der Definition der Variable. Die Dimension des Arrays wird nicht gespeichert. Diese ist somit nur zur Compilezeit dem Compiler bekannt.
Da mit dem Arraynamen nur ein Zeiger auf ein Array in die 'Hand' genommen wird, kann ein Array nie als 'Ganzes', also per Inhalt übergeben/zugewiesen werden. Eine Zuweisung (incl. Parameterübergabe) entspricht nur der Zuweisung/Kopieren des Zeigers auf ein Array (soll der Inhalt kopiert werden, so muss dies händisch getätigt werden (siehe Kopieren von Arrays)). Da die Dimension nicht gespeichert wird (und damit auch nicht kopiert wird), muss die Zielvariable ein Zeiger auf ein Array mit dem identischen Datentyp und der identischen Dimension wie das Quellarray sein. Fehlen die Dimensionsangabe (was alternativ möglich ist), so können die Array-Elemente aufgrund der nicht möglichen Offset-Berechnung nicht angesprochen/dereferenziert werden:
//Übergabeparameter arr als Beispiel für die Zuweisung
void func1(int arr[5][3]) //Array-Datentypbeschreibung im Funktionskopf
//beschreibt einen Zeiger auf ein Array, so
//dass hier nur die Startadresse übergeben wird
{ //Dimensionsgabe zwingend notwendig
arr[1][2]=12;
//Zuweisung ändert Inhalt der Aufrufervariable! (Call-by-Reference)
}
int main(void) {
int arr1[5][3]; //Definition eines Arrays
func1(arr1); //Zuweisung von arr1 an die Funktionsvariable arr
//in Form der Zuweisung des Zeiger auf ein Array
return 0;
}
Hinweise:
- Die linke Dimensionsangabe ist nur für die Berechnung der tatsächlichen Speichergröße durch den Compiler notwendig, jedoch nicht für die Offsetberechnung beim Zugriff auf einen Eintrag nötig. Bei der Definition von Zeiger auf Arrays kann die Angabe dieser Dimension entfallen:
void func2(int arr[][5]) { //Linke Dimensionsangabe nicht nötig arr[1][1]=3; } void func1(int arr[]) { //Linke Dimensionsangabe nicht nötig arr[4]=3; } int main(void) { int arr1[5]; func1(arr1); int arr2[3][5]; func2(arr2); }
- Die Dimension eines Arrays ergibt sich aus der Definition des Arrays resp. Zeiger auf Array. Nach Ausführung der Definition kann die Dimension nicht mehr geändert werden
Arrays von ...
[Bearbeiten]Arrays können von allen Datentypen erstellt werden:
- Array von Strukturen und Strukturelementen
struct xyz{ int x; int y; int array[10]; //Array eines Strukturelement } arr3[10]; //Array der Struktur arr3[3].x //Zugriff auf ein Strukturelement des Arrays arr3[4].array[5] //Zugriff auf ein Array-Strukturelement des Arrays
- Array von Zeigern
const char *arr4[]={"hello","world"}; //Eindimensionales Array aus Zeigern //Entspricht char const * const anonymous1="hello"; char const * const anonymous2="World"; const char * arr5[2] = {anonymous1,anonymous2}; printf("1. String: %s",arr5[0]); printf("5. Zeichen des 2.Strings: %c",arr5[1][4]);
- Der Datentyp eines Zeigers auf ein eindimensionales Array
(T (*))entspricht einem 'normalen' Zeiger(T *),(siehe Array Datentypen), so dass dann der Rückgabewert des Arrays auf Char-Zeiger über [] dereferenziert werden kann: arr5[1][4] == 'd' ------ +--> Zugriff auf das 2. Element, welcher einen Zeiger auf char * liefert. Dieser Zeiger zeigt auf die Startadresse von "World" [4] +--> Vom zurückgelieferten Zeiger wird das wird 4. Element dereferenziert 'd'- Anwendung:
- 1) Übergabeparameter argv
int main(int argc,char *argv[]) //argv ist ein Array von Zeigern, in welches die Laufzeitumgebung von C //bei Programmstart die Adressen der einzelnen Übergabewerte einträgt //bspw: >>./a.out para1 para2=47 // | | +--> argv[2] // | +--------> argv[1] // +----------------> argv[0]
- 2) Enum in einen String wandeln
typedef enum {OK,ERROR,WARNING} status_e; status_e ret=ERROR; const char *status2str[]= {"Status:OK","Status:Error","Status:Warning"}; printf("%d %s",ret,status2str[ret]);
Sichtweise auf Arrays auf Basis des Datentyps
[Bearbeiten]Der Datentype eines eindimensionalen Arrays ist wie folgt definiert:
Datentype: T[DIM1]
Der Variablenname des Arrays ist ein Zeiger auf ein 'eindimensionales' Array:
Datentyp: T(*)
Mehrdimensionale Arrays sind Arrays von Arrays:
Datentype: T[DIM1][DIM2][DIM3]…
Der Variablenname des Arrays ist ein Zeiger auf ein Array von Arrays:
Datentype: T(*)[DIM2][DIM3]... //Angabe der 'linken' Dimension nicht
//möglich/nötig. Das '*' kann als
//Ersatz für die fehlende linke Dimension
//verstanden werden.
//Hinweis:
//Klammerung des '*' zwingend notwendig, andernfalls würde der '*'
//zum Datentyp T zugeordnet sein, welches ein Zeiger von diesem Datentyp
//erzeugt.
Bei der Dereferenzierung von Zeigen wird entsprechend Zeiger:Sichtweise von Zeiger auf Basis des Datentyps ein * vom Datentyp weggenommen:
int var; //(int)
int *ptr1=&var; //(int *)
*ptr1 //*(int *) → (int)
Die []-Klammern beim Arrayzugriff entspricht der Dereferenzierung. Mit jeder []-Klammer erfolgt eine Dereferenzierung, welche anstatt der Wegnahme eines * die Wegnahme der linken []-Klammer vom Datentyp entspricht:
//Code → Datentyp
int array[5][4][3]; → (int[DIM1][DIM2][DIM3])
array[1] → (int[DIM1][DIM2][DIM3])[] → (int[DIM2][DIM3])
array[1][2] → (int[DIM1][DIM2][DIM3])[][] → (int[DIM3])
array[1][2][0] → (int[DIM1][DIM2][DIM3])[][][] → (int)
Hieraus ergibt sich, dass ein mehrdimensionales Array teildereferenziert werden kann. Alternativ ausgedrückt bedeutet dies, dass ein mehrdimensionales Array ein Array von Arrays (von Arrays…) ist welches mit jeder Dereferenzierung das übergeordnete 'Array von' abspaltet. Das teildereferenzierte Array ist wie der Arrayname ein Zeiger auf ein Array, welcher in einem Zeiger auf Array gespeichert werden kann:
int array[5][4][3];
int (*parr1)[4][3]=array;
int (*parr2)[3] =array[1];
int (*parr3) =array[1][2];
int value =array[1][2][0];
Auch auf einen Zeiger von Arrays kann über die []-Klammern auf die Elemente zugegriffen werden. Mit jeder []-Klammer erfolgt auch hier eine Wegnahme der linken []-Klammer vom Datentyp. Beim allerletzten Zugriff wird anstatt der [] das Sternchen weggenommen:
//Code → Datentyp
int *parr[4][3]; → (int (*)[DIM2][DIM3])
parr[1] → (int (*)[DIM2][DIM3])[] → (int (*)[DIM3])
parr[1][2] → (int (*)[DIM2][DIM3])[][] → (int (*))
parr[1][2][3] → (int (*)[DIM2][DIM3])[][][] → (int)
Ein Zeiger auf ein eindimensionales Array entspricht einem normalen Zeiger. Beide können demnach wie folgt dereferenziert werden:
int arr[4];
int (*parr)=arr; //Zeiger auf ein Array vom Datentyp int
int *ptr =arr; //Zeiger auf int
//Variante 1: Dereferenzierung über []
parr[2]=1;
ptr[2] =1;
//Variante 2: Dereferenzierun über *
*(ptr+1)=1;
*(parr+1)=1;
Zusammenfassung
[Bearbeiten]Mit der Definition eines Arrays wird Speicher entsprechend der Dimension des Arrays reserviert:
//Code → Datentyp
int array[5][4][3][2]; → (int [5][4][3][2])
Vollständige Dereferenzierung/Indizierung gibt den zugrundeliegenden Datentyp zurück:
//Code → Datentyp
array[3][2][1][0] → (int)
Eine Teildereferenzierung/Indizierung gibt ein 'SubArray' zurück, also ein Zeiger auf Arrays von Array von …, wobei vom ursprünglichen Array der Index beginnend von links entfällt:
//Code → Datentyp Dimensionen
array[1] → (int[4][3][2]) entspricht array[1][0..3][0..2][0..1]
array[2][1] → (int [3][2]) entspricht array[2][ 1 ][0..2][0..1]
array[2][1][0] → (int [2]) entspricht array[2][ 1 ][ 0 ][0..1]
array[2][1][0][0] → (int ) entspricht array[2][ 1 ][ 0 ][ 0 ]
Mittels dem Datentype Zeiger auf ein Array (Datentype: T(*)[]..) kann ein 'Zeiger' auf ein Array gespeichert werden. Der Compiler benötigt für die Adressberechnung nicht die linke Dimensionsangabe, so dass das Sternchen quasi der linken fehlenden []-Klammer entspricht:
int arr1[4];
int arr2[4][5];
int arr3[4][5][6];
int arr4[4][5][6][7];
int (*parr1) = arr1;
int (*parr2)[5] = arr2;
int (*parr3)[5][6] = arr3;
int (*parr4)[5][6][7] = arr4;
//Alternativ kann in einem Zeiger auf ein Array auch ein
//Teildereferenziertes Array gespeichert werden:
int array[5][4][3][2];
int (*sub0) = array[2][1][0];
int (*sub1)[2] = array[2][1];
int (*sub2)[3][2] = array[1];
int (*sub3)[4][3][2] = array;
Der Zugriff auf die Arrayelemente über einen Zeiger auf ein Array erfolgt wie bei einem Array:
//Code → Datentyp
sub0[0..1]=1; → array[ 2 ][ 1 ][ 0 ][0..1]=1;
sub1[0..2][0..1]=1; → array[ 2 ][ 1 ][0..2][0..1]=1;
sub2[0..3][0..2][0..1]=1; → array[ 2 ][0..3][0..2][0..1]=1;
sub3[0..4][0..3][0..2][0..1]=1; → array[0..4][0..3][0..2][0..1]=1;
Explizites Cast
[Bearbeiten]Über explizite Typkonvertierung (Cast Operator) kann ein Array in ein anderes Array 'konvertiert' werden. Dabei kann sowohl der zugrundeliegende Datentyp als auch die Dimension neu gesetzt werden:
int arr[5][4][3];
char (*ptr1)[4][3]=arr; //KO, Datentyp von arr und ptr1 unterschiedlich
char (*ptr2)[4][3]=(char (*)[4][3])arr; //Cast auf einen anderen Datentyp
int (*ptr3)[3][4]=(int (*)[3][4])arr; //Cast auf eine andere Dimension
float (*ptr4)[3] =(float(*)[3])arr; //Ohne Worte
Der Cast bewirkt keine Umsortierung der Daten im Speicher, sondern einzig einer Umwidmung. Der Cast wirkt sich einzig auf die Offsetberechnung bei der Dereferenzierung aus:
int arr[5][4][3][2];
arr[1][3][2][1]=1; //*(arr+1*(4*3*2)+3*(3*2)+2*(2)+1)=1;
//*(arr+ 24 + 18 + 4 +1)=*(arr+47)=1;
int (*parr)[3][4][2]=(int (*)[3][4][2])arr;
parr[1][2][3][1]=1; //*(parr+1*(3*4*2)+2*(4*2)+3*(2)+1)=1;
//*(parr+ 24 + 16 + 6 +1)=*(parr+47)=1;
Variable Length Array (VLA)
[Bearbeiten]Im Normalfall ergibt sich die Dimensionsangabe eines Arrays aus einer Konstanten, so dass der Compiler zur Compilezeit passend Speicher reserviert. Bei Variable Lenght Array wird die Arraydimension nicht über eine Konstante, sondern über eine Variable oder einen Ausdruck angegeben, so dass sich die tatsächliche Dimension des Arrays erst zum Ausführungszeitpunkt der Definition ergibt. Da Variablen / Ausdrücke erst zur Laufzeit ausgewertet werden, können VLAs nur als lokale Variable oder als Übergabeparameter definiert werden:
void foo(int dim1, int dim2) {
int arr[dim1][dim2+2*dim1];
void far(int dim1, int dim2, int arr[dim1][dim1+dim2]) {
Auch bei Zeigern auf Arrays kann die Dimension über eine Variable / einen Ausdruck angegeben werden:
void foo(int dim1, int dim2) {
int (*parr)[dim1][dim2];
Wird die Dimension über eine Const-Variable (siehe DatentypeSpecifier:Const Type Qualifier ) vorgegeben, so handelt es sich ebenfalls um eine Variable Length Array. Auch ein Const-Variable ist eine Variable! Statt der Nutzung einer Const-Variablen empfiehlt sich hier die Nutzung eines Makros:
const int dim1=5;
int arr1[dim1]; //VLA
#define DIM2 5
int arr2[DIM2];
Bei Zuweisung von einem Array an ein VLA Zeiger, einem Zeiger auf Array auf einen VLA Zeiger oder einem VLA Zeiger auf einen Zeiger auf Array prüft der Compiler nicht die Dimensionsangabe. Einzig überprüft er, ob die Anzahl der Dimensionen identisch ist:
const int dim1=4;
const int dim2=5;
void func(void) {
int arr1[4][5];
int arr2[dim1][dim2];
int (*parr1)[5];
int (*parr2)[dim2];
parr1=arr1; //OK Zuweisung von Array auf Zeiger auf Array
parr1=arr2; //OK Zuweisung von VLA auf Array auf Array
parr2=arr1; //OK Zuweisung von Array auf VLA Zeiger
parr2=arr2; //OK Zuweisung von VLA auf VLA Zeiger
parr1=parr2; //OK Zuweisung von VLA Zeiger auf Zeiger
parr2=parr1; //OK Zuweisung von Zeiger auf VLA Zeiger
int (*parr3)[7];
int (*parr4)[4][5];
parr3=arr1; //KO Dimensionsangabe nicht identisch
parr3=arr2; //OK Dimensionsangabe wird bei VLA nicht geprüft
parr4=arr1; //KO Anzahl der Dimensionen nicht identisch
parr4=arr2; //KO Anzahl der Dimensionen nicht identisch
Bedenke
[Bearbeiten]Bei Zeiger auf Arrays muss das * geklammert sein. Andernfalls wirkt sich das * auf den zugrundeliegenden Datentyp aus und erzeugt aus diesem einen Zeiger:
int array1[3][2]; //Hiermit wird Speicher für ein zweidimensioanles Array
//vom Datentyp int reserviert
int *array2[3][2]; //Hiermit wird Speicher für ein zweidimensionales Array
//vom Datentyp int * reserviert
int (*ptr3)[3][2]; //Hiermit wird Speicher für eine Zeigervariable
//reserviert, welches auf ein Dreidimensionales Array
//vom Typ int zeigt
int *(*ptr4)[3][2]; //ohne Worte
Sichtweise auf Array auf Basis eines Speicherabzuges
[Bearbeiten]Über die Darstellung, wie ein Array im Speicher organisiert ist, lässt sich die Arbeitsweise von Arrays, Zeiger auf Arrays und der Dereferenzierung alternativ beschreiben.
Zeiger auf Arrays und Dereferenzierung
[Bearbeiten]Wie mehrfach beschrieben werden die einzelnen Array-Elemente vom rechten Index hochgezählt im Speicher abgelegt:
*1) Der Arrayname ist ein Zeiger auf ein Array. Er zeigt auf die erste Speicheradresse (= Adresse des ersten Elementes) des vom Array belegten Speicherplatzes
*2) Der Arrayname kann in einem Zeiger auf ein Array gespeichert werden. Der Zeiger zeigt dann ebenfalls auf die erste Speicheradresse des vom Arrays belegten Speicherplatzes
*3) Wird das Array 'arr' volldereferenziert, wird ein Element des zugrundeliegenden Datentyps des Arrays angesprochen. Die Adresse des Elementes ergibt sich aus der Startadresse des Arrays plus einen Offset (hier 0*(4*3*2)+3*(3*2)+2*(2)+1)
*4) Wird ein Array nur Teildereferenziert, so ist der Rückgabewert ein Zeiger auf ein Array. Die Adresse des Zeigers in das Array ergibt sich aus der Startadresse und den Offset (hier 0*(4*3*2)+2*(3*2)+1*(2)+(entfällt) =14). Die Anzahl der Elemente, auf welches dieses teildereferenzierte Array zeigt, ergibt sich aus der verbleibenden Dimension (hier [2])
*5) Wird ein Zeiger vollständig dereferenziert (hier auf Basis des zuvor teilderefenzierten Zeigers auf ein Array), so wird auch hier ein Element des zugrundeliegenden Datentyps angesprochen. Die Adresse ergibt sich aus der Startadresse des Zeigers plus einen Offset, ermittelt auf Basis der Dimension des Zeiger auf Arrays (hier 1)
*6) Die Startadresse des teildereferenzierten Arrays ergibt sich aus (0*(4*3*2)+1*(3*2)+(entfällt)=6). Die Dimension des teildereferenzierten Arrays ist [3][2]
*7) Der Offset beim Zugriff ergibt sich zu (2*(2)+0)=2
Offsetberechnung
[Bearbeiten]Bei einem Zugriff auf ein Arrayelement rechnet der Compiler die Indexe in einen Offset um. Hierzu nutzt er die Dimensionsangabe und den Datentyp des Arrays / Zeiger auf Array aus der Definition der Variable. Eine Überprüfung, ob der Index im gültigen Wertebereich ist, findet nicht statt:
Explizites Cast
[Bearbeiten]Bei der 'Umwidmung' eines Arrays in einen anderen Arraytyp erfolgt keine Umsortierung der Daten:
Arrays vs. Zeiger auf Zeiger
[Bearbeiten]Mehrdimensionale Arrays sind Arrays von Array. Sie beinhalten Speicher zur Aufnahme aller Elemente des zugrundeliegenden Datentyps. Zeiger auf Arrays von Arrays enthalten einzig die Startadresse auf solche Arrays. Über die bei der Definition angegebenen Dimension bei Array und Zeiger auf Arrays erfolgt die Offset-Berechnung zum Zugriff auf die einzelnen Elemente.
Bei Zeiger auf Zeiger wird Speicherplatz zur Aufnahme eines Zeigers für jeden Subzeiger reserviert. Typischerweise sind diese Zeiger verkettet, so dass ein Zeiger auf die Startadresse der nächsten Zeigervariablen zeigt.
Auch wenn die Zugriffsart bei einem zweidimensionale Array und einen Array von Zeigern identisch ist, so bewirken die beiden Datenstrukturen unterschiedlichen Zugriffsmechanismen. Bei einem zweidimensionalen Array ergibt sich der Zugriff über eine einfache Offsetberechnung.
Bei einem Zeiger auf Zeiger (hier zaz) muss zunächst der Inhalt der Variablen zaz gelesen werden. Dieser zeigt auf die Startadresse des eindimensionalen Arrays. Über den Offset (hier 2*sizeof(int *)) kann nun die Startadresse eines weiteren eindimensionalen Arrays gelesen werden. Das Zielelement ergibt sich aus dieser Startadresse addiert um einen weiten Offset.
Speicherplatzreservierung
[Bearbeiten]Der Speicherbedarf eines Arrays ergibt sich aus der Multiplikation der Dimensionen und des zugrundeliegenden Datentypes.
Bei globalen und static lokalen Arrays erfolgt die Speicherplatzreservierung für Arrays durch den Compiler, d.h. die Dimensionsangabe der Arrays muss über Konstanten/Konstanteausdrücke erfolgen.
Bei lokalen Arrays erfolgt die Speicherplatzreservierung zur Laufzeit, wenn die Definition des Arrays zur 'Ausführung' kommt. Die Dimension des Arrays kann dementsprechend über Konstanten/Kontantenausdrücke und bei C (nicht C++) über Variablen und Ausdrücke (Variable Length Arrays VLA) (siehe Kap. 5.15 Variable Length Array (VLA)) angegeben werden:
int var1=7;
short arr[var1]; //Speicherplatzreservierung entsprechend dem aktuellen
//Wert von var1
var1=8; //Nachträgliches ändern von var1 ändert nicht die
//Dimension des Arrays!
arr[7]=4711; //KO Bufferoverflow, da mit Hochsetzen von var1
//nicht das Array vergrößert wird
Die Dimension von in Strukturen/Unions eingebetteten Arrays muss ebenfalls über Konstanten/Literale definiert werden. GNU-C erlaubt ergänzend, dass die Dimension von Arrays innerhalb von in Funktionen definierten Strukturen ebenfalls variabel sein darf:
struct xyz{
int x;
int y[10]; //OK
int z[x]; //KO, Dimension muss sich aus einer Konstanten ergeben
};
void foo(int n) {
int arr[n]; //OK, VLA als lokale Variable möglich
struct xyz{ //Datentypdefinition innerhalb einer Funktion
int x;
int y[10]; //OK
int z[n]; //KO, Dimension muss sich aus einer Konstanten ergeben
//Ausnahme: GNU-C
} var1; //GNU-C Dimension des Arrays z ergibt such aus den Wert n
// zu diesem Ausführungszeitpunkt
}
Alternativ kann Speicherplatz für Arrays auf dem Heap reserviert werden:
short (*ptr1)[3][2]=(short(*)[3][2])malloc(sizeof(short)*2*3*4711);
if(ptr1!=NULL) {
ptr1[1][2][1]=11;
}
short (*ptr2)[3][2]=(short(*)[3][2])malloc(sizeof(short [4][3][2]));
if(ptr2!=NULL) {
ptr1[4711][2][1]=11; //KO, Bufferoverflow
}
Damit das Array mit 0 gefüllt ist, empfiehlt sich die Nutzung von calloc:
short (*ptr2)[3][2]=(short(*)[3][2])calloc(sizeof(sort),2*3*4);
Sizeof
[Bearbeiten]Der sizeof-Operator liefert bei Arrays den tatsächlichen Speicherbedarf des Arrays in Bytes zurück:
- Bei Arrays mit konstanter Dimensionsangabe wird sizeof durch den Compiler ersetzt, sizeof entspricht folglich einem Konstantenausdruck
- Bei VLA kann der sizeof-Operator nicht durch den Compiler ersetzt werden. Hier wird der sizeof-Operator zur Laufzeit ausgewertet (d.h. die Größe des Arrays wird bei VLA's ergänzend gespeichert)
Durch Ausnutzung der Tatsache, dass der sizeof-Operator auch auf teildereferenzierte Arrays angewendet werden kann, kann über diesen Weg die Dimension des Arrays ermittelt werden:
int arr1[7];
size_t dim1_arr1=sizeof(arr1) /sizeof(arr1[0]);
// sizeof(int [7])/sizeof(int );
// 28 / 4 → 7
short arr2[3][4];
size_t dim1_arr2=sizeof(arr2) /sizeof(arr2[0]);
// sizeof(int [3][4])/sizeof(int [4]);
// 48 / 16 → 3
size_t dim2_arr2=sizeof(arr2[0])/sizeof(arr2[0][0]);
// sizeof(int [4])/sizeof(int );
// 16 / 4 → 4
double arr3[3][4][5];
size_t dim1_arr3=sizeof(arr3)/sizeof(arr3[0]);
size_t dim2_arr3=sizeof(arr3[0])/sizeof(arr3[0][0]);
size_t dim3_arr3=sizeof(arr3[0][0])/sizeof(arr3[0][0][0]);
Für einen kürzeren und besser lesbaren Code empfiehlt sich, die Dimension über Makros zu setzen:
#define ARR1_DIM1 10
#define ARR1_DIM2 12
float arr1[ARR1_DIM1][ARR1_DIM2];
Bei Anwendung des sizeof-Operators auf Zeiger auf Arrays wird nicht der Speicherbedarf des Arrays, sondern wie bei Zeigern üblich der Speicherbedarf des Zeigers zurückgegeben:
short arr[4][6];
short (*ptr)[6]=arr;
printf("%zu\n",sizeof(arr)); //48=4*6*sizeof(short)
printf("%zu\n",sizeof(ptr)); //4/8
//Vorsicht, wird der Zeiger auf ein Array teildereferenziert, so
//wird auch hier die Größe des teildereferenzierten Arrays zurückgegeben
printf("%zu\n",sizeof(ptr[0])); //12 = 6*sizeof(short)
printf("%zu\n",sizeof(ptr[0][0])); //2 = sizeof(short)
Initialisierung
[Bearbeiten]Ein Array wird über ein Initialisierungsliste (siehe Grundlagen:Initialisierungsliste / Compound Literal) initialisiert, d.h. die Initialisierungswerte stehen in geschweiften Klammern. Für jede Dimension bei einem mehrdimensionalen Array ist eine innere Initialisierungsliste zu nutzen:
int arr1[3]={ //Initialisierungsliste
1,2,3 //Initialisierungswerte
};
int arr2[3][5][3]= { //Initialisierungsliste
{ //Initialisierungsliste für linke Array-Dimension
{ //Initialisierungsliste für mittlere Array-Dimension
1,2,3 //Initialisierungswerte
},
{ //Initialisierungsliste für mittlere Array-Dimension
... //Initialisierungswerte
},
...
},
{ //Initialisierungsliste für linke Array-Dimension
},
...
}; //Ende der Initialisierungsliste
struct xyz {int x,y[3],z;};
struct xyz arr[2][2]= { //Initialisierungsliste
{ //Initialisierungsliste für linke Array-Dimension
{ //Initialisierungsliste für Struktur
1, //Strukturelement x
{ //Strukturelement y Initialisierungsliste
2,3,4
},
5 //Strukturelement z
},
{ //Initialisierungsliste für Struktur
}
},
{ //Initialisierungsliste für linke Array-Dimension
}
};
Ergibt sich aus den Initialisierungswerten eine Dimensionsangabe, so kann die Angabe der Dimension bei der Definition des Arrays entfallen:
long long vector1[4]={1LL,2LL,3LL,4LL};
long long vector2[] ={7LL,8LL,9LL,10LL};
short arr1[4]={1,2,3}; //Nicht initialisierte Elemente werden mit 0 gefüllt
short arr2[2]={1,2,3}; //KO Mehr Initialisierungswerte als Dimension
short arr3[4] = {0}; //Alle Elemente mit 0 füllen
Werden bei expliziter Dimensionsangabe:
- weniger Initialisierungswerte angegeben, so werden die verbleibenden Arrayelemente mit 0 gefüllt
- mehr Initialisierungswerte angegeben, so meldet der Compiler einen Fehler
Erstere Variante bietet die Möglichkeit unter Angabe von { 0 } das gesamte Array auf 0 zu setzen. In C++, bei GNU-C und ab C23 kann die Angabe der 0 in der geschweiften Klammer entfallen:
char arr1[5] = {0}; //Gesamtes Array wird mit 0 initialisiert
char arr2[5] = { }; //Alternative Möglichkeit
struct xyz1{int x,y,z;} arr3[10]={0}; //Dito
struct xyz2{int x,y,z;} arr4[10]={ }; //Dito
Character Arrays können alternativ mit einem String " " initialisiert werden:
char string0[5]={'4','7','1','1','\0'};
char string1[5]="4711";
wchar_t arr2g[]=L"hallo"; //Im Falle eines WideChar Strings
int string2[]="hallo"; //KO, String bedingt char als Datentyp
Ist bei expliziter Dimensionsangabe des Arrays kein Speicherplatz für das Stringendezeichen vorgesehen, so wird dieses auch nicht gespeichert:
char string2[4]="4711"; //Kein Stringendezeichen in string2 enthalten
Eine Initialisierung ist nur bei Arrays möglich, deren Dimension über eine Konstante gesetzt wurde. VLA's können nicht initialisiert werden. Außerhalb der C-Spec bieten einige Compiler die Möglichkeit an, VLA's über eine leere Initialisieurngsliste auf 0 zu setzen:
void foo(int n) {
int arr2[n]={0}; //KO, VLA können nicht initialisiert werden!
int arr1[n]={}; //KO, kein C konformer Syntax
//OK bei einigen Compilern
Ähnlich wie bei der Initialisierung von Strukturen über designated initializers können seit C99 (bedingt bei C++) einzelne Array-Elemente über ihren Index initialisiert werden:
char arr1[20] = {
[0]='a',
[8]=33,34, //Index 8 und 9 werden Initialisiert
[3]=35,36, //Index 3 und 4 werden Initialisiert
//Rückwärtsspringen bei C++ nicht möglich
[10 ... 12]=3 //KO, laut C-Spec
}; //OK bei einigen Compilern
char arr2[4][3]= {
[1][1]=7,
[2] ={1,2,3},
[3] ={ [1]=4 },
};
Folgendes gilt es hier zu berücksichtigen:
- Bei C (nicht C++) sind doppelte Indexe erlaubt, die letzte Beschreibung in der Initialisierungsliste überschreibt vorherige Initialisierungen
- Bei C++ müssen die Indexe aufsteigend sortiert sein
Weitere Beispiele:
char arr1a[4]={1,2,3,4}; //OK
char arr1b[4]={1,2,3,4,5}; //KO Compilerfehler
char arr1c[4]={1,2,3}; //OK, Fehlende Elemente werden auf 0 gesetzt
char arr1d[] ={1,2,3,4}; //OK, Dimension ergibt sich aus der Anzahl der
// Initialisierungselemente
char arr1e[100]={0}; //OK, Fehlende Elemente werden auf 0 gesetzt
char arr2a[6]="hello"; //OK
char arr2b[5]="hello"; //OK, jedoch kein Stringendezeichen vorhanden
char arr2c[4]="hello"; //KO Mehr Initialisierungswerte als Dimension
char arr2d[8]="hello"; //???
char arr2e[] ="hello" "world" "ich\
fortsetztung" __DATE__; //???
int arr2f[6]="hello"; //???
char arr4a[4][3] = { {1,2,3},{4,5,6},{7,8,9},{10,11,12} }; //OK
char arr4b[4][3] = { 1,2,3,4,5,6,7,8,9,10,11,12 }; //Außerhalb
//der Spec von einigen Compilern unterstützt
char arr4c[3][10] = { "hallo","du","da" }; //???
Typedef
[Bearbeiten]Mittels Typedef können auch Aliase auf Arrays und Zeiger auf Arrays angelegt werden. Der 'Variablenname' ist dabei der Alias:
//Typedefs für Arrays
typedef char arr1_t[7];
arr1_t arr1; //Array der Dimension 7
typedef char arr2_t[]; //OK (Incomplete Array Definition)
arr2_t arr2; //KO, aufgrund der fehlenden Dimension
arr2_t arr3={1,2}; //OK, Dimension ergibt sich aus der
// Dimension der Initialisierung
typedef char arr4_t[5][4][3];
arr4_t arr4; //OK dreidimensionales Aray
arr4_t arr5[6]; //OK vierdimensionales Array
//Typedefs für Zeiger auf Arrays
typedef char (*parr3_t)[4][3]; //Definition des Alias arr3_t
parr3_t ptr4;
Über Typedef können auch VLA's definiert werden, diese müssen dann im Funktionskontext definiert werden. Die Dimension des Arrays ergibt sich zum Ausführungszeitpunkt der Typedef-Anweisung und nicht zum Ausführungszeitpunkt der Definition der Variablen!
void func(int m) {
typedef int arr_t[m]; //Dimensionsgröße ergibt sich aus m zu diesen
//Zeitpunkt der Ausführung der typedef Anweisung
m++; //Änderung von m ändert nichts an der Dimension
arr_t arr; //der hier definierten Variable
}
Array-Literale
[Bearbeiten]Über Compound Literal kann auch eine anonymous array definiert werden (nur C nicht C++):
//Compound Literal gibt entsprechend der Nutzung eines
//Arraynamens die Startadresse des anonymous Array zurück
int (*arr)[3];
arr=(int [2][3]){{1,2,3},{1,2,3}};
//Übergabe eines Compound Literals an eine Funktion
void foo(int (*arr)[3]) {
}
foo( (int [2][3]){{1,2,3},{4,5,6}} );
//Übergabe eines Compound Literals zur Array Initialisierung
arr=malloc(sizeof(int)*3*2);
memcpy(arr, //Destination-Address
(int [2][3]){{1,2,3},{4,5,6}}, //Source-Address
2*3*sizeof(int) //Anzahl zu kopierender Bytes
);
Entsprechend Arrays, bei welchen der Arrayname einem Zeiger auf einem Array entspricht, ist ein Compound Literal ebenfalls ein Zeiger auf ein Array.
Compound Literale sind ungeachtet des Names keine Konstanten, so dass deren Inhalt geändert werden kann. Zur Darstellung von Konstanten muss das Compound Literal explizit als const definiert werden:
int (*arr2)[3];
arr2=( int [2][3]){{1,2,3},{1,2,3}};
arr2[1][1]=7; //Änderung möglich
//Explizite Definition als const
const int (*arr3)[3];
arr3=(const int [2][3]){{1,2,3},{1,2,3}};
arr3[1][1]=7; //KO, compilerfehler
Array mit 0 füllen
[Bearbeiten]Mittels der memset() Funktion besteht die Möglichkeit, einen Speicherbereich mit einem Byte-Wert zu füllen. Bei Angabe der Startadresse und der Größe des Arrays bietet sich hierüber die Möglichkeit, ein Array mit 0 zu füllen:
char arr0[5][4];
memset(arr0,0,sizeof(arr0)); //Speicherbereich/Array mit 0 Füllen
//Alternative Füllwerte füllen das Array nicht mit dem
//erwarteten Wert!
float arr1[8][9];
memset(arr1,1,sizeof(float)*8*9);
printf("%g",(double)arr1[1][1]); //Inhalt ist ungleich 1.0
Vergleichen von Arrays
[Bearbeiten]Der Arrayname ist ein Zeiger auf ein Array, so dass hierüber kein Inhaltsvergleich, sondern einzig ein Adressvergleich stattfindet:
char arr1[4],arr2[4];
if(arr1 == arr2) //Für Compiler OK, jedoch erfolgt hier
printf("Startadresse identisch"); //ein Vergleich der Startadressen
Ein Inhaltsvergleich muss entweder händisch oder kann alternativ über die memcmp() Funktion durchgeführt werden:
char arr1[4]={1,2,3,4};
char arr2[4]={1,2,3,4};
//Händischer Vergleich
int lauf;
for(lauf=0;lauf<4;lauf++)
if(arr1[lauf]!=arr2[lauf])
break;
if(lauf == 4)
printf("Arrays sind identisch");
//Vergleich mittels memcmp()
if(memcmp(arr1,arr2,sizeof(arr1)) == 0)
printf("Arrays sind identisch");
Vorsicht: Wenn aufgrund von alignment der Compiler die zugrundeliegende Datenstruktur vergrößert (bspw. struct xy {int x; char y;}; von 5-Bytes auf 8-Bytes) kann memcmp nicht genutzt werden!
Kopieren von Arrays
[Bearbeiten]Der Arrayname ist ein Zeiger auf ein Array, so dass ein Kopieren entweder händisch oder mittels der memcpy() Funktion erfolgen muss:
char arr1[4];
char (*arr2);
arr2=arr1; //Syntax OK, jedoch nur Kopie der Startadresse
//und nicht des Inhaltes!
arr2=malloc(sizeof(arr1));
//Händisches Kopieren
for(int lauf=0;lauf<4;lauf++)
arr2[lauf]=arr1[lauf];
//Kopieren mittels memcpy(), Größenangabe ermittelt aus 'Quellarray'
memcpy(arr2,arr1,sizeof(arr1));
memcpy(arr2,arr1,sizeof(arr2)); //Hier werden nur 4/8 Bytes kopiert
Array bei Funktionsaufrufen
[Bearbeiten]Parameterübergabe
[Bearbeiten]Der Arrayname ist ein Zeiger auf ein Array. Dies bedeutet, man kann das Array nicht als Ganzes (d.h. mit seinem gesamten Inhalt) ansprechen. Folglich kann ein Array nicht als Call by Value übergeben werden, sondern immer nur als Call by Reference.
Für die Datentypdefinition im Funktionskopf stehen 3 Varianten zur Verfügung:
- Zeiger auf ein Array
- Datentypdefinition entsprechend eines Arrays unter Angabe aller Dimension
- Datentypdefinition entsprechend eines Arrays mit fehlender Angabe der linken Dimension
Letztere beiden lassen vermuten, dass hier eine Call By Value Übergabe stattfinden. Dies ist ein Trugschluss. Alle 3 Datentypdefinition erzeugen, angewendet im Funktionskopf, einen Zeiger auf ein Array:
char arr1[3];
char arr2[5][3];
char arr3[5][4][3];
//Datenübergabe bei eindimensionalem Array
//und 3 unterschieden Datentypedefinitionen
//(alle 3 erzeugen ein Zeiger auf ein Array)
void func11(char *ar);
void func13(char ar[3]);
void func12(char ar[]);
//Datenübergabe bei mehrdimensionalen Arrays
//und 3 unterschiedlichen Datentypedefinitionen
void func23(char (*ar)[3]);
void func21(char ar[5][3]);
void func22(char ar[][3]);
void func33(char (*ar)[4][3]);
void func31(char ar[5][4][3]);
void func32(char ar[][4][3]);
Ergänzend zu der Dimensionsangabe des Arrays über Konstante kann die Dimension auch entsprechend VLA's über Variablen (und Ausdrücke) definiert werden (nicht C++). In diesem Fall muss die Dimensionsvariable zuvor definiert worden sein. Entweder als globale Variable oder im Funktionskopf ergänzend als eigenständiger Parameter übergeben werden. Die tatsächliche Dimension des Arrays wird zum Aufrufzeitpunkt der Funktion ausgewertet:
//Definition der Definitionsvariable als globale Variable
int dim1,dim2;
void funcxy(char arr[dim1][dim2]);
//Übergabe der 'Dimensionvariablen' vor der Arrayübergabe
void funcxy(int dim1, int dim2, char arr[dim1][dim2]);
//Unter Angabe der fehlenden linken Dimension
void funcxy(int dim2, char arr[][dim2]);
//Über Forward Parameter Definitionen im Funktionskopf
//(nur GNU-C) können die 'Dimensionvariablen'
//auch nach dem Array übergeben werden:
//https://gcc.gnu.org/onlinedocs/gcc/Variable-Length.html#Variable-Length
void funcxy(int dim1, int dim2; char arr[dim1][dim2], int dim1, int dim2);
// -------------- ------------------
// Prototypen Übergabeparameter
//Hinweis:
//Semikolon trennt im Funktionskopf beim GCC Compiler zwischen
//Prototypenbereich und dem Variablenbereich!
Egal, über welche Art das Array im Funktionskopf definiert wurde, der Datentyp ist ein Zeiger auf ein Array. Folglich gibt der sizeof-Operator angewendet auf den Arraynamen die Größe des Zeigers zurück:
void foo(int n, int arr[n][n]) {
printf("sizeof=%zu",sizeof(arr)); //4/8
Hinweis:
- Bei Arrayübergabe über VLA's kann alternativ zur Dimensionsangabe über eine Variable auch ein beliebiger Ausdruck stehen, der zum Aufrufzeitpunkt der Funktion ausgewertet wird:
//Quelle leider nicht notiert int main(int argc, char *argv[printf("Hello")]) { printf(" world!\n"); return 0; } void f(char _[( printf("Press enter to confirm: "), getchar(), 1 )]) { printf("thanks.\n"); } void imax(int *out, int a, int b, char _[( *out = a > b ? a : b, 1 )]) {}
Werterückgabe
[Bearbeiten]Ergänzend zur Übergabe eines Zeigers auf ein Array an eine Funktion kann auch ein Zeiger auf ein Array zurückgegeben werden. Anstatt der Klammerung des Variablennamens muss hier die Funktionsname inkl. Funktionskopf geklammert werden!
Entsprechend der Rückgabe von 'normalen' Zeiger (siehe Zeiger:Werterückgabe) muss auch hier Achtsamkeit auf den Gültigkeitsbereich gelegt werden, auf den der Zeiger zeigt:
int (*foo(void))[3] {
int arr[3][3];
printf("hallo");
return arr; //KO Array arr ist nach Funktionsende nicht mehr gültig
}
Die bei der Parameterübergabe alternativen Schreibweisen für den Datentyp sind hier nicht möglich:
char [] function(void) //KO
char [3] function (void) //KO
char (*arr)[3] function(void) //KO
char *function(void) //Zeiger auf Char!
Alternativ bietet es sich an, ein Alias für ein Array zu erstellen und diesen als Rückgabewerte zu nutzen. Dies verbessert zudem die Lesbarkeit des Codes:
typedef int (*alias_t)[3];
alias_t foo(void) {
return (alias_t) NULL;
}
Call by Value
[Bearbeiten]Strukturen können wahlweise als Call-By-Value und Call-by-Reference übergeben werden. Über den Weg, ein Array in eine Struktur zu packen, kann ein Array auch als Call-by-Value übergeben werden:
struct arr {
int arr[4][3]; //sizeof(int)*3*4=48-Bytes
};
struct arr foo(struct arr par) {
struct arr lok=par;
//Kopieren von 48-Byte von par nach lok;
return lok;
//Kopieren von 48-Byte aus der lokalen Variable par nach ret
}
struct arr ret=foo((struct arr){.arr={{1,2,3},{4}} });
//Kopieren von 48 Bytes vom anonymous Array in die lokale variable par
Const Matrizen
[Bearbeiten]Entsprechend Const-Zeiger sollten Zeiger auf Arrays als const übergeben werden. Dies verhindert, dass der Callee Änderungen am Array durchführen kann:
void lut1(const int (*arr)[10]) {
arr[1][1]=3; //KO Const Array kann nicht beschrieben werden
}
void lut2(const int arr[][9] ) {
arr[1][1]=3; //KO Const Array kann nicht beschrieben werden
}
Sonstiges
[Bearbeiten]- In einer Struktur kann das letzte Element ein Array ohne Größenangabe sein (siehe Datentypen:Incomplete Array)
- Bei einem Prototyp für ein Array kann wie bei Funktionsaufrufen die linke Dimension entfallen. Bei fehlender linken Dimension versagt sizeof auf den Prototyp
//Prototypen extern int vect[]; extern int arr1[][]; //KO keine Dimensionsangabe extern int arr2[][3]; extern int arr3[4][3]; void foo(void) { vect[1]=3; //OK da linke Dimensionsangabe nicht notwendig arr1[1][2]=3; //KO da keine Dimensionsangabe im Prototyp vorhanden arr2[1][2]=3; //OK da linke Dimensionsangabe nicht notwendig size_t vect_size=sizeof(vect); //KO aufgrund fehlender Dimensionsangabe size_t arr2_size=sizeof(arr2); //KO aufgrund fehlender Dimensionsangabe size_t arr3_size=sizeof(arr3); } //Definitionen int vect[3]; int arr1[4][3]; int arr2[4][3]; int arr2[4][3];
- Bei Arrayzugriffen können entsprechend dem Assoziativgesetz Arrayname und Index 'ausgetauscht' werden:
array[index] → index[array]
//Quelle: https://gist.github.com/fay59/5ccbe684e6e56a7df8815c3486568f01 int foo(int* ptr, int index) { //When indexing, the pointer and integer parts //of the subscript expression are interchangeable. return ptr[index] + index[ptr]; //It works this way, according to the standard (§6.5.2.1:2), //because A[B] is the same as *(A + B), and addition //is commutative.} }
- Der Dereferenzierungoperator, ergänzt um Zeigerarithmetik und der Array Elementzugriff sind identisch:
int arr[4][5][6]; arr[1][1][1]=1; //identisch zu *(arr[1][1]+1)=1; arr[0][1][2]=2; //identisch zu *(*(arr[0]+1)+2)=1; arr[3][2][1]=3; //identisch zu *(*(*(arr+3)+2)+1)=3;
C++
[Bearbeiten]Wie in C können auch in C++ von jedem Datentyp Arrays angelegt werden. Dies gilt auch für Klassen:
int arr[10];
class ABC {
public:
int a[10];
ABC(void) {}
} obj1[10];
ABC obj2[20];
ABC *pobj=new ABC[30]();
std::string arr_of_strings[4];
Die Dimension dieser Arrays wird mit der Definition angegeben und kann zur Laufzeit nicht geändert werden. Der Arrayname ist wie in C nur ein Zeiger auf das erste Element.
VLA sind in GNU-C++ enthalten, jedoch kein Bestandteil der C++ Spezifikation.
Mit der Klasse std:array wird ein erweiterter Array-Datentyp bereitgestellt, der ergänzende Methoden für den Vergleich, das Sortieren, usw. zur Verfügung stellt:
//Quelle: https://en.cppreference.com/w/cpp/container/array
std::array<int, 3> a1{{1, 2, 3}};
std::array<int, 3> a2 = {1, 2, 3};
// Container operations are supported
std::sort(a1.begin(), a1.end());
std::ranges::reverse_copy(a2, std::ostream_iterator<int>(std::cout, " "));
std::cout << '\n';
// Ranged for loop is supported
std::array<std::string, 2> a3{"E", "\u018E"};
for (const auto& s : a3)
std::cout << s << ' ';
Auf Basis der Klassen std::vectoren und std::list aus der Standard Template Library (STL) stehen 'Arrays' zur Verfügung, deren Größe während der Laufzeit dynamisch geändert werden können. Zugriffe auf Objekte dieser Klasse sind folglich langsamer als reine Array Zugriffe.
Die Klasse std::vector entspricht dem klassischen Array, d.h. die Elemente sind nacheinander im Speicher angeordnet. Beim Anlegen eines std::vector wird mehr Speicher reserviert, als notwendig, so dass ein Einfügen eines Elementes nicht jedesmal zu einem Realloc führt. Ein Einfügen in der Mitte des Vectors bedingt das 'hochschieben' aller Elemente über der Einschiebeposition:
//Quelle: https://en.cppreference.com/w/cpp/container/vector
// Create a vector containing integers
std::vector<int> v = {8, 4, 5, 9};
// Add two more integers to vector
v.push_back(6);
v.push_back(9);
// Overwrite element at position 2
v[2] = -1;
v[10] = -1; //KO Programmabsturz
// Print out the vector
for (int n : v)
std::cout << n << ' ';
std::cout << '\n';
Die Klasse std::list basiert auf einer doppelt verketten Liste. Beim Einfügen wird Speicher für die Daten und für die Verkettungselemente vom Heap reserviert. Im Anschluss werden einzig die Zeiger des vorliegenden und nachfolgenden Elementes umgebogen. Der Zugriff auf ein Element bedingt das Durchlaufen der Liste vom Anfang oder Ende, bis das Zielobjekt gefunden wurde:
//Quelle: https://en.cppreference.com/w/cpp/container/list
// Create a list containing integers
std::list<int> l = {7, 5, 16, 8};
// Add an integer to the front of the list
l.push_front(25);
// Add an integer to the back of the list
l.push_back(13);
// Insert an integer before 16 by searching
auto it = std::find(l.begin(), l.end(), 16);
if (it != l.end())
l.insert(it, 42);
// Print out the list
for (int n : l)
std::cout << n << ", ";
std::cout << "\n";