WEBVTT 00:00:00.640 --> 00:00:04.610 In essence, a multidimensional array is just an array in 00:00:04.610 --> 00:00:07.660 which every element is another array. 00:00:08.039 --> 00:00:11.180 What do you think would happen if I wanted to access the second 00:00:11.180 --> 00:00:16.040 element of this 2D array? Since this is array of arrays, I should 00:00:16.040 --> 00:00:18.440 get back the second nested array. 00:00:18.450 --> 00:00:23.650 In this situation, we could say a second column. And then we can use another 00:00:23.650 --> 00:00:27.350 set of brackets to get the element from that nested array. 00:00:28.140 --> 00:00:31.160 So how could we replicate this on the heap? 00:00:31.540 --> 00:00:35.350 Let's say that we want to make a dynamic two‑dimensional array. 00:00:35.740 --> 00:00:39.940 Every dimension will be taken from the terminal at runtime, so I will 00:00:39.940 --> 00:00:43.150 change this code a little bit to reflect that requirement. 00:00:43.540 --> 00:00:46.810 We know how to allocate an array of integers on the heap. 00:00:46.820 --> 00:00:51.430 We can just use the special new keyword for creating arrays. But now 00:00:51.430 --> 00:00:53.950 I want to have an array which is two dimensional, 00:00:53.960 --> 00:00:56.760 which is an array of arrays. 00:00:57.240 --> 00:01:01.280 We know that an array name works similar to a pointer, so an 00:01:01.280 --> 00:01:05.730 array of arrays would be an array made up of elements where each 00:01:05.730 --> 00:01:08.250 one of them points to another array. 00:01:09.240 --> 00:01:13.650 In other words, first, we need to make an array of pointers to integers. 00:01:14.140 --> 00:01:18.430 And since this pointer should capture the first element from the array, 00:01:18.440 --> 00:01:21.850 I need to add another asterisk to its declaration. 00:01:22.240 --> 00:01:27.670 We didn't use this syntax yet, but this is a pointer to a pointer. In this case, 00:01:27.680 --> 00:01:32.050 a pointer that points to a pointer, which points to an integer. 00:01:32.440 --> 00:01:36.640 The difference is important because if this was just a pointer to an integer, 00:01:36.640 --> 00:01:40.260 then the compiler would think that this pointer points to the first byte 00:01:40.270 --> 00:01:44.160 of a 4‑byte sequence, which makes an integer value. 00:01:44.440 --> 00:01:46.990 However, since this is an array of pointers, 00:01:47.000 --> 00:01:51.220 our pointer actually points to the first byte of an 8‑byte sequence 00:01:51.230 --> 00:01:54.660 because on my computer a pointer needs 8 bytes. 00:01:55.340 --> 00:02:00.410 This allocated array represents one dimension, in this case, a number 00:02:00.410 --> 00:02:05.070 of rows. But this is just an array of pointers. 00:02:05.080 --> 00:02:09.389 Each one of these pointers need to point to another array, which 00:02:09.389 --> 00:02:12.360 will hold numbers from each column of the table. 00:02:12.740 --> 00:02:14.510 We need to do this manually now, 00:02:14.520 --> 00:02:17.770 so let's create a for loop which will allocate a new array 00:02:17.770 --> 00:02:21.180 on the heap and store its address inside of the pointer 00:02:21.180 --> 00:02:23.150 element from the first array. 00:02:23.540 --> 00:02:25.580 Once we do this, we are done. 00:02:25.590 --> 00:02:27.960 Now we can use this pointer to a pointer, 00:02:27.960 --> 00:02:33.370 just like a name for a 2D array. I can prove this by compiling the same 00:02:33.370 --> 00:02:36.460 code for printing the table from the previous lesson. 00:02:37.140 --> 00:02:39.450 As you can see, it still works. 00:02:40.940 --> 00:02:46.250 So how come this syntax with two square brackets still works? Well, 00:02:46.250 --> 00:02:48.760 we can write this expression in a different way. 00:02:49.940 --> 00:02:53.670 This is how it would look like if we used the dereference operator 00:02:53.680 --> 00:02:58.190 instead of square brackets. First, we need to dereference the first 00:02:58.190 --> 00:03:00.790 dimension with the required offset. 00:03:00.800 --> 00:03:04.390 This will give us one of the elements from the first array, and that 00:03:04.400 --> 00:03:08.960 element is a pointer to a first integer from one of the nested 00:03:08.960 --> 00:03:14.020 arrays. Then we can add an offset to that first address to get the 00:03:14.020 --> 00:03:18.140 required column from the nested array, and this would get us back the 00:03:18.140 --> 00:03:19.750 number from the matrix. 00:03:20.140 --> 00:03:21.890 Even though this approach works, 00:03:21.900 --> 00:03:26.160 I would advise you against creating multidimensional arrays like this. 00:03:26.540 --> 00:03:30.560 Aside from the fact that it looks messy and weird to allocate each 00:03:30.560 --> 00:03:34.660 dimension explicitly, it is also really bad for performance. 00:03:35.040 --> 00:03:39.570 Imagine what happens in memory when we execute this code. First, we need to 00:03:39.570 --> 00:03:43.660 allocate space for this pointer to a pointer, which is 8 bytes. 00:03:44.840 --> 00:03:48.100 Then we allocate based on the heap for an array of 00:03:48.110 --> 00:03:50.960 two pointers, which is 16 bytes. 00:03:52.140 --> 00:03:55.240 And after that, for each one of these elements, we need to 00:03:55.240 --> 00:03:57.550 allocate another subarray on the heap. 00:03:57.560 --> 00:04:01.500 In this case, this is 2 subarrays with 3 integers, 00:04:01.500 --> 00:04:04.650 so we need 24 bytes for all of them. 00:04:05.540 --> 00:04:10.260 So this is 48 bytes in total, and all of these subarrays are 00:04:10.260 --> 00:04:14.720 scattered throughout the heap because we used new operator to 00:04:14.720 --> 00:04:17.959 allocate space for each one of them specifically. 00:04:18.339 --> 00:04:22.610 And when you want to access one of these numbers from the matrix, first, we 00:04:22.610 --> 00:04:27.000 need to find the required pointer inside of the main array and then follow the 00:04:27.000 --> 00:04:31.690 address from that pointer to find the correct subarray, and only then we can 00:04:31.690 --> 00:04:34.150 find the right element in that subarray. 00:04:34.940 --> 00:04:39.260 So this multidimensional array is placed all over the heap. 00:04:40.240 --> 00:04:42.550 When we create a static array on the stack, 00:04:42.560 --> 00:04:46.190 we only need enough storage to hold all of the elements. In 00:04:46.190 --> 00:04:50.350 this case, this would be six integers, so 24 bytes. 00:04:50.940 --> 00:04:54.260 This is half of the amount of memory we needed to store the same 00:04:54.260 --> 00:04:58.070 array on the heap, and this static array also places all of these 00:04:58.070 --> 00:05:03.260 integers next to each other in memory, which is always better for performance. 00:05:04.140 --> 00:05:07.880 Even though we said that an array name works kind of like a pointer to 00:05:07.880 --> 00:05:11.510 the first element of the array, we have proven that there are 00:05:11.510 --> 00:05:15.150 differences between a real pointer and in array name. 00:05:15.540 --> 00:05:17.380 Aside from everything we already covered, 00:05:17.540 --> 00:05:21.470 I didn't explicitly explained that the compiler actually works its magic 00:05:21.470 --> 00:05:25.280 with the array names to get us exactly what we need without actually 00:05:25.280 --> 00:05:28.680 storing this in some kind of a pointer variable. 00:05:28.690 --> 00:05:33.450 Unlike regular variables, array names don't have a place in memory. 00:05:33.540 --> 00:05:38.850 Only the array elements need space. Array name just exists in the code. 00:05:39.240 --> 00:05:41.850 So when we have 2D arrays on the stack, 00:05:41.860 --> 00:05:45.580 all of these subarrays are also managed by the compiler magic. 00:05:45.590 --> 00:05:48.750 We don't actually need a pointer for each subarray. 00:05:49.140 --> 00:05:51.200 When you try to access the first subarray, 00:05:51.200 --> 00:05:54.430 compiler will know what you're trying to do and what 00:05:54.430 --> 00:05:56.760 location in memory it needs to check. 00:05:57.140 --> 00:06:00.530 That's why I said that using this syntax is the same as using a 00:06:00.530 --> 00:06:04.450 mathematical formula from the previous lesson, because you don't need 00:06:04.450 --> 00:06:08.610 any additional space or computing power. Compiler will take care of 00:06:08.610 --> 00:06:11.060 this before the actual compilation. 00:06:11.940 --> 00:06:14.980 So if you need to have dynamic arrays on the heap, 00:06:14.990 --> 00:06:18.920 the best solution would be to actually use the mathematical formula we talked 00:06:18.920 --> 00:06:22.950 about and allocate space in a single, one‑dimensional array. 00:06:23.340 --> 00:06:26.230 You can get the total number of elements by multiplying the 00:06:26.230 --> 00:06:29.430 number of rows and columns, and then you can use the 00:06:29.430 --> 00:06:31.950 formula to access these elements. 00:06:32.340 --> 00:06:37.310 We will still need additional 8 bytes to store this pointer to an array, but we 00:06:37.310 --> 00:06:41.640 need it to access the heap, and this is a small price to pay compared to how 00:06:41.640 --> 00:06:44.660 much space we needed for the previous implementation. 00:06:45.640 --> 00:06:48.980 Also, now we have all of the elements placed in a 00:06:48.980 --> 00:06:51.060 single block of memory on the heap. 00:06:51.740 --> 00:06:52.750 In my opinion, 00:06:52.760 --> 00:06:55.920 this is the best way to implement an array on the heap if 00:06:55.930 --> 00:06:58.360 all of its dimensions need to be dynamic.