Optimal array push

Question

I wanna create some function taking two parameters: int element, and input array. I want this function to place the element parameter at the first place in the array, enlarge the array by single index, and finally place the input array after the pushed element.

To illustrate this, let's say my input array is {1, 2, 3}, and element passed as the parameter is 5. The output should be {5, 1, 2, 3}.

How can I do this optimally?

I came out with this function:

void push(int el, int **arr)
{
    int *arr_temp = *arr;

    *arr = NULL;
    *arr = (int*) malloc(sizeof(int)*(n - 1));

    (*arr)[0] = el;
    for(int i = 0; i < (int)n - 1; i++)
    {
        (*arr)[i + 1] = arr_temp[i];
    }
}

It works, but well, it's not the fastest function I wrote, and it slows down the whole program. Is there a better way to do this?

My guess was doing something like (*arr)[1] = arr_temp, but it didn't work, and I'm not sure if there's a possibility in C to do something like this.

Answer 1

Instead of using a raw array, it'd probably be better to wrap your array in a struct:

typedef struct
{
    size_t elementsAllocated;
    size_t elementsUsed;
    int* buffer;
} vector;

And then your pushing function could look something like:

vector* push_front(vector* v, int item)
{
    if (elementsUsed == elementsAllocated)
    {
        // Time to grow the buffer.
        int elementsAllocated = v->elementsAllocated * 2;
        if (elementsAllocated <= v->elementsAllocated)
        {
            abort(); // Overflow occurred.
        }

        int* buffer = realloc(v->buffer, elementsAllocated * sizeof *buffer);
        if (buffer == NULL)
        {
            abort();
        }

        // Shift the existing data over.
        memmove(buffer + elementsAllocated - v->elementsUsed,
                buffer + v->elementsAllocated - v->elementsUsed,
                v->elementsUsed * sizeof *buffer);
        v->buffer = buffer;
        v->elementsAllocated = elementsAllocated;
    }

    // Prepend the new item.
    int* p = v->buffer + v->elementsAllocated - v->elementsUsed - 1;
    *p = item;
    v->elementsUsed++;
    return p;
}

This would be significantly simpler if you can append items to the end of the array instead of prepending to the beginning. Note that the above code is completely untested and may contain off-by-one errors, but the core ideas are:

• Memory allocation is expensive. Allocate more memory than you need and then write to allocated but unused space. This reduces the number of times you need to reallocate your buffer and to copy your data to shift it over.
• Minimize the number of times you have to grow the buffer by growing it in larger steps.

Answer 2

As suggested in the comments, you may want to just append to the array, then use a little struct and function to let you access the element you want as if the array were being prepended to. You seem to have the re-sizing down, so I'll just suggest some example code for the reversal. This is untested, as I don't have a unix box sitting by me at the moment for easy testing - note my C is a bit rusty.

typedef struct{
    int* array;
    int size;
} prependArray;

void accessElement(int element, prependArray myArray) {
    return myArray.array[size-element-1];
}

This way, you can also alloc arrays that are a bit larger than you need. Keep an int in "prependArray" that lists the size you last realloc'd to. When someone tries to add an item, check if you've hit that limit; if you have, resize the list before adding the new value. This saves on allocation time if you're adding lots of numbers.

You might want to look up the "vector" data-structure for a bit more on this sort of idea.