Chapter 17 of 48

Arrays

Suppose you need to store the marks of 60 students. Creating 60 separate variables (m1, m2, ..., m60) would be painful, and you could not loop over them. What we want is one name for a whole row of values, where each value can be reached by its position. That is exactly what an array gives us.

In this chapter we will learn the built-in (C-style) arrays of C++: how they are laid out in memory, how to create, initialise and loop over them, how they behave when passed to functions, two-dimensional arrays and the address formulas asked in GATE, and the classic bugs such as going out of bounds. Character arrays used as text are covered in the next topic, Strings.

What is an Array?

An array is a fixed-size collection of elements of the same type, stored in contiguous (back-to-back) memory locations, where each element is accessed by an integer index starting from 0.

Three words in that definition matter a lot:

  • Fixed-size: the number of elements is decided at compile time and can never change.

  • Same type: an int array holds only int values.

  • Contiguous: element 1 sits right after element 0 in memory, with no gaps. This is what makes arrays fast.


Declaring and Using an Array

The syntax is type name[size];, where size must be a compile-time constant greater than zero.

#include <iostream>
#include <iterator>   // std::size (C++17)

int main() {
    int marks[5] = {78, 92, 65, 88, 71};

    std::cout << "First mark: " << marks[0] << '\n';
    std::cout << "Last mark:  " << marks[4] << '\n';

    marks[2] = 70;                      // change the third element

    std::cout << "Number of elements: " << std::size(marks) << '\n';
    std::cout << "Size in bytes:      " << sizeof(marks) << '\n';

    for (std::size_t i = 0; i < std::size(marks); ++i) {
        std::cout << "marks[" << i << "] = " << marks[i] << '\n';
    }
}

Output:

First mark: 78
Last mark:  71
Number of elements: 5
Size in bytes:      20
marks[0] = 78
marks[1] = 92
marks[2] = 70
marks[3] = 88
marks[4] = 71

Points to notice:

  • The valid indexes of a 5-element array are 0 to 4. marks[5] does not exist.

  • std::size(marks) (C++17, header <iterator>) gives the number of elements. Before C++17 people wrote sizeof(marks) / sizeof(marks[0]), which is 20 / 4 = 5 here (with a 4-byte int).

  • sizeof(marks) gives the size of the whole array in bytes, not the element count.

  • The loop counter is std::size_t, the unsigned type that std::size and sizeof return. Using int would trigger a signed/unsigned comparison warning under -Wall -Wextra.


How an Array Sits in Memory

If marks starts at address 1000 and an int takes 4 bytes, the elements are laid out like this:

index:      [0]     [1]     [2]     [3]     [4]
          ┌───────┬───────┬───────┬───────┬───────┐
marks     │  78   │  92   │  70   │  88   │  71   │
          └───────┴───────┴───────┴───────┴───────┘
address:   1000    1004    1008    1012    1016

address of marks[i] = base address + i × sizeof(int)

This formula is the reason arrays are so useful. To reach marks[i] the computer does one multiplication and one addition, no matter how big the array is. So accessing any element by index takes O(1) time. It also explains why indexing starts at 0: the index is really an offset from the start, and the first element is 0 steps away from the start.

The flip side of being contiguous and fixed-size: inserting or deleting an element in the middle means shifting all the elements after it, which takes O(n) time.


Initialising Arrays

#include <iostream>

int globalArr[4];                  // global: every element is 0

void print(const int a[], int n) {
    for (int i = 0; i < n; ++i) {
        std::cout << a[i] << ' ';
    }
    std::cout << '\n';
}

int main() {
    int a[5] = {1, 2, 3, 4, 5};    // fully initialised
    int b[5] = {1, 2};             // rest become 0
    int c[5] = {};                 // all 0
    int d[5]{};                    // all 0 (brace initialisation, C++11)
    int e[] = {10, 20, 30};        // size deduced as 3

    std::cout << "a: "; print(a, 5);
    std::cout << "b: "; print(b, 5);
    std::cout << "c: "; print(c, 5);
    std::cout << "d: "; print(d, 5);
    std::cout << "e: "; print(e, 3);
    std::cout << "globalArr: "; print(globalArr, 4);
}

Output:

a: 1 2 3 4 5 
b: 1 2 0 0 0 
c: 0 0 0 0 0 
d: 0 0 0 0 0 
e: 10 20 30 
globalArr: 0 0 0 0 

Declaration

Result

