How do you exactly do dynamic memory allocation?

[Gat Pelsinger]

I still actually don't know how is actual dynamic memory allocation done. In C, yea sure we got malloc, but because we need to be able to trace and access every single individual memory space, we can get an array and put the memory addresses of the memory spaces to be able to actually hold them. Is this even how you do or I am bluffing? But a problem to this approach is that what if we don't also know the size of the array, which we probably don't, then don't we also need to dynamically resize the array? How do you do that, and not only in C but C++ and Java?

 

EDIT - Also, I am able to use malloc without typecasting it? How?

[noname8365]

Yes, you literally just use malloc. Remember to also use a free for every malloc so that your program doesn't leak memory.

 

If you want a dynamically resizable array (ie, linked list) you're better off using some language other than C because C is rather low level and it will get complicated.

[Slottr]

Not sure what you're trying to do specifically, but in C: memory allocation for arrays is static.

 

You'll generally set array sizes based on the content you're building and how much of it. You don't need to keep track of individual memory addresses outside of pointers.

 

Java is different as its not as low level. 

[adm0n]

The dynamic aspect of dynamic memory allocation first and foremost means, that the size of your array isn't available/known at compile time (or you don't want to put the array on the stack for other reasons). So you create your array at run time via something like malloc.

 

If you want to change the size of your array, you can either call realloc, or create a new array that has the correct size and copy everything you want from the old array over to the new one. Then you free the old one, and store the pointer to the new array in the old variable. That way it seems to the program like you have changed the size of the array. (This is how a c++ vector is implemented if I remember correctly).

 

There are different dynamic data structures, that handle things for you, but dynamic memory allocation just refers to you handling all the memory allocation at run time.

 

Edit: The compiler can decide if it wants to throw an array if you don't type cast the pointer you get via malloc. I think a lot of them just handle the casting for you nowadays. You could theoretically also just write your whole program with void pointers. But that would be horrible, so please don't do that.

[Gat Pelsinger]

@adm0n

2 hours ago, Gat Pelsinger said:

EDIT - Also, I am able to use malloc without typecasting it? How?

 

[dcgreen2k]

4 hours ago, Gat Pelsinger said:

Also, I am able to use malloc without typecasting it? How?

In C, you don't need to include the typecast because malloc's return value automatically gets cast to the type of the variable you assign it to. This means:

int* array = (int*) malloc(sizeof(int) * 100);
int* array = malloc(sizeof(int) * 100);

do the same thing. Note that you do still need to include the variable type at the very start of the line, or else it won't work like you want it to as an array of ints.

 

4 hours ago, Gat Pelsinger said:

I still actually don't know how is actual dynamic memory allocation done. In C, yea sure we got malloc, but because we need to be able to trace and access every single individual memory space, we can get an array and put the memory addresses of the memory spaces to be able to actually hold them. Is this even how you do or I am bluffing?

All you need to access the memory you allocate is the pointer that malloc returns. That pointer is the start of the array that got allocated, and no additional bookkeeping is required. Here's an example of using memory allocated with malloc:

#include <stdio.h>
#include <stdlib.h>

int main() {
    // Allocate memory that can hold an array of 10 ints
    int* array = malloc(sizeof(int) * 10);

    // Fill up the memory with values from 0 to 9
    for (int i = 0; i < 10; i++) {
        array[i] = i;
    }

    // Print out the values we just wrote
    for (int i = 0; i < 10; i++) {
        printf("%d\n", array[i]);
    }
    
    // Don't forget to free the memory
    free(array);

    return 0;
}

 

4 hours ago, Gat Pelsinger said:

But a problem to this approach is that what if we don't also know the size of the array, which we probably don't, then don't we also need to dynamically resize the array? How do you do that, and not only in C but C++ and Java?

You can dynamically resize arrays. In C, you would use realloc to do this.

#include <stdio.h>
#include <stdlib.h>

int main() {
    // Allocate memory that can hold an array of 10 ints
    int* array = malloc(sizeof(int) * 10);

    // Fill up the memory with values from 0 to 9
    for (int i = 0; i < 10; i++) {
        array[i] = i;
    }

    // Expand the array to hold 100 ints
    array = realloc(array, sizeof(int) * 100);

    // The values we wrote earlier got copied into the new array
    for (int i = 0; i < 10; i++) {
        printf("%d\n", array[i]);
    }

    // But now we can write more values without causing a memory error
    // Here we're writing to the end of the array
    for (int i = 90; i < 100; i++) {
        array[i] = i;
    }

    // Check the new values we wrote
    for (int i = 90; i < 100; i++) {
        printf("%d\n", array[i]);
    }
    
    // Don't forget to free the memory
    free(array);

    return 0;
}

 

