Arrays, Pointer Arithmetic, and C-Style Strings
Participation
Loading...

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

Arrays, Pointer Arithmetic, and C-Style Strings

So far, we've covered a lot of the fundamental tools C++ gives us, as well as some general principles of good programming design, in particular including the design of Abstract Data Types (ADTs).

We'll now look at various containers, which allow us to store and organize collections of other objects, and the underlying data structures we can use to implement them efficiently. You could think of this as the entry into the second half of "EECS 280: Programming and Introductory Data Structures" (although we'll come back to some more programming techniques later).

Consider std::vector, which we've used extensively so far. How would we implement our own vector-like container? Given the operations we'd like (e.g. indexing, push_back(), etc.), how should the internal memory for each element be arranged? How do we ensure that performance doesn't degrade unacceptably as the number of elements in the vector increases? These are the kinds of questions we'll consider in the next several lectures.

For today, we'll consider one of the fundamental approaches to representing a sequential container in memory - to simply store elements next to each other in memory within a large, 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, so we'll cover that too.

Updated Winter 2025
1: Introduction to Arrays
1.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…


1.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.


2: Arrays, Pointers, and Pointer Arithmetic
2.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.

2.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:

3: Pointer Comparison Operators
3.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).

3.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…


4: Traversal by Pointer
4.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.
4.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:

5: Array Parameters and Functions
5.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.

5.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:

6: C-Style Strings
6.1 Not Started

Let's take a quick look at a direct application of arrays - as the starting point for most reasonable representations of strings and/or text data. In particular, the low-level abstraction of an array of char is the primary representation for strings in the original C language.


6.1

Which of the following are true?
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.