Arrays and Pointer Arithmetic
Participation
Loading...

Export your exercise answers to use with another computer or browser.

Arrays and Pointer Arithmetic

One of the fundamental approaches to implementing a data structure is to store elements next to each other in memory within a contiguous allocation. In C++, an array (not to be confused with std::array from the C++ standard library), provides a low-level abstraction over a sequence of objects stored within a larger block of memory. It's customary to work with arrays via pointers, including by using pointer arithmetic to compute addresses of individual elements.

We'll also introduce the notion of time complexity to formally analyze the efficiency of operations on data structures.

It turns out that arrays (and data structures built using them) provide very efficient access to data in a couple different ways:

  • Sequential Access: Iterating through a sequence of elements from start to end.

  • Random Access: Accessing an element at a particular index (i.e. position) in the sequence.

Updated Fall 2024
1: Time Complexity

As we're asessing the fitness of a data structure for a given task, it's helpful to determine its time complexity, which quantifies how well it performs as the size of the data we're working with scales up.

2: Introduction to Arrays
2.1 Not Started

Arrays are a low-level abstraction over a sequence of objects in memory that we can fit into the memory model we've been building up so far…


2.1 Exercise: Introduction to Arrays

Determine whether each of the following statements are true or false.

Arrays can be resized if you need more space.

The elements in an array are stored contiguously in memory.

All elements in a particular array must be the same type.

All individual array elements must be the same size in memory.

Each array element lives at the same address in memory.

Sample solution…

Arrays can be resized if you need more space.

The elements in an array are stored contiguously in memory.

All elements in a particular array must be the same type.

All individual array elements must be the same size in memory.

Each array element lives at the same address in memory.


3: Arrays, Pointers, and Pointer Arithmetic
3.1 Not Started

Because an array is essentially just a sequence of objects (one for each element in the array) that are laid out contiguously in memory, we can leverage pointers (i.e. addresses) to work with arrays. Here's one example, informally:


Let's recap the fundamental arithmetic operations with pointers. Assume ptr1 and ptr2 are pointers and that x is an integer.

  1. Pointer Offset. For example, ptr1 + x. This computes a new address, offset x "spaces" in memory past the original ptr1. The size of a "space" depends on the type that ptr1 was pointing to.

  2. Pointer Difference. For example, ptr2 - ptr1. This computes the number of spaces between the two addresses in memory.

Note that in both cases, we don't have to worry about how many bytes are involved - the compiler takes care of that behind the scenes based on the pointer types. We can think about offsets and differences in terms of the sequences of whole objects in memory.

Finally, and perhaps one of the biggest takeaways here, indexing in arrays with the [] operator is a O(1) - constant time operation, because it's equivalent to a single pointer offset operation followed by a single dereference operation. We can just compute the address of an element and effectively jump there, regardless of how large the array is.

3.1 Exercise: Pointer Arithmetic

Trace this code and draw a memory diagram as you go. Once you're finished, use your diagram to answer the question below. You could also run the lobster simulation to check your work.

What values are printed for each of the expressions sent to cout at the end of the program? If the expression results in undefined behavior, write "undefined".

     *a     *(a + 2)              a - d

b - c            b[2]     *(arr + 5)

Sample solution…

     *a     *(a + 2)              a - d

b - c            b[2]     *(arr + 5)

You're welcome to check your solution with this walkthrough video:

4: Pointer Comparison Operators
4.1 Not Started

Just like we can do arithmetic with pointers by considering offsets and distances between locations in memory, we can also understand pointer comparisons naturally in terms of addresses.


So, basically, ptr1 < ptr2 will be true if and only if ptr1 points to an address that is numerically lower than the address ptr2 points to. Or, put another way, if ptr1 is pointing somewhere before ptr2 in memory. The rest of the comparison operators (>, <=, >=) work analogously.

It's also worth noting the equality operators == and != test whether two pointers are pointing to the same object (by checking if they hold the same address and are pointing to the same place).

