CODEWITHSUNDEEP
carraysmemcpyshallow-copy
Ivor Denham-Dyson
Ivor Denham-Dyson

Reputation: 685

How to make a shallow copy of an array and store that copy in a struct

I have a structure.

typedef struct Heap {
    int length;
    int size;
    int A[];
} Heap;

I am trying to make a shallow copy of a given array and store it in this struct. Such that when the array is altered or elements are swapped this is mirrored in the original array.

Heap * build_max_heap(int A[], int length) {
    Heap * heap = malloc(sizeof(Heap) + length*sizeof(int *));
    *heap = (Heap) { length, length };
    memcpy(heap->A, A, length*sizeof(int *));

    /*
    for(int i = floor(((heap->length)-1)/2); i >= 0; --i) {
        max_heapify(heap, i);
    }
    */

    return heap;
}

int main() {
    int A[] = {0, 3, 7, 61, 3, 40, 4, -1, 8, 10};

    Heap * heap = build_max_heap(A, 10);

    A[0] = 100;

    for(int i = 0; i < 10; ++i) {
        printf("%i, ", A[i]);
    }

    printf("\n");

    for(int i = 0; i < 10; ++i) {
        printf("%i, ", heap->A[i]);
    }

    return 0;
}

Currently the following is returned.

100, 3, 7, 61, 3, 40, 4, -1, 8, 10,
0, 3, 7, 61, 3, 40, 4, -1, 8, 10,

My expected result would be 

100, 3, 7, 61, 3, 40, 4, -1, 8, 10,
100, 3, 7, 61, 3, 40, 4, -1, 8, 10,

Similarly heap->A[0] = 100; should have the same effect. I am also not sure whether length*sizeof(int *) is correct or should instead be length*sizeof(int) however I imagine this will be resolved by answering the former.

Code

Upvotes: 0

Views: 95

Answers (2)

0___________
0___________

Reputation: 67476

Your idea was good- the realization not.

typedef struct Heap {
    size_t length;
    size_t size;
    int A[];
} Heap;

Heap *build_max_heap(int *A, size_t length) {
    Heap * heap = malloc(sizeof(*heap) + length*sizeof(*A));
    *heap = (Heap) { length, length };
    memcpy(heap-> A, A, length*sizeof(*A));

    /* another stuff */

    return heap;
}

This kind of structs with data ad the end of the struct is in a very common use. I allows only one allocatiion (and one free) instead of two. It is also more efficient as it does not require reading the pointer A and then dereferencing it.

Upvotes: -1

tmrlvi
tmrlvi

Reputation: 2361

Shallow copy amounts to copying the references instead of the values. However, this requires defining the struct a bit differently:

typedef struct Heap {
    int length;
    int size;
    int *A;
} Heap;

This way, the values of the array A are not contained immediately after the struct, and we have the freedom to assign any pointer to it. Then, we simply init the heap as:

Heap * build_max_heap(int A[], int length) {
    Heap * heap = malloc(sizeof(Heap));
    *heap = (Heap) { length, length, A };
    /* ... heapify code etc ... */
    return heap;
}

But you must use this with caution - this implies that if you create two heaps out of A, they will influence each other. It is still best practice to create a copy.

Upvotes: 2

Related Questions