Arrays and Pointers

Fixed-size array

We’ve had variables to store data of specific primitive types and to perform powerful tasks like arithmetic operations and several control structures involving conditions and loops. However, this method has its limitations, as we’re only able to store a single data value in each variable. This becomes a problem when we need to maintain data with more than one value. The common solution of using multiple variables is not efficient when we need to search for a specific element. To overcome this issue, we’ll introduce fixed-size arrays.

In an array, contiguous blocks of a fixed length are allocated in the memory.

The above illustration depicts the memory arrangement of an array of four integers generated by the instruction int A[4] = {3, 2, 4, 1};. The result is four adjacent memory blocks, each consisting of four bytes, with a distinct address. This raises a question: how can we effectively access these memory blocks within the array?

Accessing the array

Accessing elements within an array can be achieved through two methods. The first method involves establishing a relationship between arrays and pointers, while the second method utilizes the [] operator. Let’s explore these approaches in detail.

1. Array indexing through the subscript [] operator

When working with arrays, accessing their memory locations can be made easier using the subscript operator ([]). For instance, A[0] allows us to access the data at the first index of the array. Similarly, A[1], A[2], A[3], and so on, access subsequent memory locations. This subscript-based approach simplifies accessing array elements and is particularly useful when dealing with large datasets, as it only requires two variables: the base of the memory, like the name of the array, and the index, which is nothing but an offset you want to move from the base address.

Here are two examples in which we display the content of an array using the subscript operator [], with hardcoded indexing in the ArrayIndexing.cpp file and variable-based indexing in the ArrayIndexingThroughLoop.cpp file.

2. Arrays and pointers

Accessing memory blocks within an array is straightforward. The array name, like A, represents the initial memory location of the array. Essentially, the name A serves as an address for the array’s first memory location. While this appears similar to a pointer, there’s a subtle difference: A has the same address and points to the same memory location. In contrast, a typical pointer usually has a distinct address and points to a different location.

By dereferencing the array’s name as a pointer, we can easily access the data value stored at the first index. We can manipulate the array name by adding an offset to access subsequent memory locations. For example, adding 1 to the base address of array A gives us the address of the next memory location, incrementing by the data type size (such as four bytes for an integer). This approach allows us to access all other memory locations and their data values.

The provided code shows how we can access the data of an array using its name.

Visually, the memory of the above program looks as shown in the following illustration. Notice that dotted addresses in memory are not physical labels (they do not exist physically). They are logical representations that the operating system maps and manages automatically during the execution of the program.

The sizeof() operator with arrays

The sizeof() operator in C++ determines the size of a data type or object at compile-time. Applying sizeof() to an array name, like sizeof(array_name), provides the total size of the array in bytes. Dividing this by the array’s data type size will give us the array’s capacity. This approach is convenient and simple. Let’s explore an example showing the usage of sizeof() to calculate array size.

Arrays and functions

When passing arrays to functions in C++, we pass an array name as an argument, which acts as a pointer to the first element. Usually, after that array name (the base address), we pass the size on which the function performs manipulation.

In the example of the print() function, the parameter is defined either as int arr[] or int* arr. However, it's important to note that int* may not necessarily represent an array; instead, it can represent the address of a location. On the other hand, logically, int arr[] always suggests the passed base address of an array.

This notation is used to indicate that the function expects an array as the parameter. The array name arr is treated as a pointer (holding an address as the relative base), enabling traversal and access to individual elements of the array, starting from the passed base address.

Tip: Run the above two codes separately and understand their working.

• The printFunctionWithMsg.cpp file: On lines 3–10, the powerful concept of only passing the base address as an argument provides great flexibility. On the receiving end, the function parameter is simply a pointer unaware of anything other than the base address. The size parameter indicates the amount of memory offset from the base address (held in A) that needs to be accessed. This flexibility allows us to avoid creating separate print() functions for every array, showcasing the true power of functions—reusability.

This concept also introduces another powerful idea: we can access the entire array and a portion of it by considering any address as the base address. This means we can access a specific range or subset of elements within the array, starting from a desired address. It provides granular control over the data we want to work with, further enhancing the versatility of array usage.

Next, there are some important initialization methods that we should learn.

Revisiting initialization of arrays

Let’s look at the following example:

• In the intArraysInitializations.cpp file, we define four arrays: A (initialized with all values set to 0), B (initialized with values 1 to 10), C (initialized with values 1, 2, and 3), and D (initialized with values 1 and 2 followed by eight zeros). The print() function is used to display the elements of each array.

• In the charArraysInitialization.cpp file, we define four character arrays: A (initialized with the characters 'a' to 'j'), B (initialized with 'a', 'b', and eight null characters ('\0')), and C and D (both initialized with the string "abc" followed by a null character ('\0')). The print() function is used to display the elements of each character array. Additionally, arrays B, C, and D are directly printed using cout, which interprets character array names as null-terminated strings and prints the characters of the array until it reaches the null character '\0' and then stops. However, printing the array A directly using cout will not work as it lacks a null terminator, leading to unpredictable results. The case for printing E[] and F[] is similar. cout<<E will keep printing letters starting from the base address of E[] until it reads '\0', and therefore, by combining the values of both arrays, it prints "abab".