int a[5] = {1, 2, 3, 4, 5};

All five given

int b[5] = {1, 2};

Missing elements are set to 0

int c[5] = {}; or int d[5]{};

All elements 0

int e[] = {10, 20, 30};

Size deduced from the list (3)

int f[3] = {1, 2, 3, 4};

Compile error: too many initialisers

int g[5]; (inside a function)

Elements are indeterminate (garbage)

int g[5]; (global or static)

All elements 0

A local array with no initialiser contains whatever happened to be in that memory. Reading such an element before assigning it is undefined behaviour in C++23 (C++26 reclassifies it as "erroneous behaviour", but the value is still meaningless). The habit to build: always initialise local arrays, even if only with {}.

A common myth is that int a[5] = {7}; sets every element to 7. It does not: a[0] becomes 7 and the other four become 0. = {0} happens to set all of them to 0 only because the "rest" rule fills the others with 0 too.


Looping with the Range-based for Loop

Since C++11, the range-based for loop visits each element of an array without any index:

#include <iostream>

int main() {
    int prices[] = {120, 45, 300, 80};

    // read each element (a copy)
    for (int p : prices) {
        std::cout << p << ' ';
    }
    std::cout << '\n';

    // modify each element: use a reference
    for (int& p : prices) {
        p += 10;
    }

    for (int p : prices) {
        std::cout << p << ' ';
    }
    std::cout << '\n';
}

Output:

120 45 300 80 
130 55 310 90 

In for (int p : prices), p is a copy of each element, so changing p would not change the array. Writing int& p makes p another name for the actual element, so p += 10 updates the array itself. We will study this & properly in the References topic; for now, remember: use & when the loop must modify the elements.

Use the range-for loop when you need every element in order. Use the index loop when you need the index itself, want to skip elements, or walk two positions at once.


Going Out of Bounds

C++ does not check array indexes. Reading or writing a[3] in a 3-element array, or a[-1], is undefined behaviour: the program might print garbage, silently corrupt another variable, crash, or appear to work perfectly. Unlike Java there is no exception to catch.

#include <iostream>

int main() {
    int a[3] = {10, 20, 30};
    int i = 3;                          // one past the last valid index
    std::cout << "a[3] = " << a[i] << '\n';   // undefined behaviour
}

A normal build may just print some random number. Built with the sanitizers (g++ -std=c++23 -g -fsanitize=address,undefined), the bug is caught immediately. Output (trimmed; addresses differ on every run):

a04_asan_oob.cpp:6:34: runtime error: index 3 out of bounds for type 'int [3]'
...
==704==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ae0674f002c ...
READ of size 4 at 0x7ae0674f002c thread T0
    #0 0x5f8afe6fb69d in main a04_asan_oob.cpp:6
...
    [32, 44) 'a' (line 4) <== Memory access at offset 44 overflows this variable

The most common cause is an off-by-one loop: for (int i = 0; i <= n; ++i) instead of i < n. Get used to the pattern "start at 0, stop before n". Running your programs with -fsanitize=address,undefined while practising is one of the best habits you can build.


Common Array Algorithms

Most array questions in exams and coding rounds are built from a handful of patterns. Here they are in one program:

#include <iostream>