In C++:

#include <iostream>

int main() {
    // Allocate memory for an array of 10 ints
    int* array = new int[10];

    // Write values in the array
    for (int i = 0; i < 10; i++) {
        array[i] = i;
    }

    // Expand the array to hold 100 ints
    // Note: we do this in C++ by creating an entirely new array!
    int* bigger_array = new int[100];

    // Next, we copy all the old elements over
    for (int i = 0; i < 10; i++) {
        bigger_array[i] = array[i];
    }

    // Last, delete the old array
    delete[] array;

    // Let's make sure the elements are present in the new array
    for (int i = 0; i < 10; i++) {
        std::cout << bigger_array[i] << std::endl;
    }

    // Free the new array
    delete[] bigger_array;

    return 0;
}

 

In Java:

public class Main {
    public static void main(String[] args) {
        // Allocate memory for an array of 10 ints
        int[] array = new int[10];

        // Write values to the array
        for (int i = 0; i < 10; i++) {
            array[i] = i;
        }

        // Expand the array to hold 100 ints
        int[] biggerArray = new int[100];

        // Copy the old values
        System.arraycopy(array, 0, biggerArray, 0, 10);

        // Make sure the old elements are present
        for (int i = 0; i < 10; i++) {
            System.out.println(biggerArray[i]);
        }
    }
}

 

Or, you could use std::vector in C++ and ArrayList in Java to have a dynamic array without having to worry about allocating, deallocating, copying, etc.

[Gat Pelsinger]

@dcgreen2k I see. I didn't even need the array resizing. I just had to treat the pointer that malloc returned to as an array. But my question is though, that how does it let us treat it as an array? We never defined it as an array. I think my understanding of array's is a little bit different. Just like how recently I found out you can create custom code scopes in C by using curly brackets without any keywords. I used to think scopes could only be made by using stuff like for loops or if blocks. But no you can create your own blocks.

[dcgreen2k]

1 minute ago, Gat Pelsinger said:

But my question is though, that how does it let us treat it as an array? We never defined it as an array.

It lets us treat it as an array because an array is just a contiguous block of memory. Malloc gives you a contiguous block of memory with a pointer to the very start of it.

 

On top of that, did you know that the [] arrays use is just syntax sugar? The square brackets are a short form of doing something called pointer arithmetic, which is how your computer actually works with arrays. Here's what I mean:

#include <stdio.h>
#include <stdlib.h>

int main() {
    // Allocate memory that can hold an array of 10 ints
    int* array = malloc(sizeof(int) * 10);

    // Fill up the memory with values from 0 to 9
    for (int i = 0; i < 10; i++) {
        array[i] = i;
    }

    // Get the value at index 5 with regular array syntax
    int value_regular = array[5];
    printf("%d\n", value_regular);

    // That array syntax actually expands to this pointer arithmetic
    int value_arith = *(array + 5);
    printf("%d\n", value_arith);
    
    // That expansion is also why we can do this weird thing
    int value_weird = 5[array];
    printf("%d\n", value_weird);

    // Don't forget to free the memory
    free(array);

    return 0;
}

 

In short, arrays are just something programming languages give us to make working with blocks of memory easier.

[Sauron]

8 minutes ago, Gat Pelsinger said:

But my question is though, that how does it let us treat it as an array? We never defined it as an array

An array is nothing more than a pointer to a block of contiguous memory.

 

When you define an array of n chars all the program does is allocate n bytes in memory and return a pointer to the beginning of that area (with a few caveats for memory alignment). When you access, say, the 3rd element in the array you simply add 2 to that pointer and voilà, you found the third byte in that memory area. For types larger than 1 byte the compiler abstracts away the multiplication (i.e. the third element of a word array would be offset by 2*2 bytes from the start of the array).

 

Fundamentally the memory area does not know or care what it contains; type constraints are dictated by the compiler, not by the memory. There is also no information regarding the size of the array; all you know is where it starts.