Return A Dynamically Allocated 2D Array From A Function | C Programming Tutorial
Vložit
- čas přidán 1. 09. 2022
- How to return a dynamically allocated 2D array from a function in C. Source code: github.com/portfoliocourses/c.... Check out www.portfoliocourses.com to build a portfolio that will impress employers!
I had a very hard time to understand this concept when trying to change the *stack values when doing a DFS. I learned that, even if we have a *stack, we need to set the parameter of the function to change the *stack to **stack like:
void change_stack(stack_t **stack, int value) // This is a pointer to the stack pointer and is needed to change/access the stack itself by dereferencing it later.
void stack_pop(stack_t **stack) {
if(!*stack) {
printf("Stack is empty
");
return;
}
stack_t *old = *stack;
*stack = (*stack)->next;
free(old);
}
Otherwise, if the function is void change_stack(stack *stack, int value), it does not change the actual value. We need the pointer to *stack.
I learned this the hard way ahah
Thank you for your videos. You're being a monumental help
Is it possible to write code that produces the same result using the `static` keyword?
Exactly the help I needed. Explained very clearly. Thank you
You're welcome! 🙂 I'm really glad to hear this helped you out.
this video should get more likes and views! Nice explanation!🙏
This is the best so far, i`ve found about arrays in functions, even better than college ones.
Thank you Gabriel, I'm glad you enjoyed it! :-)
Thank you so much for this detailed explanation. I've been having trouble trying to understand the logic ✌️💪🙂
You're very welcome, I'm glad to hear this was helpful for you! :-)
I would not advise allocating a 2D array like this because the multiple malloc calls fragment the array across memory, which has significant impacts on performance. Instead you should allocate one big array of [m*n] and then typecast the array to [m][n]
For anyone curious, this is a good article covering optimizations/trade-offs with dynamically allocating 2D arrays: medium.com/@pauljlucas/dynamically-allocating-2d-arrays-efficiently-and-correctly-in-c-1b35384e87bf.
Can you explain why memory fragmentation causes performance issues? After all, accessing an array element is done in one step. Code does not point to the top of the heap and then search sequentially for the location. Does it?
@@rivernet62 Accessing main memory is an expensive operation. A computer can execute at least a hundred computational instructions in the time it takes to perform a single main memory access. Due to this, CPUs are designed to use tiered caching where the most recently used data is stored in small caches the CPU can quickly access, and when a value is retrieved from memory, in reality, the entire cache line (all nearby values) are also cached to reduce the number of necessary memory accesses. If an array is fragmented across memory, you cannot fully take advantage of caching because the locality of the values is reduced, meaning more memory accesses.
@@eruhinmakhtar9162 thank you for the good explanation. I have to say that design sounds highly non-deterministic. How could you predict caching behavior?
@@rivernet62Caching is designed around the ideas of temporal and spatial locality. Temporal locality is the idea that if a program access a piece of memory once, it will likely need it again, hence why the cache stores recently used values. Spatial locality is the idea that if a program access memory, it will likely need nearby memory values too, hence entire cache lines are fetched from main memory. Caching is deterministic, and the way you leverage caching the most is by designing your algorithms with as much temporal and spatial locality in memory accesses as possible.
Just what I was looking for. Thanks!
You’re welcome! :-)
Thank you so much. I was confused on how to return an array (didn't know you could use pointers like this).
You’re very welcome! :-)
Another way is to create a single pointer, alocate all elements once and use some arithmetic to get correct a(i,j) element. In the end, free all elements once.
this is really helpful. Thank you so much!
You’re welcome Nathan! :-) I’m glad to hear it was really helpful for you.
It's better to store matrix in an 1D array by rows or by columns (in fortran manner). See LAPACK interface, for instance.
Weird, when an 100% identical "solution" as written in the main function, i mean code syntax, cannot be applied in a function below main. (*arrayPTR)[i] vs *(int*)arrayPTR + i).
If I understand the subject correctly, this is not exactly a 2d array in C. The returned matrix functions as if it's a 2d array, but in fact, it is a 1d array of pointers, each pointer points to the first element of a 1d array. This is different compared to an actual 2d array created by the following code:
int a[2][3]; // where a will decay to a pointer to a whole 1d array of size 3, i.e., int (*ptr)[3];
That's correct, it's not a 2D array "on the stack" like when we create an array with something like: int a[2][3]. We would still call it a 2D array, but more specifically we would say that it's a "dynamically allocated 2D array". There are actually a few ways to create dynamically allocated 2D arrays: www.techiedelight.com/dynamically-allocate-memory-for-2d-array/. In this video I go over the most common way to dynamically allocate a 2D array in detail, including a discussion about how they are arranged in memory compared to a 2D array on the stack, you've got the right idea already but you might find it interesting if you're curious about the subject: czcams.com/video/ZLc_OpzND2c/video.html.
why use malloc(sizeof(int*)*m) to allocate space for rows in 2d array ?
Because we have m rows total, and each row is "a pointer to an int".... a pointer to the first int in the first column of that row. sizeof(int *) gives u the number of bytes to store a pointer to an int, and when we multiply that by m, we'll have enough space to store m amount of pointer to int values. Hopefully this helps! :-)
Thank you so much
You’re very welcome Ako! :-)
I understand from a "monkey see monkey do" point of view. However, I don't see how the syntax jives with what is happening under the hood. (1) To access any element A[i][k], the compiler just needs a pointer to the first element and the size of the array. Why does it need a pointer to a pointer. (2) Also, is it true that all that the compiler keeps track of is a single pointer for the first element of the array, rather than "m" pointers for each row of the array? Thanks.
Great question Karim! :-) So a 2D array declared on the stack is different than the type of 2D array we've made in this video using dynamic memory allocation. This video discusses dynamically allocating 2D arrays and may be of interest to you: czcams.com/video/ZLc_OpzND2c/video.html.
In this case here we are using a pointer to a pointer because it will point to an array of pointers (essentially, pointers to each row in our 2D array). Each of the pointers in *this* array will point to a row of int values in our 2D array. When we have:
matrix[i]
In this case, what's happening is that we're accessing the pointer to an int at the index i in the array of pointers to ints... and that pointer to an int points to the first int in an array of ints for this "ith row". We then have:
matrx[i][j]
And we get the jth element in this row.
You can see the difference somewhat in the code I've posted below. Notice how the sizeof(array[0]) is different for both "2D arrays" because they are fundamentally different structures. In the case of the 2D array on the stack array[0] is essentially an array of 10 ints (the row), and it takes 4 byes to store an int, so we have that the sizeof(stack_array[0]) is 40. But in the case of heap_array[i] it's really a pointer to an int, and so we get the size of a pointer (which should be 8 bytes).
Hopefully this helps! :-)
------
#include
#include
int main()
{
int stack_array[10][10];
printf("%zu
", sizeof(stack_array[0]));
int **heap_array = malloc(sizeof(int *) * 10);
for (int i = 0; i < 10; i++)
heap_array[i] = malloc(sizeof(int) * 10);
printf("%zu
", sizeof(heap_array[0]));
return 0;
}
@@PortfolioCourses I understand better after looking at the code you sent. What I missed in the original video was that the first malloc reserves space for "m" pointers and returns a pointer (called matrix) for the starting address (??) of those "m" pointers.
That is why matrix is a pointer to a pointer. The second malloc (for each row "i") reserves space for "n" ints and returns a pointer (called matrix[i] for those "n" ints). I still have to learn about pointer arithmetic but is it correct that the reference matrix[i][j] is really *(matrix[i] + j), i.e., the int value stored at address (matrix[i] + j)? In other words, when the compiler sees matrix[i][]j], it knows that it has to do the above pointer arithmetic.
Awesome vid, I tried making a snake game, but stuck on a seg fault lol taking a break for now.
Thanks for the positive feedback Juan! And good luck on that snake game. :-)