int main() {
    const int n = 8;
    int a[n] = {34, 7, 23, 32, 5, 62, 32, 18};

    // 1. sum and average
    int sum = 0;
    for (int x : a) sum += x;
    std::cout << "Sum = " << sum << ", average = "
              << static_cast<double>(sum) / n << '\n';

    // 2. largest and smallest
    int largest = a[0], smallest = a[0];
    for (int i = 1; i < n; ++i) {
        if (a[i] > largest)  largest = a[i];
        if (a[i] < smallest) smallest = a[i];
    }
    std::cout << "Largest = " << largest << ", smallest = " << smallest << '\n';

    // 3. linear search
    int key = 23, pos = -1;
    for (int i = 0; i < n; ++i) {
        if (a[i] == key) { pos = i; break; }
    }
    std::cout << key << " found at index " << pos << '\n';

    // 4. reverse in place with two indexes
    for (int i = 0, j = n - 1; i < j; ++i, --j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    std::cout << "Reversed: ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';

    // 5. second largest distinct value in one pass
    int first = a[0], second = -1;   // assumes non-negative values
    for (int i = 1; i < n; ++i) {
        if (a[i] > first) {
            second = first;
            first = a[i];
        } else if (a[i] < first && a[i] > second) {
            second = a[i];
        }
    }
    std::cout << "Second largest = " << second << '\n';
}

Output:

Sum = 213, average = 26.625
Largest = 62, smallest = 5
23 found at index 2
Reversed: 18 32 62 5 32 23 7 34 
Second largest = 34
  • Initialise largest and smallest with a[0], not with 0; otherwise an array of negative numbers would give a wrong maximum.

  • Linear search checks each element once: O(n) time. (Binary search is O(log n), but needs a sorted array.)

  • Reversing with two indexes moving towards each other does n/2 swaps and needs no second array.

  • The second-largest loop is a favourite interview question because it is done in one pass, O(n), instead of sorting, O(n log n). The condition a[i] < first in the else if makes sure that a repeated copy of the largest value is never chosen as second.


Passing Arrays to Functions

When you pass an array to a function, the array is not copied. In almost every expression, the name of an array automatically converts to the address of its first element. This is called array-to-pointer decay, and we will see what it really means in the Pointers topic. Two consequences follow:

  1. The function works on the caller's array, so changes are visible after the call.

  2. The function does not know the size. A parameter written as int arr[] (or even int arr[10]) is really a pointer, so you must pass the size separately.

#include <iostream>

// 'arr' is really an int* here, so the size must be passed separately.
void doubleAll(int arr[], int n) {
    for (int i = 0; i < n; ++i) {
        arr[i] *= 2;                    // changes the caller's array
    }
}

// const promises we will only read the elements
int total(const int arr[], int n) {
    int s = 0;
    for (int i = 0; i < n; ++i) s += arr[i];
    return s;
}

int main() {
    int data[4] = {1, 2, 3, 4};
    doubleAll(data, 4);
    for (int x : data) std::cout << x << ' ';
    std::cout << "\ntotal = " << total(data, 4) << '\n';
}

Output:

2 4 6 8 
total = 20

Mark array parameters const when the function only reads them, as total does. The compiler will then reject any accidental write.

The sizeof Trap

Because the parameter is a pointer, sizeof inside the function gives the size of a pointer, not of the array:

#include <iostream>

void show(int arr[]) {
    std::cout << sizeof(arr) << '\n';   // NOT the array size!
}

int main() {
    int a[10] = {};
    std::cout << sizeof(a) << '\n';     // 40
    show(a);
}

Output (on a typical 64-bit system):

40
8

Inside show, arr is an int*, so sizeof(arr) is the size of a pointer (8 bytes here), not 40.

GCC even warns about it (this warning is on by default):

a06_warn_sizeof.cpp: In function ‘void show(int*)’:
a06_warn_sizeof.cpp:4:25: warning: ‘sizeof’ on array function parameter ‘arr’ will return size of ‘int*’ [-Wsizeof-array-argument]
    4 |     std::cout << sizeof(arr) << '\n';   // NOT the array size!
      |                        ~^~~~
a06_warn_sizeof.cpp:3:15: note: declared here
    3 | void show(int arr[]) {
      |           ~~~~^~~~~

The same applies to std::size(arr): on such a parameter it does not compile at all, which is actually helpful because it stops the bug early.


Two-Dimensional Arrays

A 2D array is an array of arrays: int a[2][3] is an array of 2 elements, each of which is an array of 3 ints. Think of it as a table with 2 rows and 3 columns.

#include <iostream>

const int ROWS = 2;
const int COLS = 3;

// the number of columns must be part of the parameter type
void print(const int m[][COLS], int rows) {
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < COLS; ++j) {
            std::cout << m[i][j] << '\t';
        }
        std::cout << '\n';
    }
}

int main() {
    int a[ROWS][COLS] = {
        {1, 2, 3},
        {4, 5, 6}
    };
    int b[ROWS][COLS] = {{10, 20, 30}, {40, 50, 60}};
    int sum[ROWS][COLS];
    int t[COLS][ROWS];                  // transpose has swapped dimensions

    for (int i = 0; i < ROWS; ++i) {
        for (int j = 0; j < COLS; ++j) {
            sum[i][j] = a[i][j] + b[i][j];
            t[j][i] = a[i][j];
        }
    }

    std::cout << "a + b:\n";
    print(sum, ROWS);

    std::cout << "transpose of a:\n";
    for (const auto& row : t) {         // range-for works on 2D too
        for (int x : row) std::cout << x << '\t';
        std::cout << '\n';
    }

    std::cout << "sizeof(a) = " << sizeof(a)
              << ", sizeof(a[0]) = " << sizeof(a[0]) << '\n';
}