4.1 Exercise: Pointer Comparison

Given an array and some pointers:

int main() {
  int arr[5] = { 5, 4, 3, 2, 1 };
  int *ptr1 = arr + 2;
  int *ptr2 = arr + 3;
}

Determine whether each of the following expressions evaluates to true or false. Or, if the expression has undefined behavior, write "undefined".

ptr1 == ptr2

ptr1 == ptr2 - 1

ptr1 < ptr2

*ptr1 < *ptr2

ptr1 < arr + 5

Sample solution…

ptr1 == ptr2

ptr1 == ptr2 - 1

ptr1 < ptr2

*ptr1 < *ptr2

ptr1 < arr + 5

Why does the last expression yield a guaranteed true rather than undefined behavior? The key is that although arr + 5 computes the address (i.e. a pointer) of the space one-past-the-end of the array, it doesn't dereference it with * and try to access data stored there. It also turns out an expression like this is very useful - it tells us whether ptr1 is still in bounds or not, since it's checking to make sure it's less than the one-past-the-end address. We'll see this in action in the next section…


5: Traversal by Pointer
5.1 Not Started

There are two fundamental ways to approach sequential access of the elements in an array using a loop, which we might also call "traversal" or "iteration" through the array's elements:

  • Traversal by Index: Start an index variable (e.g. i) at 0, increase it by 1 on each iteration of the loop, and plug i into an indexing operation to find each element of the array.
  • Traversal by Pointer: Start a pointer (e.g. ptr) at the beginning of an array, move it forward one space in memory on each iteration, and dereference it along the way to visit each element of the array.


Neither traversal by pointer nor traversal by index is fundamentally better or more efficient for arrays. You might hear someone say that traversal by index is slower, but this is generally not true given that modern compilers can optimize both approaches into the same machine code. You should use the one that feels more natural to you or that matches the generally accepted pattern for the code you're writing. In most cases, that's probably traversal by index.

However, we're taking a look at traversal by pointer now because:

  1. It's another interesting thing you can do with pointers.
  2. It is customarily used in certain contexts, like with C-style strings, which we'll look at in a future lecture.
  3. It's conceptually similar to traversal by iterator, which we'll learn about later on in the course.
5.1 Exercise: Traversal By Pointer

Which of the following code snippets correctly implement traversal by pointer? For each, indicate whether it is correct or has a bug. If it has a bug, describe what's wrong. Is it a compile error or a runtime error? How would you fix it?

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

for(int *ptr = 0; ptr < 5; ++ptr) {
  cout << *ptr << endl;
}

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

for(int *ptr = arr; ptr < arr + 5; ++ptr) {
  cout << ptr << endl;
}

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

for(int *ptr = arr; ptr < ptr + 5; ++ptr) {
  cout << *ptr << endl;
}

Surprise! Each of the code snippets above contains at least one mistake. If you didn't find this, double check the ones you marked as correct, or take a look this walkthrough video:

6: Array Parameters and Functions
6.1 Not Started

When working with arrays, it's often helpful to write helper functions that process the arrays in some way, perhaps using a loop to iterate through each element and perform some operation.

An example of this would be a function that prints out an array…


Two big takeaways here:

  1. The compiler turns array parameters into pass-by-pointer behind the scenes. That gives us a pointer we can use to access the original array. This is similar to pass-by-reference, but technically different.

  2. Because of this, the only thing passed into an array function is a pointer to the first element. That means we have to pass the size of the original array as a separate parameter.

6.1 Exercise: Pass-by-Pointer

Write a function called maxValue that uses traversal-by-pointer to find the value of the maximum element in an array.

You're welcome to check your solution with this walkthrough video:
You've reached the end of this lecture! Your work on any exercises will be saved if you re-open this page in the same web browser.

Participation Credit
Make sure to sign in to the page, complete each of the exercises, and double check the participation indicator at the top left of this page to ensure you've earned credit.