An array stores data in blocks of sequential memory. We'll denote an array visually by a large rectangle with many smaller rectangles inside. On the leftmost side, we'll have index zero, which is the first element of the array, and every element that follows we'll have an index increases by one. This entire array is placing one sequential block of memory, so that as soon as one element ends, the next element begins. Let's look a couple of examples. An example of an array that has the first 10 prime numbers, is this first array right here. You'll see an index zero, we have the very first prime number two, and immediately following this memory, we have the next prime number three, followed by five, then seven. Arrays aren't limited to just having integers, here's an array that contains eight characters. Let's see a C++ program that contains a basic array. In C++, here's the syntax to create an array of a fixed size of values. We see the type of this array is integer and it's going to contain 10 integers, here are the first 10 prime numbers. We can access each element of the array using square braces. So here, values at three is going to access the third index in the array. Remember, indices start counting from zero, so, zero, one, two, three, and the third element is number seven, we expect this program to output seven. Let's see what happens when we run arrays example one. Moving into the arrays directory, and moving into example one, running make, we can see we've already made it, so I'm going to make clean just to really remake it, and run dot slash main, and here we see the output is seven, awesome. So, this exactly what we expect, we expect the third element or the third index in our array to be the value seven. Arrays have a few limitations. The first limitation is, all data stored in the array must be of the same type. An integer array can only contain integers, a character array can only contain characters, a cube array can only contain cubes. Because we know two facts about arrays, we know that all arrays are the same type, and we will know that all of a certain type is the same size. So, we know the size of a type and we know all of the elements are the same type. Knowing both of these things, we can calculate a given offset from any fixed starting point of the array. For example, if we look at this array, we know this array of integers, and if we want to know where index five is located at, what we know it's one, two, three, four, five integers past the start of the array. If we look at another array, consider a cube array, we can use a size of operator in C++ to ask the compiler to tell us how big a cube is. So, size of cube is going to return what the size in memory it takes to store a cube, in terms of number of bytes. So, if we find out that each cube is eight bytes long, then we can actually calculate what the offset is to index three. Index three being right here, we know that it takes us three cubes to reach index three, so three times eight bytes, means we have to advance 24 bytes from the beginning of the array to access the third index. This is really powerful, because we can use a simple equation to access the exact memory location we need to go to. Instead of having to jump to the millionth element by looking at each element in between, we know we want to look at the millionth index, we do a million times the size of the data. This is a really fast operation and we're going to contrast this against other data types as we explore those. Let's build a C++ program that actually shows off the size of operator, as well as showing off the memory address. Here's example two. We see we have the same array of prime numbers, and the first thing I'm going output is the size of an integer. So, we want to know how much memory does it take to store an integer on your computer. Computers are either going to take four or eight bytes to store an integer, and that's going to largely depend on what kind of system you're on and other compiler settings. If that takes four bytes, then we're going to see four bytes printed out here, and then we're going to go ahead and calculate the offset by looking at the memory address where index two is stored, minus the memory address where index zero is stored. We're going to look at how much memory is between index two and index zero. So, thinking about what we expect, is if we expect the size off to be four, then the difference between index zero, index two is going to be two integers or four times two. So, if this number is four, I expect the output of the offset to be eight. Let's go ahead and run this program and see what happens. I'm going to clear the screen, move into example two, and run make, then run dot slash main. The first number we see here corresponded to the size of an integer. So, the integer on the system is four bytes large. The second number is the distance between the index two of the array and index zero of the array, it's eight bytes, exactly what we expect. So, we know they exist sequentially in memory. Let's look at another example. Here in example three, we have three cubes, cube 11, cubed 42, and cube 100. We can now print out the size of a cube. When I ran this program earlier, I found out that my cube was eight bytes large. So, storing cube in memory takes exactly twice as much memory as storing integer, and I can do the same calculation, how far away is the cube at index two from the cube at index zero? Here we have eight byte blocks of memory. So, when we have two cubes, they each take eight bytes, we'll see that we have to travel 16 bytes to access the second element. So, what that means is, even though we see the exact same syntax, this line of code did not change whatsoever, but because the contents and type of our array is different, it's going to advance by different offsets. So, what we expect to see, is the first line to be eight and the second line to be 16 bytes, different values because we have a cube array, instead of an integer array. Let's go to console and see if that works out. Moving into the example three directory, running make, and running dot slash main. Here we see, when we run main, the numbers eight and 16, this is exactly what we thought we'd see, awesome. Let's explore another limitation of an array. A second limitation of array, is that an array has to have a fixed capacity. So, an array must sequentially store data in memory, and the capacity of the array is the maximum number of elements that can be stored sequentially in that piece of memory. So the size of the array is the current number of elements in the array, while the capacity is the maximum number of elements that can exist. Once we exceed the maximum number of elements in the array, we have to resize the array to allow us to have more memory. Remember, we can't just have an infinite amount of sequential memory, because we're going to have other things in memory. So, we got to find a block large enough to store all of the elements we care about in the array, and we're going to request the block that's only large enough to store the data we care about right now. As your array grows, we'll resize it, but as part of resizing, we have to allocate a new chunk of memory. When we do allocate a new chunk of memory, we may need to copy the data over. So if the old location has 10 elements here and we want to add an 11th prime number, then we have to copy over all of the original elements. Only then, when we want to write another prime number, 29, can we do that, once we have space here at the end of the array? Until we have that space, if we wrote to the end of the array, we're writing in someone else's memory. We saw earlier the standard vector, and the standard vector is something in the standard template library that implements an array as a dynamically growing array. What that means is, that internal to the vector, when the vector's capacity reaches the size of the array and it needs to add another element, it has to go about resizing itself. So, all of the things you just saw is true about a vector, the vector has a fixed size, the vector has a fixed capacity. Whenever the size reaches the capacity, then we have to expand the vector. Let's look at a very last example that really dives into how a vector works, and really see that it is exactly the same thing as an array. So, similar to example three, I have an array of three cubes, but instead of having a native C++ array, I have a vector. The initial capacity of the vector is going to be outputted in cubes of capacity. This tells me how many elements can be stored at maximum in my vector. I'm going to add another element, then I'm going to say size after adding. So, we expect the size to be four, because the initial size was three, and then we're going to look at the new capacity. So, it's very likely that the initial capacity of this array will be three. The new capacity of this array inside the vector is likely going to be larger than three and in fact larger than four, because we really want to make sure we have enough room to add again. So, I'm going to expect the capacity after adding to be about double the original capacity, and we'll explore why that is in a future video. So, we expect that to grow from three to about six, and we'll see what happens in just a moment. We can do the exact same thing we did before and see what is the memory address of cube is zero and what is the memory address of cube is at two, two and zero? We can find out what the memory separation is, or the offset between those two things,. Since we know every cube is eight bytes long, we expect the separation to be 16 if they really are stored sequentially in memory. Then finally, we can actually search through the array to find out where in a cube is that. So, if we want to find cube 400, we can go ahead and go through the array using a four loop to say, "Hey, I want to find where my cube is at a particular index." So we're looking for cube of 400 and we're searching for cube of 400 by going through the array one element at a time. Let's run this program and see all of this work together. Go into the example for directory, running make, and then running dot slash main. We see the initial capacity of our cube array that had three elements, is three. We then add an element and the size after adding is four, and as we predicted, the capacity after adding is going to be larger than the size, so it exactly doubled the capacity of the array. We find the memory separation between index two and index zero, two cubes wide is 16 bytes. So, indeed, the cubes are being stored sequentially in memory. Finally, we found the target at two, so it's to show that we can successfully use a four loop to find a particular index inside of an array. So, at this point, you understand the basics of arrays. We're going to contrast this against another form of storage called a linked list or linked memory, and then explore why we might use one or the other. I'll see you then.