Output:

a + b:
11	22	33	
44	55	66	
transpose of a:
1	4	
2	5	
3	6	
sizeof(a) = 24, sizeof(a[0]) = 12

Things to remember:

  • a[i][j] means row i, column j. Rows come first.

  • When passing a 2D array, every dimension except the first must be given (int m[][COLS]), because the function needs the row length to compute where row i begins.

  • sizeof(a) is 2 × 3 × 4 = 24 bytes, and sizeof(a[0]) (one row) is 3 × 4 = 12 bytes.

  • In the range-for over a 2D array, the outer variable must be a reference (const auto& row). With plain auto row, each row would decay to a pointer, and the inner loop would not compile.

Row-Major Order and the Address Formula

Memory is one-dimensional, so the rows of a 2D array are stored one after another. C and C++ use row-major order: all of row 0, then all of row 1, and so on.

int a[2][3] = {{1, 2, 3}, {4, 5, 6}};

Logical view          Memory (row-major)
 1  2  3              ┌───┬───┬───┬───┬───┬───┐
 4  5  6              │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │
                      └───┴───┴───┴───┴───┴───┘
                       a[0][0]     a[1][0]   a[1][2]

For an array with R rows and C columns, element size w bytes, and base address B (indexes starting at 0):

Row-major:     address of a[i][j] = B + (i × C + j) × w
Column-major:  address of a[i][j] = B + (j × R + i) × w

If indexes start at lower bounds Lr (rows) and Lc (columns) instead of 0:
Row-major:     B + ((i − Lr) × C + (j − Lc)) × w

Column-major order is used by Fortran, MATLAB and many maths libraries; C and C++ built-in arrays are always row-major. Row-major order is also why looping over i in the outer loop and j in the inner loop is faster: you walk memory in order, which is friendly to the CPU cache.

Worked example. int A[10][20] with base address 1000 and a 4-byte int. Find the address of A[5][7].

Row-major:    1000 + (5 × 20 + 7) × 4 = 1000 + 107 × 4 = 1428
Column-major: 1000 + (7 × 10 + 5) × 4 = 1000 +  75 × 4 = 1300

What You Cannot Do with Built-in Arrays

No assignment, no whole-array comparison

b = a; does not compile for arrays. And a == b does compile, but it compares the addresses of the two arrays (after decay), never the elements, so it is always false for two different arrays. This was so error-prone that C++20 deprecated it, and C++26 makes it an error. GCC 15 in C++23 mode says:

int main() {
    int a[3] = {1, 2, 3};
    int b[3] = {1, 2, 3};
    bool same = (a == b);   // compares addresses, not elements!
    return same;
}
a10_warn_copy.cpp: In function ‘int main()’:
a10_warn_copy.cpp:4:20: warning: comparison between two arrays is deprecated in C++20 [-Warray-compare]
    4 |     bool same = (a == b);   // compares addresses, not elements!
      |                  ~~^~~~
a10_warn_copy.cpp:4:20: note: use unary ‘+’ which decays operands to pointers or ‘&a[0] == &b[0]’ to compare the addresses

To copy or compare elements, use a loop or the standard algorithms (covered fully in STL Algorithms):

#include <algorithm>   // std::copy, std::equal
#include <iostream>
#include <iterator>    // std::begin, std::end

int main() {
    int a[3] = {1, 2, 3};
    int b[3];

    // b = a;          // error: arrays cannot be assigned
    std::copy(std::begin(a), std::end(a), std::begin(b));

    std::cout << std::boolalpha
              << "equal elements? "
              << std::equal(std::begin(a), std::end(a), std::begin(b)) << '\n';
}

Output:

equal elements? true

No size chosen at run time

The size of a built-in array must be a constant expression. Code like this is not standard C++:

int main() {
    int n = 5;
    int a[n];          // variable-length array: not standard C++
    a[0] = 1;
    return a[0];
}

GCC accepts variable-length arrays (VLAs) as an extension borrowed from C, so the code may seem to work. Compile with -pedantic and you get:

a12_warn_pedantic_vla.cpp: In function ‘int main()’:
a12_warn_pedantic_vla.cpp:3:9: warning: ISO C++ forbids variable length array ‘a’ [-Wvla]
    3 |     int a[n];          // variable-length array: not standard C++
      |         ^