Let’s practice a few nontrivial examples for traversing and manipulating arrays.

Example 1: Reversing an array

Problem statement: Implement a function named reverse() that will take two arguments as input: the starting point of an array A and the total number of elements that need to be reversed. The function should reverse the specified elements of the array in place.

Note: We use the swap() function that is already implemented in the language.

• Lines 25–39: The given code demonstrates the manipulation of an integer array A by reversing its elements in different portions. Initially, the contents of A are displayed, followed by printing two portions of the array. The first portion consists of the first half of A, while the second portion consists of the remaining half. Subsequently, the code reverses the elements in each portion using the reverse() function. After the reversal, the modified content of A is displayed, and the two portions are printed again to showcase the changes. Overall, the code shows how to reverse elements within specific portions of an array, offering insights into array manipulation techniques.

• Lines 12–22: Within the reverse() function, two variables, start and end, are initialized. start is set to the first index of the array, while end is set to the last index. The function utilizes a while loop that continues as long as start is less than end. Inside the loop, the swap() function is used to exchange the values at A[start] and A[end], effectively reversing the elements. Then, start is incremented and end is decremented to move toward the middle of the array.
  

Example 2: Bubble sort

So far, we’ve learned how to manipulate the data within the array. In some cases, we need sorted data to solve our problem effectively. Various sorting algorithms have been proposed, and one of them is named bubble sort. In this example, we’ll learn the concept of the bubble sort algorithm and how we can implement it.

We know that when we boil a liquid, the molecules with higher kinetic energy form bubbles. These bubbles rise and reach the top. This is the inspiration for bubble sorting, according to which the elements that meet a certain condition after comparison are swapped (they rise).

The nested loop implementation

Sample program:

Before sorting in ascending order, let’s ensure we understand the central strategy of bubbling.

The bubbling strategy

First, we take the starting position i = 0. Then:

1. We compare the value at A[i] with its immediate neighbor: A[i]>A[i+1].

2. If the ith number is greater than the (i+1)th number, we exchange their positions by using the swap() function.

3. We repeat the above two steps until we reach the last possible pair.

Here’s the code that shows the bubbling step:

Let’s look at the animation that shows the bubbling process.

The above animation clearly shows that the maximum value will reach the end after the first bubbling ends. Similarly, the second iteration of bubbling will shift the second maximum value at the second to last position of the array.

But how many times do we need to repeat this bubbling step to complete sorting? To sort the array of $n$ elements, we must repeat the bubbling step $n-1$ times on the given array.

Here’s the code for sorting the array in ascending order:

Quiz

Let’s test your understanding with a short quiz.

Managing array size and capacity

An array is a powerful tool, but it has some limitations. For example, look at the array below. It has a specific size and elements.

The compiler allocates 16 consecutive bytes of memory and initializes them with four elements (each having four bytes of memory).

However, what if we need to add more elements to the array?

One approach is to create an array of a larger size (than required), like int A[1000]={2,3,4,5}. In this case, the compiler allocates 4,000 consecutive bytes of memory (1,000 blocks where each block is four bytes). It initializes the first four positions with the given elements, and the remaining part of the array is initialized to 0. This strategy enables us to add up to 994 more elements to the array, expanding its functionality.

So, generally, to address these limitations, it becomes crucial to manage both the size and capacity of the array, where the size of an array represents the number of elements currently present. In contrast, the capacity refers to the maximum number of elements the array can hold. By maintaining these two variables separately, we can optimize the efficiency of functions that operate on arrays.

In the following example code, the addElement() function is introduced. This function accepts an array A[] (the base address of the allocated memory), its size, capacity, and an element to be added. The function determines whether there is space to add the element by checking if the size is less than the capacity. The element is inserted at the next available index if space is available, and the size is incremented accordingly. This approach ensures efficient array capacity usage, preventing unnecessary iterations over unused elements.

• Lines 3–12: We implement the function addElement(), which takes four arguments: an array A, size (which shows the current number of elements in the array), capacity (which shows the maximum capacity of an array), and the element of the integer type that needs to be inserted. First, we check if size is smaller than capacity, and then we add the element into the array and increment size.

• Lines 15–16: We create an array A of capacity 15 and initialize it with only 10 elements. We then create two variables, size and capacity, and initialize them with the values 10 and 15, respectively.

• Lines 17–22: We call the addElement() function to add the elements to the array A.

By separating the size and capacity parameters, functions can operate on arrays without considering unnecessary elements, improving their performance. This approach also provides flexibility for arrays to grow dynamically without needing to redefine a larger-sized array from scratch.

Is the array with the size and capacity variables the ultimate solution? Or are there more advanced techniques available to enhance the flexibility and efficiency of array structures?

 Limitations of the array

As we encounter scenarios where the array reaches its maximum capacity, we need to devise effective solutions to manage this situation. Simply increasing the capacity to an excessively large value may seem like a quick fix, but it leads to unnecessary memory waste when multiple arrays are involved.

If each array is not fully occupied, a significant amount of memory remains unused. To optimize memory usage, we require a more efficient approach that can dynamically allocate memory based on the actual needs of each array. We’ll explore alternative techniques that overcome the limitations of the array, ensuring efficient memory utilization.