Array Data Type

Array Type

  • A derived type to store a sequentially stored list of values of the same base type

  • Advantage:

    • simple native syntax

    • fast random access by index

    • minimal memory usage

  • Disadvantage:

    • not easy to use

    • fixed size

    • not secure, allows out-of-range access

    • causing memory errors

  • Memory allocation

    • storage as two parts: pointer and data

    • local array

      • pointer in stack

      • continuous memory block in stack

    • dynamic array

      • pointer in stack as a local variable

      • continuous memory block in heap (must allocate manually with new)

  • [] operator

    • to declare a local array int arr[10];

      • size must be specified (empty [] not allowed) except with size inference with initialization

      • size must be a compilation time constant

    • to refer to an element in the list arr[n]

      • no out-of-range check

      • it is a simplified syntax of the equivalent pointer syntax *(arr + n)

  • Size handling

    • Store in a separate variable

    • Call sizeof() function

      • size = sizeof(arr) / sizeof(arr[0])

      Warning

      Not recommended! It will fail after the array variable is passed/assigned

  • Initialization

    • automatic size inference by the compiler int arr[] = {1, 2, 3}

    • fill with 0 if provided values are less than the size

  • Pitfalls

    • out-of-range index

    • incorrect size handling

    • Java syntax int [] arr or int arr[]

    • returning a local array from a function

Example

 1// ==== Array ====
 2
 3// ---- Correct ----
 4
 5// size must be a compilation time constant
 6#define SIZE1 4  // macro
 7const int SIZE2 = 4;  // constant
 8int arr1[4];  // literal
 9int arr2[SIZE1];
10int arr3[SIZE2];
11
12// local array arr4
13// pointer in stack
14// 10 continuous int in stack allocated at the same time
15int arr4[10];
16
17// dynamic array arr5
18// declared as a pointer
19// pointer in stack, allocated when declared
20int *arr5;
21// 10 continuous int in heap, allocated by the new operator
22arr5 = new int[10];
23// must delete later to release the heap memory
24delete [] arr5;
25
26// initialization
27int arr6[10] = {};  // all elements to 0
28int arr7[] = {1, 2, 3, 4};  // size will be inferred by the compiler
29int size = sizeof(arr7) / sizeof(arr7[0]);  // get 4
30// int size = sizeof(arr7) / sizeof(int);  // get 4
31int arr8[4] = {1, 2}; // get contents 1, 2, 0, 0
32
33// new syntax of initialization
34int arr9[4]{};  // all 0
35int arr10[]{1, 2, 3, 4};  // size 4
36
37int *arr11 = new int[4]{1, 2, 3, 4};
38int *arr12 = new int[4]{};  // all zeros
39
40// ---- Wrong ----
41
42// size not known during compilation
43// WARNING: This is allowed with g++ but not allowed in standard C++
44//          g++ support variable length array as an extension
45int size;
46cin >> size;
47int arr[size];
48
49// bad/no size
50int arr[3.0];
51
52// Java syntax
53int [] arr1;
54int arr1[];
55
56// out-of-range access
57int arr[100];
58cout << arr[100];

Pointer syntaxes for array

  • the array variable holds the memory address to the first element

  • first element: *arr is the same as arr[0]

  • \(n^{th}\) element: *(arr + n) is the same as arr[n]

1int arr1[4] = {1, 2, 3, 4};
2int *arr2 = arr1 + 1;
3
4// &arr1[0] is same as arr1
5// arr2 can be used as an array sharing data with arr1
6// arr2 have a max size of 3
7// arr2[0] is the same as arr1[1]
8cout << arr1[1] << endl;  // get 2
9cout << arr2[0] << endl;  // get 2

Array Based Data Structures

  • Vector

  • Hash Table

  • Heap