Arrays and indexing

Why it exists

A program often has many values of the same kind: the marks of 60 students, the pixels of a row, the digits of a number. Declaring 60 separate variables is impractical, and no loop could visit them. An array gives one name to a whole sequence and lets the program pick an element by a number, its index.

The machine reason it works so well is that the elements sit side by side in memory. To reach element number $i$ the computer does not search: it multiplies and adds. That makes access a constant-time operation, and it is why arrays are the foundation under strings, matrices, heaps and hash tables.

Prerequisites

Precise definitions

• Array. A sequence of $n \ge 1$ objects of the same type, stored in contiguous memory. int a[5]; declares five ints. The number of elements is part of the array's type: int[5] and int[6] are different types.
• Index. Elements are numbered from 0. The valid indices of a[5] are 0, 1, 2, 3, 4. There is no index 5.
• No bounds checking. C never checks an index. Reading or writing a[5] or a[-1] is undefined behaviour: it may crash, print garbage, or silently corrupt a neighbouring variable.
• Size. sizeof a is $n \times \texttt{sizeof(element)}$. The number of elements is sizeof a / sizeof a[0]. This works only where a really is an array (not a function parameter, see the functions page). In this course an int is 4 bytes, as on typical gcc platforms; the standard only requires a minimum, so GATE questions state it.
• Address of an element. If the array starts at address $B$ and each element takes $w$ bytes, then

$\text{address of } a[i] = B + i \times w.$

This is the whole idea of an array. The lower bound is 0 in C. In the language-neutral questions GATE often asks, the lower bound $L$ can be any integer, and the formula becomes $B + (i - L) \times w$. The number of elements of an array with bounds $L \ldots U$ is $U - L + 1$.

• Subscript is pointer arithmetic. By definition (C11 6.5.2.1), a[i] means *(a + i). The array name a in an expression becomes a pointer to its first element (it decays), and adding $i$ to a pointer moves it by $i$ elements. Because + is commutative, i[a] is the same thing. Nobody writes it, but a trap question may. The pointers page explains the arithmetic in full.
• When the name does not decay. An array expression keeps its array nature only as the operand of sizeof or of unary & (C11 also lists _Alignof), and a string literal that initialises an array keeps it too. In every other expression it turns into a pointer.
• Initialisation (C11 6.7.9).
  • int a[5] = {1, 2}; sets $a = \{1, 2, 0, 0, 0\}$. Elements without an initialiser are set to zero.
  • int a[5] = {0}; sets all five to zero.
  • int a[] = {1, 2, 3}; lets the compiler count: the array has 3 elements.
  • An array with static storage duration (global or static) that has no initialiser is entirely zero.
  • A local (automatic) array with no initialiser contains indeterminate values. Reading them is a bug.
• Arrays are not first-class values. You cannot assign one array to another (b = a; is an error), you cannot return an array from a function (a struct that contains an array can be copied and returned), and a == b on two arrays compares their addresses, not their contents. To copy contents you loop or use memcpy.

How it works

Step through the program below. It is a real run: the addresses are read from the running machine. The one fact to see is the address column. Each cell is exactly 4 higher than the one before it, so a[i] needs no search, only "start + i × 4".

Things to notice:

• The variable i is a separate object. It is not part of the array. The array is only the five cells.
• Writing a[i + 2] uses an expression as the index. Any integer expression is allowed.
• The loop reads the cells in order, so the memory is walked in order. This is also the reason arrays behave well with caches, which the COA subject returns to.

Operations and their cost

Worked examples

#include <stdio.h>
 
int main(void) {
    int a[5] = {10, 20, 30, 40, 50};
    printf("%zu %zu %td\n", sizeof a, sizeof a / sizeof a[0],
           (char *)&a[1] - (char *)&a[0]);
    return 0;
}

20 5 4

#include <stdio.h>
 
int g[3];
 
int main(void) {
    int a[6] = {1, 2, 3};
    int b[] = {4, 5, 6, 7};
    for (int i = 0; i < 6; i++) printf("%d ", a[i]);
    printf("\n%zu %d %d %d\n", sizeof b / sizeof b[0], g[0], g[1], g[2]);
    return 0;
}

