CODEWITHSUNDEEP
carrayselement
Nick Spot
Nick Spot

Reputation: 267

C Dynamic Array Inserting in the Middle

Heyo. In my C program, im dealing with lots of operations in which i have to read files, and store its data in arrays. For that, as the array handling in C is a little bit complicated, i'm using the following code suggested in this post:C dynamically growing array

typedef struct {
    float *array;
    size_t used;
    size_t size;
} points;

void initArrayInd(arrayInd *a, size_t initialSize) {
    a->array = (GLubyte *)malloc(initialSize * sizeof(GLubyte));
    a->used = 0;
    a->size = initialSize;
}

void insertArrayInd(arrayInd *a, GLubyte element) {
    if (a->used == a->size) {
        a->size *= 2;
        a->array = (GLubyte *)realloc(a->array, a->size * sizeof(GLubyte));
    }
    a->array[a->used++] = element;
}

void freeArrayInd(arrayInd *a) {
    free(a->array);
    a->array = NULL;
    a->used = a->size = 0;
}

I'm used to Java programming, so my way of thinking how should i code the things is, in most of the cases, wrong. I want to, based on this dynamic array allocation, be able to create a new function that will insert me a record in the position i have specified. I want to know what is the best way to do so.

Should i insert the the new record at the end of the array, and then shift everything one position. Should i create a new array, copy the i-1 elements, then place i and copy the i+n elements. Should i split the initial array into two, create a third and mix everything together. What is the best way in C to accomplish so?

EDIT: This would do it? 

void insertFPointsAt(points *a, float element, int position) {
    if (a->used == a->size) {
        a->size *= 2;
        a->array = (float *)realloc(a->array, a->size * sizeof(float));
    }
    memmove(&a->array[position], &a->array[position+1], &a->array[a->used] - &a->array[position]);
    a->array[position] = element;
}

Upvotes: 4

Views: 4839

Answers (2)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726609

When you insert in the middle of the array, you need to implement this algorithm:

  • Check if you have enough space for the element that you want to insert
  • If you do not have enough space, extend the array the way that you do when you add an element at the end
  • Move the data up by one position using memmove
  • Place the element at the position requested by the caller

The only step that's different from inserting at the end is the third one, where you move the content of your array up by one element. memmove function deals with this correctly even when the two areas overlap.

EDIT: The memmove call should look like this:

memmove(&a->array[position+1], &a->array[position], &a->array[a->used] - &a->array[position]);

A few additional notes:

  • Growing the array to twice the size is not going to work after freeing the array, because you set the size to zero.
  • Unlike C++ where a cast of malloc is required, C does not require you to cast the return value of malloc/calloc/realloc.

Upvotes: 5

Carl Norum
Carl Norum

Reputation: 224964

You only ever need to shift the elements after the index you're trying to insert. Where you'll run into unnecessary copying is when you resize the array - the realloc call might do a copy for you, and you'd end up copying twice. I'd do something like:

insert element E at index I:
   if resize is necessary:
       - allocate new larger buffer
       - copy elements 0 to I-1 from old buffer into new buffer
       - insert E at index I of new buffer
       - copy elements I to end of old buffer into new buffer, starting at index I+1
       - free old buffer
   else
       - copy elements I to end of buffer 'up by one' index
       - insert E at index I of the buffer

Upvotes: 1

Related Questions