[MUSIC]. We've seen multidimensional arrays now, at least two dimensions, but things extend, in the same way to three dimensions and four and more dimensions. what I want to do now is introduce you to a multi-level arrays which are a little bit different. They try to do some similar things but in a very different way using pointers rather than a continuous allocation in memory. Lets take a look at the multi-level array. Here I'm showing three one-dimensional array. That we've that we declared are zip digit arrays. one for each zip code of five digits each, okay? One-dimensional arrays we're now going to declare a multi-level array called a univ that is actually an array of pointers to integers. You notice the star there in front of it and it's going to have this number of elements in this case set 23 and the three elements will be our three one-dimensional arrays from above. And you'll see that that looks like it should be a two-dimensional array, right? We've just organized three zip codes into an array of three elements. each element having five digits. But is this a two-dimensional array? well it's not. It's a little bit different. and the reason it's different is because they, the the three a, the three sub arrays do not have to be continuous in memory. and they don't have to be in row major order like we had before. In this case, you'll notice that the three arrays have been allocated to three different locations in memory. Separately, each one of them in isolation they were declared as separate arrays initially. Then our array univ has three pointers in it it's an array of pointers after all and these were point to those the beginning of each of those three one dimensional arrays. But [INAUDIBLE] not in any set order. It doesn't expect them to be in a particular arrangement in memory. This turns out to be also the way Java represents arrays all the time. It does not have really multi dimensional arrays, it only has multi-level arrays, involving pointers like this. Although, this is made invisible in the language, but this is what's going on underneath. Okay, so our array univ has three elements, each one of them is a pointer that's 4 bytes long and of course, it's a one-dimensional array of pointers. So, they're represented one after the other, in memory, each one of them points to an integer basically the starting integer of the three one-dimensional arrays that we have. So let's take a look at how access works to this. So, here we're going to have the same procedure we had before for getting a digit of the zip code only this time you'll notice, although we address it, it looks the same, let's see what actual assembly code gets generated, okay? So see at the beginning, we'll have our first index in the register ECX. And we're going to multiply that by four and put the result in EDX. And why are we multiplying it by four? Well, because we're indexing into our univ array and we need to know how much of an offset to have to get the right pointer. Once we have that pointer, you'll notice we will use that, to get that pointer we will use that offset we've just computed added to the starting address of the array, and then access that memory location. Ac, this is actually reading that memory location, getting the pointer, and putting it into EDX. Okay, so we've done one memory access already into the univ array to get the right pointer. Once we have the pointer, we're going to, use that as an offset to four times the other parameter, the other argument to this function, the index of the digit, okay? And the four there is because of course we're doing integers and they're four byes each so we're computing the address along the one dimensional, the offset in the one dimensional array, adding that to the starting address of the one dimensional array that we just got from the univ array. So, that gives us a second memory access, we're now going to that memory location and actually reading the digit. So, the important thing to understand here is that in this case we must do two memory reads. First to get the address to the row, the pointer to the row and then access within that row. In the multidimensional case, we could do that in one address computation because we had the guarantee that each row followed one after the other. Okay, so, the access does look similar in the C code okay, in fact they look identical, but in reality because of the different structure, here a continous arrangement in row major order. And here first the level of pointers that get us to the start of the row. And then a one-dimensional array. this requires only one memory access. we can do, compute the entire address in one expression. here we have to do it in two parts. First, to get the pointer and then to add on the offset and access again. So two memory accesses. So these arrays are a little bit more expensive in performance because we have to do those two memory accesses rather than one. Okay let's complete this video the same way we did the previous one. With some examples of accesses. so let's go to univ two, three. the address computation here, you'll notice is first to get the the starting address of the third element of the univ array. That would be the 56, that address is the UCB zip code. And then the offset within that, four times the second index of three. So that gives us an address of 68 which in fact yields the fourth digit of that zip code, or the number two. And that is absolutely guaranteed to always be the right answer, because we're, we're doing the right thing here. Let's look at a case where we use an index that's a little off this one, five. Okay, in this case the same address computation is done. this time we yield an address of 36. which is a not part of the one-dimensional array we were really going after. We were going after the second element of the univ array which should have been to the start of the CMU array, and then because we have an offset of five elements, we're going off the end of that array and we go to address 36 out here. Turns out by pure coincidence, that is the first address of the UW zip code array, but that is a pure coincidence. It just happened to be that way the UW array could've been somewhere else in memory. And then, wouldn't have had any idea what value would've come up here. In this case, we do get the nine, but there's absolutely no guarantee that that will be the case if we run our program again, because we might end up in a different that UW array might end up in a different part of memory. Okay let's do that 2 minus 1 example next. Again, the same address computation. We go to address 52, but that is outside of the element we were really trying to address. And again, it's only working out by coincidence that we get the 5. no guarantee at all that that would be consistently that value. Similarly for this one, we're even going outside of the university array to the next element where the next element would be. but who knows what's there and what address we'll be reading. That will take us to some random part of memory. We'll then go 4 bytes before that, because of the minus 1. And who knows what's there even. so we have no idea what address it is, we have no idea what value is there, of course. and no guarantee that anything will ever be consistent in this case. for the last one here 1, 12 the same address computation yields a seven. just because of pure coincidence that there happened to be something there, but again those arrays could've been shuffled around, so no guarantee on that either. Remember again the code doesn't do any bounds checking C doesn't do that. We'll see later that Java does and will actually give us a warning that we're accessing out of bounds that's a very useful thing. At an added cost of an extra check every time. C doesn't bother with that extra check, just does the address computation. Alright, so the add, the location of each lower level array in memory is not guaranteed in this case. In the previous multidimensional case, we had a guarantee because of row major ordering in memory. and this time we do not. All we know is that there's a first set of of pointers, and then we follow the pointer to the one-dimensional array. no guarantee of how those will end up in memory. Alright, to do a little bit of a summarization of arrays in C then is arrays themselves are a contiguous allocation in memory. there is no bounds checking. we can usually treat the array like the array name like a pointer to the first element. And then elements are offset from that start of the array. multidimensional arrays are continuous in memory and in row major order. multi-level arrays, these ones we've just been discussing, are not contiguous, not contiguous, and pointers are used between levels, so we have many less guarantees about how things are arranged.