1 2 3 0 0 0
4 0 0 0

#include <stdio.h>
 
int main(void) {
    int a[4] = {5, 6, 7, 8};
    printf("%d %d %d\n", a[2], *(a + 2), 2[a]);
    return 0;
}

7 7 7

#include <stdio.h>
 
int main(void) {
    int a[6] = {10, 20, 30, 40};
    int n = 4, pos = 2, x = 25, shifts = 0;
    for (int i = n; i > pos; i--) {
        a[i] = a[i - 1];
        shifts++;
    }
    a[pos] = x;
    n++;
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n%d\n", shifts);
    return 0;
}

10 20 25 30 40
2

#include <stdio.h>
 
int main(void) {
    int f[5] = {1, 2, 3, 4, 5};
    int r[5] = {1, 2, 3, 4, 5};
    for (int i = 1; i < 5; i++) f[i] = f[i] + f[i - 1];
    for (int i = 4; i >= 1; i--) r[i] = r[i] + r[i - 1];
    for (int i = 0; i < 5; i++) printf("%d ", f[i]);
    printf("\n");
    for (int i = 0; i < 5; i++) printf("%d ", r[i]);
    printf("\n");
    return 0;
}

1 3 6 10 15
1 3 5 7 9

Cheat box

Traps and GATE patterns

Connections

The formula $B + i \times w$ is the same base plus scaled index calculation that a CPU performs in an indexed addressing mode. Where an array lives (stack, data, heap) is explained on the memory layout page. Two-dimensional arrays extend the same formula and are the subject of multidimensional arrays.

PYQs

Consider the following C function in which size is the
number of elements in the array E: The value returned
by the function MyX is the
int MyX(int *E, unsigned int size)
{

int Y = 0;

int Z;

int i, j, k;

for(i = 0; i< size; i++)

 Y = Y + E[i];

for(i = 0; i< size; i++)

for(j = i; j < size; j++)

{

Z = 0;

for(k = i; k <= j; k++)

Z = Z + E[k];

if (Z > Y)

Y=Z;
}
return Y;
}

The value returned by the function MyX is the

The following function computes the maximum value
contained in an integer array
           p[] of size n (n >= 1).
int max(int *p, int n) {
int a=0, b=n-1;
while (__________)
{
     if (p[a] <= p[b])
    {
        a = a+1;
}
      else
{
     b = b-1;
     }
}
return p[a];
 }
The missing loop condition is

Let A be a square matrix of size n × n. Consider the
following pseudocode. What is the expected output?
C = 100;
for i = 1 to n do
for j = 1 to n do
{
Temp = A[i] [j] + C;
A [i] [j] = A[j] [i];
 A[j][i] = Temp – C;
 }
for i = 1 to n do
  for j = 1 to n do
        output (A[i][j]);

A Young tableau is a 2D array of integers
increasing from left to right and from top to bottom.
Any unfilled entries are marked with ∞, and hence
there cannot be any entry to the right of, or below a
∞. The following Young tableau consists of unique
entries.

When an element is removed from a Young
tableau, other elements should be moved into its
place so that the resulting table is still a Young
tableau (unfilled entries may be filled with a ∞).
The minimum number of entries (other than 1) to
be shifted, to remove 1 from the given Young
tableau is    .

Suppose c = ⟨c[0], ..., c[k-1]⟩ is an array of length k,
where all the entries are from the set {0,1}. For any
positive integers a and n, consider the following
pseudocode.
DOSOMETHING (c, a, n)
z←1
for i←0 to k-1
do z←z2 mod n
if c[i]=1
then z←(z×a) mod n
return z
If k = 4, c = ⟨1, 0, 1, 1⟩, a = 2, and n = 8
then the output of DO SOMETHING (c, a, n) is

.

DATA STRUCTURE

Self-check

#include <stdio.h>
 
int main(void) {
    int a[4] = {1, 2};
    int s = 0;
    for (int i = 0; i < 4; i++) s += a[i];
    printf("%d %zu\n", s, sizeof a);
    return 0;
}

3 16

Revision card

References