Other compilers, such as MSVC, reject it outright. When the size is known only at run time, use std::vector (see the vector topic) or dynamic allocation (see Dynamic Memory Allocation).

No huge local arrays

Local arrays live on the stack, which is only a few megabytes. int big[10000000]; (40 MB) inside main will usually crash with a stack overflow. Make such arrays global or static (they are then stored in a separate data area), or use std::vector, which keeps its elements on the heap.


Built-in Arrays vs Standard Containers

Modern C++ code often prefers two library types that fix the problems above. We will meet them in later topics, but it helps to know where they fit:

Feature

Built-in array int a[5]

std::array<int, 5> (C++11)

std::vector<int>

Size

Fixed, compile time

Fixed, compile time

Can grow and shrink at run time

Knows its own size

Only in the declaring scope

Yes, .size()

Yes, .size()

Copy with =

No

Yes

Yes

Compare with ==

No (compares addresses)

Yes, element by element

Yes, element by element

Decays to pointer when passed

Yes

No

No

Bounds-checked access

No

.at(i) throws

.at(i) throws

Where elements live

Stack (if local)

Stack (if local)

Heap

Built-in arrays are still worth knowing well: they appear in older code, in university exams and GATE, in competitive programming, and they are what std::array and std::vector are built on.


Common Mistakes

  • Off-by-one errors: using i <= n or accessing a[n]. The last valid index is n - 1.

  • Uninitialised local arrays: summing int a[10]; without setting the elements first gives garbage.

  • Using sizeof on an array parameter to find its length. Pass the size as a separate argument.

  • Thinking int a[5] = {1}; fills every element with 1. Only the first element is 1.

  • Comparing or assigning arrays with == and =. Use loops or std::equal / std::copy.

  • Relying on VLAs like int a[n];. They are a GCC extension, not C++.

  • Initialising the maximum with 0 instead of the first element.


Interview and GATE Questions

Why do array indexes start at 0 in C and C++?

Because the index is an offset from the starting address: the address of a[i] is base + i × size. The first element is at offset 0, so no extra subtraction is needed on every access.

int A[1..10][1..15] (indexes start at 1) is stored in row-major order with base address 100 and 2-byte elements. What is the address of A[4][5]?

100 + ((4 − 1) × 15 + (5 − 1)) × 2 = 100 + 49 × 2 = 198. In column-major order it would be 100 + ((5 − 1) × 10 + (4 − 1)) × 2 = 100 + 43 × 2 = 186.

What does int a[5] = {0}; do? And int a[5] = {3};?

The first sets all five elements to 0. The second sets a[0] to 3 and the remaining four to 0.

Inside void f(int arr[100]), what is sizeof(arr)?

The size of a pointer (8 bytes on typical 64-bit systems, 4 on 32-bit), because array parameters are adjusted to pointers. The 100 is ignored by the compiler.

Is 3[a] the same as a[3]?

Yes, for built-in arrays. The built-in subscript E1[E2] is defined as *((E1) + (E2)), and addition is commutative, so both mean *(a + 3). Never write it in real code; it only appears in trick questions. (The Pointers topic explains *(a + 3).)

What is the time complexity of accessing, searching and inserting in an unsorted array of n elements?

Access by index: O(1). Search: O(n). Insert or delete at an arbitrary position: O(n), because elements must be shifted. Inserting at the end of a partly filled array (if there is space): O(1).

Why must the column count be given when passing a 2D array to a function?

To compute the address of m[i][j] the function uses base + (i × C + j) × w, which needs C. The number of rows is not needed for the address calculation, so the first dimension may be omitted.

Is int n; std::cin >> n; int a[n]; valid C++?

No. Array bounds must be constant expressions in standard C++. GCC and Clang accept it as an extension (a VLA), but it is not portable and risks stack overflow for large n. Use std::vector<int> a(n); instead.

In Simple Words

An array is a fixed number of same-type values stored side by side in memory. Index i is simply an offset from the start, which is why indexing begins at 0 and any element can be reached in O(1) time.

  • Valid indexes are 0 to n − 1; going outside is undefined behaviour, not an exception.

  • Always initialise local arrays (int a[10]{};).

  • Arrays decay to pointers when passed to functions, so pass the size too.

  • 2D arrays are stored row by row: address = B + (i × C + j) × w.

  • Arrays cannot be copied with = or compared with ==; prefer std::array or std::vector in modern code.