Hope you guys enjoyed the video! Just a quick note: the code that I wrote at 16:47 should really be *a2d[y][x] = 2;* since we want the inner loop to iterate through the actual int array data. Don't forget to drop a comment below if something still confuses you about multidimensional arrays, and have a nice day!
Also I see allot of questions about using stack allocated arrays for multidimensional arrays and them being consecutive memory, might want to pin a comment explaining why this is, in general, a bad idea.
Thank you for your videos. If I create a 2D array/grid/matrix using STL vector e.g. std::vector a2d , will it suffer from the same performance penalty as the int** a2d?
Hey if I wanted to multiply a 2 dimensional array by a value like 10 that has 3 rows and 4 columns with initial values present in each location, why would I set the "setw(5)" with the 5 argument instead of a (4) argument in this manipulator function.
I have been programming for 24 years, and used C++ for 15 of them, I make all my money from making my own programs... But I have actually learnt a few really useful things by going back and checking everything against your videos. Turns out there is always more to learn, and I like your teaching style. Thanks.
i tried to sidestep the entire pointer confusion issue by using pointer arithmetic, kinda like you did in the latter half. people groan whenever its brought up, but once you get the basic idea down, you can write equations for any situation and just re-use the equations as necessary. much easier than keeping track of what level of pointer abstraction youre on, at least for me. plus it uses contiguous memory, so its fast and easy to work with. the equation i worked out is *(xAxis + xOffset * yAxis + yOffset), where xAxis is the variable name/reference. yAxis will vary based on use case, but this equation can be expanded to n-dimensions as necessary, and it really saved me headaches when making my rpg game in the terminal by using it for the screen buffer (yAxis in that case was the vertical draw size, or in other words the number of rows).
Hello, there is a possibilty to create 2D array and having data in one row, example below: int** AllocMatrix2D(size_t dim1, size_t dim2) { int** matrix2d = new int* [dim1]; int* dumm = new int[dim1 * dim2]; for (size_t i = 0; i < dim1; ++i) matrix2d[i] = dumm + i * dim2; return matrix2d; } void deleteMatrix2D(int**& matrix2d) { delete[] matrix2d[0]; delete[] matrix2d; matrix2d = 0;
4 ปีที่แล้ว
A lot easier to understand and much more intuitive doing this in Assembly language, where you're dealing with the raw pointers and direct memory structures all the time. C++, on these aspects at least, certainly does over-complicate what is a fairly simple concept. It might be easier to think in terms of pointers to pointer tables, where each pointer in that table points to the start of your array of actual data.
Hi, in the final example if you want to make it slightly more efficient you could pull the 'y*5' to outside the xloop to safe keep calculating it for every element
Well, there are actually much easier ways of handling multidimensional arrays. For Stack allocation of 10*10 array: int Mat[10][10]; For Heap allocation of 10*10 array: int (*Mat)[10] = new int[10][10]; // Declaring (*Mat)[10] means : Name Mat refers to (a pointer to (an int array of size 10)). // The brackets are needed in the declaration of (*Mat)[10]. The explanation has brackets to remove ambiguity from misinterpreted English. Mat[4][5] = 6; delete [] Mat; This kind of allocation is easy to handle. There is no memory fragmentation and is almost as good as 1D array. This also easily extends to higher dimensions: For Heap allocation of 10*10*10 array: int (*Mat)[10][10] = new int[10][10][10]; Mat[4][5][0] = 6; delete [] Mat; (I'm not too sure of the deletion part. So just verify it before using it for anything important.)
here is a simple explanation if u dont get it say the int* is a column, then int** are rows for each row there are gonna be 50 int* and int*** is height of a cube lets say , so for each unit of height there are gonna be 50 rows or 50 int** which have 50 int* so..get it now?
I love your videos Cherno. You're a great teacher. Just a minor suggestion. In your example of 3D arrays, you could have used x, y, and z as all different sizes (say 50, 40 and 30) so as to make things more clear to beginners. Just my 2 cents though :) And cheers again for these awesome videos which help even an experienced programmer like me. Thank you.
Write a c++ program that creates a char matrix ( 2D array) dimension then: User insert the dimension and the data of this array Search about one char taken by user if founded Replace it by another char taken by user if not founded , print not founded message. Print all data sorted.
thank you for your brilliant video! 👍 I have a question that storing 2-D data in a 1-D array involves one addition, one multiplication, and one addressing, while in a 2-D array it only involves addressing and potential cache missing. Will the later always be slower than the former? Thanks for reading my comment!
gods bless the holy malloc! int** a2d = (int**)malloc(50*50*sizeof(int)) and you have one continuous memory block that you can address as a2d[x][y] edit: nvm I'm misremembering the syntax. it works but not as I've written here. edit2: oh gods it's been way too long. the above does not work at all, it needs to be done slightly differently and I'm too stupid to figure out right now should be something like int** a2d = (int**) malloc(50*sizeof(int*)+50*sizeof(int)) then you gotta fill the first 50*sizeof(int*) with int* that are 50 * sizeof(int) apart... techanically trivial but my brain doesn't comply with my wants right now... #define ARRAY_X 15 #define ARRAY_Y 15 #define TYPE int #include #include int main(){ TYPE** a2d = (TYPE**) malloc(ARRAY_X*sizeof(TYPE*) + ARRAY_X*ARRAY_Y*sizeof(TYPE)); TYPE* firstaddr = (TYPE*)(a2d + ARRAY_X); memset(firstaddr, 0, ARRAY_X*ARRAY_Y*sizeof(TYPE)); for(int i=0; i
i dont think it's just 25 ints, Assuming 32bit PTR : 5x5 it would be 25+5(intptrs) = 30 ints (for 2D) and it will be 5x5x5(ints)+5x5(ptr to row)8 +5(ptr to plane) = 125+25+5 = 155 ints. basically for each dimension you pay with more memory X all the previous dimension count. this issue is not present in contiguous multi dim array, at most you might be using MxNxsizeof(member) + 2 x sizeof(index used). assuming you dont use stack to allocate your max index as aswell.
Or more simply: int x[1d][2d][3d]...[nd]. This creates an array of [n] dimensions. Of course, you'll never (I don't know, maybe), use more than [3] dimensions, that's so confusing. Well, I don't know that much about C++, because I don't make big projects (by the time I'm writing this, I'm 15), so I don't find pointers that useful right now.
Why aren´t you using std::array? Many times I have heard that std::array is more c++ style compared to "int* array = new int[]" with next to nothing in terms of overhead and many useful features normal C- Arrays don't have, like knowing it's own size and not instantly decaying to a pointer. I am grateful for an answer from you or anyone able and willing to explain :) Otherwise great video as always, thank you!
I have a question Multidimensional arrays look a lot cleaner when allocated or stack, like: int array[5][5][5]; are those ints allocated in memory "in a row"?
Even if you allocate in heap, like this: int (*array)[5][5] = new int[5][5][5]; The data is still stored consecutively. The point of Cherno's video is that he makes dynamic arrays, it's even possible to make non rectangular array -- triangular or other shapes. Personally, I would rather use boost::multi_array in most cases.
Sanyam Malhotra yeah ofc you can. But then you'd need to store the size of each array somewhere (in another array?) And loop through that for the size.
Can't we just use malloc to allocate contiguous memory of size x*y and then initialize our array[x][y] the same way (2 for loops)?? In this case we would have the advantage of the notation [x][y] while eliminating any possible performance issues.
How about a video showing how to store an 2d array of floats? I need to store a vga frame of distance float values. I am getting lost in the array type vs the pointer type not matching and that does not make sense to me.
How can I allocate an array partially? For example, I have a matrix with some non-zero elements (e.g., just diagonal), can I reduce the allocation to that essential elements without losing direct indexing? It means somehow I compact used memory without affecting the efficiency?
I think your explanation at 04:28 is a bit confusing: actually you are “creating” integers, 50 to be exact. And they are initialized: to whatever your memory has at that point, or possibly to 0 or some guard check value depending on the underlying malloc implementation. Just print out a value of said array and your program will output a value, instead of crashing :) Obviously they both take up 200 bytes of memory, assuming a 32 bit arch. But to say that creating an integer array and a pointer array are basically identical, is a bit misleading imo. And I think it would be confusing for new programmers. It’s only identical in term of allocated memory. Not in terms of functionality. And certainly not for the compiler. If I create a float it’s also taking up 4 bytes. But to say that float is identical to an integer, just because they both take up equal size, is stretching it a bit.
In the 2D pointer array case, can I simply do std::vector a2dPtrArray? using vector. does it sound like doing the same Job? If yes, would be there any kind of cache miss?(because std::vector suppose to have a contiguous memory)
//How about this approach? #define X_SIZE 50 #define Y_SIZE 50 int main(int argc, char** argv) { int** arr=new int*[Y_SIZE]; // This could even be on stack { // Allocate all the elements but dole them out int* temp = new int[X_SIZE * Y_SIZE]; for (int i = 0; i < Y_SIZE; ++i) { arr[i] = temp; temp += X_SIZE; //next sub array } } delete[] arr[0]; // This will clean up the lot delete[] arr; }
I need to write two arrays one that prints student name and the other that prints the student's grade. Should I be creatinga multidimensional array of or something else
Depends on how you want to store the grade. If grade is string, like "A-", "B+" etc, you could use a 2 dim array of strings, but that's not a very nice solution. I would create a struct to hold the name and grade, and then create an array of those structs.
This is WRONG. Array of pointers are NOT multidimensional arrays, they are different types, and have different memory typology. Arrays' memory are ALWAYS continuous. Arrays can decay into a pointer in some circumstances like argument passing and implicit conversion, but that only happens in the first dimension. We can confirm it with below codes: int a2d[2][3]; // this is a REAL 2D array int ** not_a2d = a2d; // won't compile! u have to use a cast forcefully int (*p2a)[3] = a2d; //compiles due to decays on implicit conversion Yes, as Cherno demonstrated later in this video, 1D arrays can simulate (need reinterpretation) multidimensional arrays just because arrays' memory are continuous.
Been coding in C++ for 4+ years now, don't really know why I'm watching these videos, but sometimes something new pops up. So even though I knew all of this, it was really nice to see you think about not only the intuitive way of doing something, but also the (most of the time) better way. Most people teaching C++ (or any language really) just looks at one approach, and it's usually the intuitive one not the better one. Really great video! Keep it up!
@@alt0v14 I don't know what the implementation of Java arrays is, they might already be doing it this way underneath, check the class implementation. This is the kind of reason why I think it is important for universities to teach a low level language first (mine does) rather than a higher level one like Python or Java, so that people know these tricks and that it may actually be what their higher level objects are really doing. There is a tradeoff to this method, you aren't jumping around in memory following pointers, but you are doing arithmetic calculations on every index. If you can guarantee memory contiguity with one of the other things he mentioned, then you actually might be better off bouncing through the pointers than doing the calculations.
I'm in a similar situation, but find the extra insight in these videos related to the "why" of doing something very beneficial. That is something that is overlooked in many other training presentations and is really key, I think, to making people better programmers; thinking through why they are writing code in a specific way rather than just copying and pasting something to try and get the job done.
You should have mentioned the much simpler stack declaration of such arrays: int a[n][n];. Also, if you want it heap allocated and don't want fragmentation, you could do int* a=new int[n*n]; int** m=new int*[n]; for(i=0;i
If anyone is curious about the time difference between allocating/deleting a 3d array versus a 3d flattened array of size 5x5x5. It's significant. Below are my bench mark times using the timing method learned from previous video: 3D ARRAY 0.0278ms 0.0164ms 0.011ms 0.0112ms Average: 0.0166ms 3D ARRAY FLATTENED 0.0015ms 0.0008ms 0.0025ms 0.0009ms Average: 0.001425 Optimization improvement by 11.65 times faster. WOW
Well, if you have 1000*1000*1000 array on which you do complex calculations later, allocation time is not that relevant. Saying that, what about addressing ? What is faster, get a value from 1D array (including index calculation) or 3D one ? Let us say, it is random access.
@@dmitripogosian5084 since the calculation is a couple of sums and a multiplication, I don't think is even noticeable, most likely is better to have it flattened to have less cache misses
@@gabrielbarrantes6946 Well, if the calculation sits in your inner most loop, the difference between one multiplications and two multiplications can be approaching factor of 2 for your program's runtime. But I agree that cache misses are more degrading most of the time
Love this video. Would love to see an in-depth video of writing a freelist/mempool that also takes into consideration dynamic allocation when the pool is empty and the optimisations around it.
I just did a search for this topic on your page the other day. I'm so glad to see it up !! I absolutely love your work and it's helped me understand c++ in a way I never thought possible. I'm self teaching so your work means a lot to me !! Thanks
Hristo Hristov yes they are but are, in general, a bad idea because they can be very large in memory and can cause a stack overflow later on in your code due to you using a large portion of the limited stack space available with the array.
But when the for loop reaches the last cycle, x and y are 4. So [ x + y * 5 ] is (4 + 4) * 5 = 40 -> so it must be out of bounds. Or is C calculating like this : 4 + (4 * 5)?
This was my first thought of how to create multi D arrays in C but I found on the Internet people making arrays like this int matrix[2][3]; Ans then you could write int (*ptr)[3] = matrix; Which is kind of an intuitive syntax because if you want to know what you get when you dereference ptr, just look at this expression without a star sign. Also, when I put a 2D array like this on the stack it gets put continously in the memory. If you write ptr[1][2] you will get an offset of (1 * 3 + 2) * sizeof(int) bytes (1*3 because every array has 3 elements). If this same ptr points at an address 100, ptr[4][2] will be at an address 100 + (4*3+2) * 4 = 100 + 56 = 156. That's the approach that I found on the Internet though, what cherno showed in this video was also natural to me as to how you would store multi D arrays. With, Cherno's approach, ptr would be declared like this int **ptr and taking this same example, ptr[4][2] would be at an address that is stored at an address 100 + 4*(sizeof(void*)) and then add 2*sizeof(int). Which means one more jumping through the memory than with the approach that I have mentioned beforehand.
Nobody ever said this to me but when you look at pointers, if you want to see what they are pointing to just remove a star. Double pointer has 2 stars, remove one and you get a pointer. Therefore a double pointer is pointing to a pointer. int (*ptr)[3] is pointing to an array of 3 ints, thus, when you dereference it, you will find 3 integers. Not an address, but an array of 3 integers. This also means that when you walk through memory by writing ptr+1 you will move 3*sizeof(int) bytes. On the other hand, if you have a double pointer, if you write doublePtr+1 you will travel sizeof(void*) bytes in memory.
As always, great video! Although I'm already familiar with most concepts you teach, I learned it all in other languages (mostly Java and C#), so they're a great way for me to get more familiar with C++ Regarding this particular video, I do feel like using a visual representation could work better for explaining multidimensional arrays - at least that has been my experience when teaching other people. Best of luck and keep up the excellent work!
Yup your both right, stack is always consecutive in the order you allocate that's why using the stack is always faster. However most arrays are heap allocated, especially multidimensional, since they can get very big very fast. So you want to use the heap to avoid stack overflow; of course if they are very small you should be fine on the stack.
@@nijucow You can request larger stack at program start if you know how big they will need to be. Edit: Not always of course, often the size initially allowed is the maximum, but it could also be smaller in the case of shared clusters.
indeed for my compiler under linux, it only works for memory allocated on the stack like I just did in this instance, doesn't work on the heap use "new" keyword.
I have to say college lectures teach some very bad but somewhat functional code hahaha, when am in class they never take time to teach us about memory and the stack at all and worse of all to my knowledge my current instructor has no real-world knowledge about modern use of C++ syntax, she completely lost the ball on the use of the switch statement and 2D arrays allocution within a for loop - pseudocode has helped me think better but can't only take you across the block, schools should understand that hahaha.
When you really need to have a 2d array, you could also create a 1d array first, that stores all the data, then create an array of pointers (the 2d array) that stores pointers to {data, data + width, data + 2*width,...}. Then you have a 2d array, which has all its data in one spot. Its a bit tricky to delete it, because you just have to delete the data array and the pointer array, and not every single array row, but I think this can be dealt with.
Or if you *really* wanted to be pedantic about it and actually create a 2-D array with pointers and integers but keep the memory contiguous, you might go about it the way we old-school-C programmers would, though in reality we would never do this: #include #include int main() { int** twoDArray = ( int** ) calloc( 5, (sizeof( int * ) + 5 * sizeof( int ) ) ); if( NULL == twoDArray ) { return -1; } for( int i = 0; i < 5; i++ ) { twoDArray[ i ] = ( int * )( ( char * ) twoDArray + ( ( 5 - i ) * sizeof( int * ) + i * 5 * sizeof( int ) ) ); } for( int i = 0, count = 1; i < 5; i++ ) for( int j = 0; j < 5; j++, count++ ) twoDArray[ i ][ j ] = count; for( int i = 0, count = 0; i < 5; i++, count++ ) for( int j = 0; j < 5; j++, count++ ) std::cout
If the life cycle of your matrix is simple then there's no need really, just create a local std::vector or the same with std::array. Back to your question, sure, there is a way to use a smart pointer instead, if the situation requires it.
Pointers do not have always a size of 4 Bytes. If you compile a 32-Bit application then yes, the pointer will have a size of 4 Bytes but if you compile as a 64-Bit application it will have 8 Bytes. so you might have in 3:45 for 32-Bit 50*4 = 200 Bytes but for 64-Bit 50*8 = 400 Bytes. If you don't believe me check this: #include #define SIZE 2 int main() { int** array = new int*[SIZE]; std::cout
Another great video. I once saw another option to have 2d-array and keep the data contiguously stored in memory: const int ncols = 5, nrows = 5; int *array = new int[ncols * nrows]; int **a2d = new int*[nrows]; for (int i = 0; i < nrows; i++) a2d[i] = &array[i * ncols]; for (int i = 0; i < nrows; i++) { for (int j = 0; j < ncols; j++) a2d[i][j] = 5; } The problem is we have to keep in mind that "a2d" and "array" point to the same data and the code to delete the data might be a little bit confusing: delete[] array; delete[] a2d;
Just my thoughts. If someone is need of an array of 3 ints (for example), he can just define struct of 3 ints and then use an array of instances of this struct.
At 05:10, it is not necessarily true that you have allocated 200 bytes of memory in your second case (i.e., new int*[50]). For example, a single pointer occupies 8 bytes of memory in X86-64 (aka, AMD64) computer architecture, in which case you will need to allocate 400 bytes of memory in your second case (i.e., new int*[50]).
Fascinating. I vaguely remember some of this from when I was first learning C++. I think that C# multidimensional arrays are really single-dimensional arrays under the hood, so they avoid some of the downfalls of actual meta-arrays listed here.
There's no such thing as a multi-dimension array, it's all just flat memory. Memory comes in sizes, not shapes. It's only humans that need a concept of multi dimensions. DO NOT think of a 2D array as a grid, it isn't. There IS NO grid. It's a a size. There are no rows, there are no columns, it's a list of integers.
it's 2022 and I'm learning a ton from your various series - i love that you show how simple and easy things can be, as well as demystifying complex stuff - amazing energy - huge thanks and i'll defo be donating to your patreon.
good explaination. instead of 50x50, i suggest use asymatrical matrix like 3x5 to explain this would be better for all to understand the dimentions. and further more, compare initializing matrix in stack vs heap.
I know that you deliberately used new-delete for education, but damn, is looks so much scarier than 2D std::array or std::vector. It could have really scared away someone who doesn't have much programming experience and doesn't know that they can always do it with STL containers)
Cherno Great Videos man, they have really helped me in understanding how memory works - Hahaha I have to say when you teach you're using your pro thinking and not a beginner's mindset which is not a bad thing, because I have no problem with it [I have learnt to code properly in my own way] but a lot of my class mats can't understand you when I shared your video. I Like that you put a lot of emphasis on memory and performance, but my friends don't understand you and so do I sometimes - I have to pause and draw what your saying, it would be great if you could start with a diagram of what your going to do or are doing, never the less great work man I really enjoy your videos I don't know how you manage.
Can we build our own class, store the data in a 1-dimensional array and overload the [] operator to still have the grid syntax but without cache misses? Should be possible, or?
I think that you can allocate a one dimension array on heap and then after you create a int** pointer you can copy the addresses of the specific elements from the one d array to the first dimension of pointers from the 2d array and after that you can access that contiguous memory by using two dimensions. int main() { int * one_d = new int[9]; int** two_d = new int*[3]; for(int i = 0; i < 9; i++) { one_d[i] = i; } for(int i = 0; i < 3; i++) { two_d[i] = &(one_d[i * 3]); }
for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { cout
Life's nit fair as a C++ programmer. Here we are performing mental acrobatics to ensure that we access and read memory in the most efficient manner and create really efficient speedy software. And these Python. R and Java coders hold themselves out as true programmers. I dare say that we C++ programmers are true blue software engineers and the rest software mechanics ( smile )
Hope you guys enjoyed the video! Just a quick note: the code that I wrote at 16:47 should really be *a2d[y][x] = 2;* since we want the inner loop to iterate through the actual int array data.
Don't forget to drop a comment below if something still confuses you about multidimensional arrays, and have a nice day!
May i recommend you put annotations in the video when you make errors like this?
Also I see allot of questions about using stack allocated arrays for multidimensional arrays and them being consecutive memory, might want to pin a comment explaining why this is, in general, a bad idea.
Thank you for your videos. If I create a 2D array/grid/matrix using STL vector e.g. std::vector a2d , will it suffer from the same performance penalty as the int** a2d?
t cherno how old r u now??
Hey if I wanted to multiply a 2 dimensional array by a value like 10 that has 3 rows and 4 columns with initial values present in each location, why would I set the "setw(5)" with the 5 argument instead of a (4) argument in this manipulator function.
I have been programming for 24 years, and used C++ for 15 of them, I make all my money from making my own programs... But I have actually learnt a few really useful things by going back and checking everything against your videos. Turns out there is always more to learn, and I like your teaching style. Thanks.
26 years of God so much experience
Humility is the best programming and learning skill in general :)
I love your comment
12:43 was super helpful. I was having trouble with memory leaks, so thank you so much!
i tried to sidestep the entire pointer confusion issue by using pointer arithmetic, kinda like you did in the latter half. people groan whenever its brought up, but once you get the basic idea down, you can write equations for any situation and just re-use the equations as necessary. much easier than keeping track of what level of pointer abstraction youre on, at least for me. plus it uses contiguous memory, so its fast and easy to work with.
the equation i worked out is *(xAxis + xOffset * yAxis + yOffset), where xAxis is the variable name/reference. yAxis will vary based on use case, but this equation can be expanded to n-dimensions as necessary, and it really saved me headaches when making my rpg game in the terminal by using it for the screen buffer (yAxis in that case was the vertical draw size, or in other words the number of rows).
The timing on this is incredible. I am about to start an assignment on this topic and it couldn't have come at a better time :D
I’ve been learning C++ for six months. Your videos are just right for me! Thank you ;-)
Hello,
there is a possibilty to create 2D array and having data in one row, example below:
int** AllocMatrix2D(size_t dim1, size_t dim2) {
int** matrix2d = new int* [dim1];
int* dumm = new int[dim1 * dim2];
for (size_t i = 0; i < dim1; ++i)
matrix2d[i] = dumm + i * dim2;
return matrix2d;
}
void deleteMatrix2D(int**& matrix2d) {
delete[] matrix2d[0];
delete[] matrix2d;
matrix2d = 0;
A lot easier to understand and much more intuitive doing this in Assembly language, where you're dealing with the raw pointers and direct memory structures all the time. C++, on these aspects at least, certainly does over-complicate what is a fairly simple concept. It might be easier to think in terms of pointers to pointer tables, where each pointer in that table points to the start of your array of actual data.
Nobody can explain like you. Love this video
Hi, in the final example if you want to make it slightly more efficient you could pull the 'y*5' to outside the xloop to safe keep calculating it for every element
awesome! 1-dimensional array to store bitmap!
Well, there are actually much easier ways of handling multidimensional arrays.
For Stack allocation of 10*10 array:
int Mat[10][10];
For Heap allocation of 10*10 array:
int (*Mat)[10] = new int[10][10];
// Declaring (*Mat)[10] means : Name Mat refers to (a pointer to (an int array of size 10)).
// The brackets are needed in the declaration of (*Mat)[10]. The explanation has brackets to remove ambiguity from misinterpreted English.
Mat[4][5] = 6;
delete [] Mat;
This kind of allocation is easy to handle. There is no memory fragmentation and is almost as good as 1D array.
This also easily extends to higher dimensions:
For Heap allocation of 10*10*10 array:
int (*Mat)[10][10] = new int[10][10][10];
Mat[4][5][0] = 6;
delete [] Mat;
(I'm not too sure of the deletion part. So just verify it before using it for anything important.)
My god, this video is a livesaver, thank you so much!
here is a simple explanation if u dont get it
say the int* is a column, then int** are rows for each row there are gonna be 50 int*
and int*** is height of a cube lets say , so for each unit of height there are gonna be 50 rows or 50 int** which have 50 int*
so..get it now?
I love your videos Cherno. You're a great teacher. Just a minor suggestion. In your example of 3D arrays, you could have used x, y, and z as all different sizes (say 50, 40 and 30) so as to make things more clear to beginners. Just my 2 cents though :) And cheers again for these awesome videos which help even an experienced programmer like me. Thank you.
Excellent and more intuitive suggestion.
Write a c++ program that creates a char matrix ( 2D array)
dimension then:
User insert the dimension and the data of this array
Search about one char taken by user if founded
Replace it by another char taken by user if not founded ,
print not founded message.
Print all data sorted.
thank you for your brilliant video! 👍
I have a question that storing 2-D data in a 1-D array involves one addition, one multiplication, and one addressing,
while in a 2-D array it only involves addressing and potential cache missing.
Will the later always be slower than the former?
Thanks for reading my comment!
thanks for that
Great tutorial
gods bless the holy malloc!
int** a2d = (int**)malloc(50*50*sizeof(int))
and you have one continuous memory block that you can address as a2d[x][y]
edit: nvm I'm misremembering the syntax. it works but not as I've written here.
edit2: oh gods it's been way too long. the above does not work at all, it needs to be done slightly differently and I'm too stupid to figure out right now
should be something like int** a2d = (int**) malloc(50*sizeof(int*)+50*sizeof(int))
then you gotta fill the first 50*sizeof(int*) with int* that are 50 * sizeof(int) apart...
techanically trivial but my brain doesn't comply with my wants right now...
#define ARRAY_X 15
#define ARRAY_Y 15
#define TYPE int
#include
#include
int main(){
TYPE** a2d = (TYPE**) malloc(ARRAY_X*sizeof(TYPE*) + ARRAY_X*ARRAY_Y*sizeof(TYPE));
TYPE* firstaddr = (TYPE*)(a2d + ARRAY_X);
memset(firstaddr, 0, ARRAY_X*ARRAY_Y*sizeof(TYPE));
for(int i=0; i
Cherno，your series that's awesome!!!! Thank you!
i dont think it's just 25 ints,
Assuming 32bit PTR : 5x5
it would be 25+5(intptrs) = 30 ints (for 2D)
and it will be 5x5x5(ints)+5x5(ptr to row)8 +5(ptr to plane) = 125+25+5 = 155 ints.
basically for each dimension you pay with more memory X all the previous dimension count.
this issue is not present in contiguous multi dim array, at most you might be using MxNxsizeof(member) + 2 x sizeof(index used). assuming you dont use stack to allocate your max index as aswell.
2D, 1D array performance test using the previous episode method.
====steps====
1. allocate memory
2. assign values
3. delete
============
===result===
2D: 0.001397ms
1D: 0.000429ms
==========
#include
#include
struct Timer{
std::chrono::time_point start, end;
std::chrono::duration duration;
Timer(){
start = std::chrono::high_resolution_clock::now();
}
~Timer(){
end = std::chrono::high_resolution_clock::now();
duration = end - start;
float ms = duration.count() * 1000;
std::cout
Shouldn't it be "array of pointers" at 10:53, and "array" at 10:56, so that in 11:01 it is actually an "integer"?
pointer pointer pointer pointer pointer pointer
Or more simply: int x[1d][2d][3d]...[nd]. This creates an array of [n] dimensions. Of course, you'll never (I don't know, maybe), use more than [3] dimensions, that's so confusing.
Well, I don't know that much about C++, because I don't make big projects (by the time I'm writing this, I'm 15), so I don't find pointers that useful right now.
so fun for c++..thank cherno
Great video. I think if you allocate the array on the stack it will be one continuous block right?
Why aren´t you using std::array?
Many times I have heard that std::array is more c++ style compared to "int* array = new int[]" with next to nothing in terms of overhead and many useful features normal C- Arrays don't have, like knowing it's own size and not instantly decaying to a pointer.
I am grateful for an answer from you or anyone able and willing to explain :)
Otherwise great video as always, thank you!
great stuff. Can you do more on threading thou? Something with threads sharing memory? (producer consumer threads?)
This video led me to better understand the 4th dimension by myself (and my brain is now ashes)
I have a question
Multidimensional arrays look a lot cleaner when allocated or stack, like:
int array[5][5][5];
are those ints allocated in memory "in a row"?
Even if you allocate in heap, like this:
int (*array)[5][5] = new int[5][5][5];
The data is still stored consecutively.
The point of Cherno's video is that he makes dynamic arrays, it's even possible to make non rectangular array -- triangular or other shapes. Personally, I would rather use boost::multi_array in most cases.
use 2d for jagged arrays, if you are going to differ the size for each separate row every time.
But then you cannot use a for loop to access/change it since the size of each row varies.
Sanyam Malhotra yeah ofc you can. But then you'd need to store the size of each array somewhere (in another array?) And loop through that for the size.
Cool.
You can just keep a guardian at the end of every array
Can't we just use malloc to allocate contiguous memory of size x*y and then initialize our array[x][y] the same way (2 for loops)?? In this case we would have the advantage of the notation [x][y] while eliminating any possible performance issues.
Pointer inception
How about a video showing how to store an 2d array of floats? I need to store a vga frame of distance float values.
I am getting lost in the array type vs the pointer type not matching and that does not make sense to me.
How can I allocate an array partially? For example, I have a matrix with some non-zero elements (e.g., just diagonal), can I reduce the allocation to that essential elements without losing direct indexing? It means somehow I compact used memory without affecting the efficiency?
Is there a way that you could get around having to manually delete all of the inner arrays by using smart pointers?
I think your explanation at 04:28 is a bit confusing: actually you are “creating” integers, 50 to be exact. And they are initialized: to whatever your memory has at that point, or possibly to 0 or some guard check value depending on the underlying malloc implementation. Just print out a value of said array and your program will output a value, instead of crashing :)
Obviously they both take up 200 bytes of memory, assuming a 32 bit arch. But to say that creating an integer array and a pointer array are basically identical, is a bit misleading imo. And I think it would be confusing for new programmers.
It’s only identical in term of allocated memory. Not in terms of functionality. And certainly not for the compiler. If I create a float it’s also taking up 4 bytes. But to say that float is identical to an integer, just because they both take up equal size, is stretching it a bit.
Awesome
In the 2D pointer array case, can I simply do std::vector a2dPtrArray? using vector. does it sound like doing the same Job? If yes, would be there any kind of cache miss?(because std::vector suppose to have a contiguous memory)
I actually like your videos but could you please tell me how did you study coding so good ? How to excel in concepts and coding ?
i understood it pretty well but i think this is how you code seizure into a program lol
It's funny how u go from very hard topic (threads) to easy one (2D arrays) ;)
I already studied C in my first year. While studying C++, this is my first NOPE moment.
But you can just do int* a2d = new int[50][50]?
How do you assign or swap the elements between arrays subscript
//How about this approach?
#define X_SIZE 50
#define Y_SIZE 50
int main(int argc, char** argv)
{
int** arr=new int*[Y_SIZE]; // This could even be on stack
{ // Allocate all the elements but dole them out
int* temp = new int[X_SIZE * Y_SIZE];
for (int i = 0; i < Y_SIZE; ++i)
{
arr[i] = temp;
temp += X_SIZE; //next sub array
}
}
delete[] arr[0]; // This will clean up the lot
delete[] arr;
}
You realize a topic is hard in c++ when a person who is an expert has a hard time explaining it. That's all folks
I need to write two arrays one that prints student name and the other that prints the student's grade. Should I be creatinga multidimensional array of or something else
Depends on how you want to store the grade. If grade is string, like "A-", "B+" etc, you could use a 2 dim array of strings, but that's not a very nice solution. I would create a struct to hold the name and grade, and then create an array of those structs.
Can we really store the Image using c++?........I wanna learn that.
what is the difference between the way you do it, and for example "int foo[5][5][5]"?
Cherno is talking about heap allocated 2d arrays, int foo[5][5][5] is stack allocated
this way you get stack overflow real fast.
This is WRONG.
Array of pointers are NOT multidimensional arrays, they are different types, and have different memory typology. Arrays' memory are ALWAYS continuous.
Arrays can decay into a pointer in some circumstances like argument passing and implicit conversion, but that only happens in the first dimension.
We can confirm it with below codes:
int a2d[2][3]; // this is a REAL 2D array
int ** not_a2d = a2d; // won't compile! u have to use a cast forcefully
int (*p2a)[3] = a2d; //compiles due to decays on implicit conversion
Yes, as Cherno demonstrated later in this video, 1D arrays can simulate (need reinterpretation) multidimensional arrays just because arrays' memory are continuous.
Been coding in C++ for 4+ years now, don't really know why I'm watching these videos, but sometimes something new pops up. So even though I knew all of this, it was really nice to see you think about not only the intuitive way of doing something, but also the (most of the time) better way. Most people teaching C++ (or any language really) just looks at one approach, and it's usually the intuitive one not the better one.
Really great video! Keep it up!
Same thing, coding in java for 9+ years... And you know, that trick with arrays must work for java too :)
@@alt0v14 I don't know what the implementation of Java arrays is, they might already be doing it this way underneath, check the class implementation. This is the kind of reason why I think it is important for universities to teach a low level language first (mine does) rather than a higher level one like Python or Java, so that people know these tricks and that it may actually be what their higher level objects are really doing. There is a tradeoff to this method, you aren't jumping around in memory following pointers, but you are doing arithmetic calculations on every index. If you can guarantee memory contiguity with one of the other things he mentioned, then you actually might be better off bouncing through the pointers than doing the calculations.
I'm in a similar situation, but find the extra insight in these videos related to the "why" of doing something very beneficial. That is something that is overlooked in many other training presentations and is really key, I think, to making people better programmers; thinking through why they are writing code in a specific way rather than just copying and pasting something to try and get the job done.
You should have mentioned the much simpler stack declaration of such arrays: int a[n][n];. Also, if you want it heap allocated and don't want fragmentation, you could do int* a=new int[n*n]; int** m=new int*[n]; for(i=0;i
At 0:45 the "C" in the guys surname ALMOST lines up with the "C" logo in his laptop. Makes me think of r/mildlyinfuriating...
If anyone is curious about the time difference between allocating/deleting a 3d array versus a 3d flattened array of size 5x5x5. It's significant. Below are my bench mark times using the timing method learned from previous video:
3D ARRAY
0.0278ms
0.0164ms
0.011ms
0.0112ms
Average: 0.0166ms
3D ARRAY FLATTENED
0.0015ms
0.0008ms
0.0025ms
0.0009ms
Average: 0.001425
Optimization improvement by 11.65 times faster. WOW
i was searching for this.
although i think u can have this type of array if you want to manage individual 1d array
Well, if you have 1000*1000*1000 array on which you do complex calculations later, allocation time is not that relevant. Saying that, what about addressing ? What is faster, get a value from 1D array (including index calculation) or 3D one ? Let us say, it is random access.
Come on, there is NO SUCH THING as a 3D array. Arrays are all flat, memory is just a size.
@@dmitripogosian5084 since the calculation is a couple of sums and a multiplication, I don't think is even noticeable, most likely is better to have it flattened to have less cache misses
@@gabrielbarrantes6946 Well, if the calculation sits in your inner most loop, the difference between one multiplications and two multiplications can be approaching factor of 2 for your program's runtime. But I agree that cache misses are more degrading most of the time
Love this video. Would love to see an in-depth video of writing a freelist/mempool that also takes into consideration dynamic allocation when the pool is empty and the optimisations around it.
OOOooh that would be suuper cool!
I would love to see a video on caching and accessing memory in the right way
my brain exploded just because of this one video, im scared to watch another tutorial lmao
First time I understood arrays in C++. So, I have to say, good teaching! Thank you for that!
I just did a search for this topic on your page the other day. I'm so glad to see it up !! I absolutely love your work and it's helped me understand c++ in a way I never thought possible. I'm self teaching so your work means a lot to me !! Thanks
Thanks for the video Cherno. I have a question.
Are stack allocated multidimensional arrays lay out contiguously in memory?
Hristo Hristov yes they are but are, in general, a bad idea because they can be very large in memory and can cause a stack overflow later on in your code due to you using a large portion of the limited stack space available with the array.
But when the for loop reaches the last cycle, x and y are 4. So [ x + y * 5 ] is (4 + 4) * 5 = 40 -> so it must be out of bounds. Or is C calculating like this : 4 + (4 * 5)?
Thanks, I was looking for an explanation like your comment... I was confused at this point of code.
This was my first thought of how to create multi D arrays in C but I found on the Internet people making arrays like this int matrix[2][3];
Ans then you could write
int (*ptr)[3] = matrix;
Which is kind of an intuitive syntax because if you want to know what you get when you dereference ptr, just look at this expression without a star sign. Also, when I put a 2D array like this on the stack it gets put continously in the memory. If you write ptr[1][2] you will get an offset of (1 * 3 + 2) * sizeof(int) bytes (1*3 because every array has 3 elements). If this same ptr points at an address 100, ptr[4][2] will be at an address 100 + (4*3+2) * 4 = 100 + 56 = 156.
That's the approach that I found on the Internet though, what cherno showed in this video was also natural to me as to how you would store multi D arrays. With, Cherno's approach, ptr would be declared like this int **ptr and taking this same example, ptr[4][2] would be at an address that is stored at an address 100 + 4*(sizeof(void*)) and then add 2*sizeof(int). Which means one more jumping through the memory than with the approach that I have mentioned beforehand.
Nobody ever said this to me but when you look at pointers, if you want to see what they are pointing to just remove a star. Double pointer has 2 stars, remove one and you get a pointer. Therefore a double pointer is pointing to a pointer. int (*ptr)[3] is pointing to an array of 3 ints, thus, when you dereference it, you will find 3 integers. Not an address, but an array of 3 integers.
This also means that when you walk through memory by writing ptr+1 you will move 3*sizeof(int) bytes.
On the other hand, if you have a double pointer, if you write doublePtr+1 you will travel sizeof(void*) bytes in memory.
The vibration at 5:25 had me looking all over for a rogue phone going off in my room.
As always, great video!
Although I'm already familiar with most concepts you teach, I learned it all in other languages (mostly Java and C#), so they're a great way for me to get more familiar with C++
Regarding this particular video, I do feel like using a visual representation could work better for explaining multidimensional arrays - at least that has been my experience when teaching other people.
Best of luck and keep up the excellent work!
Love you advanced insights and the optimization considerdations! Down with 2D arrays!
This is all specific to heap allocation, isn't it?
If I stack allocate int[5][5] and int[25] are both consecutive memory.
Yep, seems like what he said only applies to heap allocated multidimensional arrays.
Yup your both right, stack is always consecutive in the order you allocate that's why using the stack is always faster. However most arrays are heap allocated, especially multidimensional, since they can get very big very fast. So you want to use the heap to avoid stack overflow; of course if they are very small you should be fine on the stack.
@@nijucow the 50x50x50 array was 125kbytes. Its a good 7% of the stack, bht wont overflow it.
I need no channel youtube! As long as you use int this is true. Wouldn’t be difficult to define a data type 15x larger.
@@nijucow You can request larger stack at program start if you know how big they will need to be. Edit: Not always of course, often the size initially allowed is the maximum, but it could also be smaller in the case of shared clusters.
Thx:)))))) I was looking for this like whole day, thx a lot:))
Great video..
Yep, sure can! In this case it would be allocated on the stack of course. This would be the preferable way to do it if you can.
I agree with you, it works on my C++ compiler, i learned also that for C programming langage.
int tableauint[5][10] = {0};
for(int i = 0; i
indeed for my compiler under linux, it only works for memory allocated on the stack like I just did in this instance, doesn't work on the heap use "new" keyword.
Did you get that couch from your grandma?
I have to say college lectures teach some very bad but somewhat functional code hahaha, when am in class they never take time to teach us about memory and the stack at all and worse of all to my knowledge my current instructor has no real-world knowledge about modern use of C++ syntax, she completely lost the ball on the use of the switch statement and 2D arrays allocution within a for loop - pseudocode has helped me think better but can't only take you across the block, schools should understand that hahaha.
Holy shit.
Now I know why C# was invented!
Lol ... I am sure you know for sure why C++ exists today as well then. Cheers
When you really need to have a 2d array, you could also create a 1d array first, that stores all the data, then create an array of pointers (the 2d array) that stores pointers to {data, data + width, data + 2*width,...}. Then you have a 2d array, which has all its data in one spot. Its a bit tricky to delete it, because you just have to delete the data array and the pointer array, and not every single array row, but I think this can be dealt with.
Or if you *really* wanted to be pedantic about it and actually create a 2-D array with pointers and integers but keep the memory contiguous, you might go about it the way we old-school-C programmers would, though in reality we would never do this:
#include
#include
int main()
{
int** twoDArray = ( int** ) calloc( 5, (sizeof( int * ) + 5 * sizeof( int ) ) );
if( NULL == twoDArray ) { return -1; }
for( int i = 0; i < 5; i++ )
{
twoDArray[ i ] = ( int * )( ( char * ) twoDArray + ( ( 5 - i ) * sizeof( int * ) + i * 5 * sizeof( int ) ) );
}
for( int i = 0, count = 1; i < 5; i++ )
for( int j = 0; j < 5; j++, count++ )
twoDArray[ i ][ j ] = count;
for( int i = 0, count = 0; i < 5; i++, count++ )
for( int j = 0; j < 5; j++, count++ )
std::cout
Benchmark:
```
#include
#include
struct Timing {
std::chrono::time_point start;
Timing() {
start = std::chrono::steady_clock::now();
}
double Elapsed() {
const auto end = std::chrono::steady_clock::now();
return std::chrono::duration(end - start).count();
}
};
double Create2DArray() {
Timing timing;
int** a2d = new int* [5];
for (int i = 0; i < 5; i++) {
a2d[i] = new int[5];
for (int j = 0; j < 5; j++)
a2d[i][j] = 3;
}
return timing.Elapsed();
}
double CreateDelete2DArray() {
Timing timing;
int** a2d = new int* [5];
for (int i = 0; i < 5; i++) {
a2d[i] = new int[5];
for (int j = 0; j < 5; j++)
a2d[i][j] = 3;
}
for (int i = 0; i < 5; i++) {
delete[] a2d[i];
}
delete[]a2d;
return timing.Elapsed();
}
double Create1DArray() {
Timing timing;
int* a1d = new int[25];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++)
a1d[j + i * 5] = 2;
}
return timing.Elapsed();
}
double CreateDelete1DArray() {
Timing timing;
int* a1d = new int[25];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++)
a1d[j + i * 5] = 2;
}
delete[]a1d;
return timing.Elapsed();
}
int main() {
double totalTimeCreate2D = 0.0;
double totalTimeCreateDelete2D = 0.0;
double totalTimeCreate1D = 0.0;
double totalTimeCreateDelete1D = 0.0;
for (int i = 0; i < 10; i++) {
totalTimeCreate2D += Create2DArray();
totalTimeCreateDelete2D += CreateDelete2DArray();
totalTimeCreate1D += Create1DArray();
totalTimeCreateDelete1D += CreateDelete1DArray();
}
std::cout
Is there a way to use smart pointers for multi-dimensional arrays for memory management? If so, how should you do it, or why not?
If the life cycle of your matrix is simple then there's no need really, just create a local std::vector or the same with std::array. Back to your question, sure, there is a way to use a smart pointer instead, if the situation requires it.
Pointers do not have always a size of 4 Bytes. If you compile a 32-Bit application then yes, the pointer will have a size of 4 Bytes but if you compile as a 64-Bit application it will have 8 Bytes.
so you might have in 3:45 for 32-Bit 50*4 = 200 Bytes but for 64-Bit 50*8 = 400 Bytes. If you don't believe me check this:
#include
#define SIZE 2
int main()
{
int** array = new int*[SIZE];
std::cout
int********** array = new int********* [99];
FBI OPEN UP
Another great video. I once saw another option to have 2d-array and keep the data contiguously stored in memory:
const int ncols = 5, nrows = 5;
int *array = new int[ncols * nrows];
int **a2d = new int*[nrows];
for (int i = 0; i < nrows; i++)
a2d[i] = &array[i * ncols];
for (int i = 0; i < nrows; i++) {
for (int j = 0; j < ncols; j++)
a2d[i][j] = 5;
}
The problem is we have to keep in mind that "a2d" and "array" point to the same data and the code to delete the data might be a little bit confusing:
delete[] array;
delete[] a2d;
It looks so complicated. maybe better try std::vector
Just my thoughts. If someone is need of an array of 3 ints (for example), he can just define struct of 3 ints and then use an array of instances of this struct.
At 05:10, it is not necessarily true that you have allocated 200 bytes of memory in your second case (i.e., new int*[50]). For example, a single pointer occupies 8 bytes of memory in X86-64 (aka, AMD64) computer architecture, in which case you will need to allocate 400 bytes of memory in your second case (i.e., new int*[50]).
Fascinating. I vaguely remember some of this from when I was first learning C++. I think that C# multidimensional arrays are really single-dimensional arrays under the hood, so they avoid some of the downfalls of actual meta-arrays listed here.
how i shuld do to create a 2d array and add step by step rows ? I mean like vectorname.push_back(1d array) ? Is that possible ?
I am curious on how you might make a 2darray that a user can specify the size of? I know it would have to be a pointer.
There's no such thing as a multi-dimension array, it's all just flat memory. Memory comes in sizes, not shapes. It's only humans that need a concept of multi dimensions.
DO NOT think of a 2D array as a grid, it isn't. There IS NO grid. It's a a size. There are no rows, there are no columns, it's a list of integers.
Came here to ask why heap and not stack. The comments didn't let me down. Thanks, guys 👌👌
it's 2022 and I'm learning a ton from your various series - i love that you show how simple and easy things can be, as well as demystifying complex stuff - amazing energy - huge thanks and i'll defo be donating to your patreon.
good explaination. instead of 50x50, i suggest use asymatrical matrix like 3x5 to explain this would be better for all to understand the dimentions. and further more, compare initializing matrix in stack vs heap.
Yes understood.
awesome video
MicroGut has no videos!
I know that you deliberately used new-delete for education, but damn, is looks so much scarier than 2D std::array or std::vector. It could have really scared away someone who doesn't have much programming experience and doesn't know that they can always do it with STL containers)
Cherno Great Videos man, they have really helped me in understanding how memory works - Hahaha I have to say when you teach you're using your pro thinking and not a beginner's mindset which is not a bad thing, because I have no problem with it [I have learnt to code properly in my own way] but a lot of my class mats can't understand you when I shared your video.
I Like that you put a lot of emphasis on memory and performance, but my friends don't understand you and so do I sometimes - I have to pause and draw what your saying, it would be great if you could start with a diagram of what your going to do or are doing, never the less great work man I really enjoy your videos I don't know how you manage.
Can we build our own class, store the data in a 1-dimensional array and overload the [] operator to still have the grid syntax but without cache misses? Should be possible, or?
I think that you can allocate a one dimension array on heap and then after you create a int** pointer you can copy the addresses of the specific elements from the one d array to the first dimension of pointers from the 2d array and after that you can access that contiguous memory by using two dimensions.
int main()
{
int * one_d = new int[9];
int** two_d = new int*[3];
for(int i = 0; i < 9; i++)
{
one_d[i] = i;
}
for(int i = 0; i < 3; i++)
{
two_d[i] = &(one_d[i * 3]);
}
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
cout
This series would be one of the best sellers if it were on Udemy or anywhere else ........hands down best....
I imagine libraries exist to handle multidimensional arrays, lookups and deletes. Do you have any overview and pros/cons of them?
i dont get it, or dont like it. I expected some class based modern methods. Anyway, using pointer method for me the best than use [][][][] stuff.
Life's nit fair as a C++ programmer. Here we are performing mental acrobatics to ensure that we access and read memory in the most efficient manner and create really efficient speedy software. And these Python. R and Java coders hold themselves out as true programmers. I dare say that we C++ programmers are true blue software engineers and the rest software mechanics ( smile )
i am hungry. Could You please make 50x more Videos in a same time period? I am hungry.