CS 70

Arrays, Our First Data Structure!

We've arrived at our first CS 70 data structure: the simple, often underappreciated array.

You probably already have experience with arrays from working with them in Java.

  • Duck speaking

    Yes, I totally know Java. So C++ will be just the same?

  • LHS Cow speaking

    There are many similarities, but also significant differences in what you need to write to express similar ideas. Often prior Java knowledge will lead you astray, so be on the look out for differences.

  • Duck speaking

    I've also used Python arrays!

  • Python speaking

    Actually, I think you're thinking of Python's “list” data structure. It does have many array-like properties, but it's similar to Java's ArrayList class rather than basic Java arrays.

Properties of Arrays

You've seen arrays in other classes. What would you say are the fundamental properties of arrays as a data structure?

Fundamental Properties of (Primitive) Arrays

An array is contiguous, ordered, homogeneous, fixed-size storage. Let's break that down:

  • Contiguous: The items in the array are all together in memory with no gaps.
  • Ordered: The elements in an array have a clear order to them. We know which one is “first” and which one is “forty-second”.
  • Homogeneous: The elements of an array all have to be the same type.
  • Fixed Size: Once we create an array, we can't change the number of things it can hold.

The fact that all the elements of an array are the same type, coupled with the fact that each type takes a fixed amount of memory and the fact that arrays are contiguous in memory, means that the machine can determine exactly where in memory any element is located very quickly.

  • Goat speaking

    Sure, okay. Do I need to remember these properties?

  • LHS Cow speaking

    Actually, yes. We'll put it on a test at some point, because Learning Goal 2A is “List and define the four fundamental properties of C++'s (primitive) arrays”—these exact properties.

  • Hedgehog speaking

    Hmm, how am I going to commit these words to memory?

  • Duck speaking

    Well, we could try a mnemonic, like “Cats Often Hide Fish” to remember “Contiguous, Ordered, Homogeneous, Fixed size”, and maybe imagine all the fish swimming in a row with a number on each one. They could be COHo Fish too to all be the same kind and keep the mnemonic.

  • Cat speaking

    Hmm. I think I'll just think of an egg carton from the store. It's a fixed size, for a dozen eggs, they're all next to each other, they're all the same kind of thing, and I can start at one end and work my way through in order.

  • LHS Cow speaking

    Whatever works!

What strategy will you use to remember the four fundamental properties of arrays?

Why Are Arrays Underappreciated?

There will be very few times when a fixed-size array will be the right data structure for a big program. On Homework 4, we'll learn about std::vector, which can do everything an array can do without the fixed-size restriction.

  • Duck speaking

    So why take the time to learn about arrays?

  • LHS Cow speaking

    Arrays are the fundamental building block of lots of other, fancier, data structures—including std::vector.

  • RHS Cow speaking

    Understanding arrays will help us understand what's going on in memory when we use (and build) other data structures.

(When logged in, completion status appears here.)