36

I just have a simple question about arrays in C:

What is the best way to remove elements from an array and in the process make the array smaller.

ie: the array is n size, then I take elements out of the array and then the array grows smaller by the amount that I removed it from.

basically I'm treating the array like a deck of cards and once I take a card off the top of the deck it shouldn't be there anymore.

EDIT: I'm going to drive myself crazy before the end of the day, thanks for all the help I'm trying the value swapping thing but it's not working right.

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

enum faces { Ace = 0, Jack = 10, Queen, King };
char *facecheck(int d); 
int draw(int deck, int i); 

int main() { 
    int deck[52], i, n;
    char suits[4][9] = {
        "Hearts",
        "Diamonds",
        "Clubs",
        "Spades"
    };

    n = 0;

    for (i = 0; i < 52; i++) {
        deck[i] = n;
        n++;
    };

    for (i = 0; i < 52; i++) {       
        if (i % 13 == 0 || i % 13 == 10 || i % 13 == 11 || i % 13 == 12)
            printf("%s ", facecheck(i % 13));
        else
            printf("%d ", i % 13 + 1);
        printf("of %s \n", suits[i / 13]);
    }

    draw(deck, i);

    return 0; 
}  

char *facecheck(int d) {
    static char *face[] = {
        "Ace",
        "Jack",
        "Queen",
        "King"
    };

    if (d == Ace)
        return face[0];
    else {
        if (d == Jack) 
            return face[1];
        else {
            if (d == Queen)
                return face[2];
            else { 
                if (d == King)
                    return face[3];
            }
        }
    } 
}

int draw(int deck, int i) { 
    int hand[5], j, temp[j];

    for (i = 0; i < 52; i++) {
        j = i
    }; 

    for (i = 0; i < 5; i++) {
        deck[i] = hand[]; 
        printf("A card has been drawn \n");
        deck[i] = temp[j - 1];
        temp[j] = deck[i];
    };
      
    return deck;
}
Improve this question
4
  • 3
    If you actually want it to 'grow smaller', implement a linked list. Otherwise, do some value swapping and keep an 'end of array' guard value in your array. You cannot simply remove an element from a regular array Commented Apr 4, 2013 at 20:32
  • The performance tradeoff is terrible if you're going to realloc or memcpy every time you change your array. Commented Apr 4, 2013 at 20:33
  • 1
    Ignore those naysayers -- memcpy is the way to go. (Although if you're really taking "a card off the top" then just use a simple stack -- make the "top" the end of the array, and decrement a value indicating its length with each "pop" of the "stack".) Commented Apr 4, 2013 at 20:36
  • @JoeFrambach memcpy() does not work because of the overlapping memory copy. The correct way is to use memmove() . Commented Feb 24, 2016 at 6:10

6 Answers 6

Reset to default
27

There are really two separate issues. The first is keeping the elements of the array in proper order so that there are no "holes" after removing an element. The second is actually resizing the array itself.

Arrays in C are allocated as a fixed number of contiguous elements. There is no way to actually remove the memory used by an individual element in the array, but the elements can be shifted to fill the hole made by removing an element. For example:

void remove_element(array_type *array, int index, int array_length)
{
   int i;
   for(i = index; i < array_length - 1; i++) array[i] = array[i + 1];
}

Statically allocated arrays can not be resized. Dynamically allocated arrays can be resized with realloc(). This will potentially move the entire array to another location in memory, so all pointers to the array or to its elements will have to be updated. For example:

remove_element(array, index, array_length);  /* First shift the elements, then reallocate */
array_type *tmp = realloc(array, (array_length - 1) * sizeof(array_type) );
if (tmp == NULL && array_length > 1) {
   /* No memory available */
   exit(EXIT_FAILURE);
}
array_length = array_length - 1;
array = tmp;

realloc() will return a NULL pointer if the requested size is 0, or if there is an error. Otherwise, it returns a pointer to the reallocated array. The temporary pointer is used to detect errors when calling realloc() because instead of exiting, it is also possible to just leave the original array as it was. When realloc() fails to reallocate an array, it does not alter the original array.

Note that both of these operations will be fairly slow if the array is large or if a lot of elements are removed. There are other data structures like linked lists and hashes that can be used if efficient insertion and deletion is a priority.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

In the first example, the array length will have changed because of the remove, so it seems fair to pass the array_length as a pointer as well, no? So it becomes (... int *array_length) and at the end of the function body: (*array_length)--;
What happens to the address of the item which got removed? Does it get automatically free()'d? Specifically if we're deleting an item which is a reference to an object.
11

What solution you need depends on whether you want your array to retain its order, or not.

Generally, you never only have the array pointer, you also have a variable holding its current logical size, as well as a variable holding its allocated size. I'm also assuming that the removeIndex is within the bounds of the array. With that given, the removal is simple:

Order irrelevant

array[removeIndex] = array[--logicalSize];

That's it. You simply copy the last array element over the element that is to be removed, decrementing the logicalSize of the array in the process.

If removeIndex == logicalSize-1, i.e. the last element is to be removed, this degrades into a self-assignment of that last element, but that is not a problem.

Retaining order

memmove(array + removeIndex, array + removeIndex + 1, (--logicalSize - removeIndex)*sizeof(*array));

A bit more complex, because now we need to call memmove() to perform the shifting of elements, but still a one-liner. Again, this also updates the logicalSize of the array in the process.

Improve this answer

3 Comments

if removeIndex is the last element (1) the second argument is not within the bounds of the array and (2) --logicalSize - removeIndex is 0, and thus (i assume (though i have not tested)) nothing happens, as no bytes are to be moved... in my case, i only memmove if --logicalSize - removeIndex is not 0 and then realloc array to logicalSize no matter what (will have the effect of removing removeIndex when it is the last element as well as resizing the array to its new size regardless)
@AustinBravo The if() is just superfluous: It is correct that array + removeIndex + 1 is beyond the end of the array, but that's fine because it's just beyond the last element of the index, and thus the standart guarantees that the pointer arithmetic is ok. And since --logicalSize - removeIndex is zero, as you correctly observed, the memmove() call does not dereference that pointer. There is no point in special handling of edge cases if the normal code already handles them correctly; if you are fearfull, better add a unit test for the edge case than special case handling code, imho.
@AustinBravo In fact, one of my main criteria for elegant code is that all edge cases are handled correctly without need for special case handling. It has the nice side effect, that the code for the normal case and the edge cases cannot diverge, and that no bugs can hide within special case handling code. Of course, it requires a deeper knowledge of the functions and language constructs in question to write such code. As long as you don't know better, go ahead and add the special case. But I will prefer the more concise code.
8

You don't really want to be reallocing memory every time you remove something. If you know the rough size of your deck then choose an appropriate size for your array and keep a pointer to the current end of the list. This is a stack.

If you don't know the size of your deck, and think it could get really big as well as keeps changing size, then you will have to do something a little more complex and implement a linked-list.

In C, you have two simple ways to declare an array.

  1. On the stack, as a static array

    int myArray[16]; // Static array of 16 integers

  2. On the heap, as a dynamically allocated array

    // Dynamically allocated array of 16 integers
int* myArray = calloc(16, sizeof(int));

Standard C does not allow arrays of either of these types to be resized. You can either create a new array of a specific size, then copy the contents of the old array to the new one, or you can follow one of the suggestions above for a different abstract data type (ie: linked list, stack, queue, etc).

Improve this answer

3 Comments

How would you implement something using a pointer, like let's just say the array is a deck of cards, so you know the value (52) and such. I'm having trouble coming up with the code to do this, I've been wracking my brain for days trying to figure a bunch of stuff out so my brain is coded out, hence why I need help
Can you edit your question to include some of your code and attempts so far? An array is a very simple thing to create. More details would clear things up.
Standard C does allow to resize dynamically allocated arrays, with realloc(). Now you could say that realloc() copies, but it doesn't (it will grow/shrink in place when possible, or use memmove rather than memcpy when it really needs to move the array).
7

Interestingly array is randomly accessible by the index. And removing randomly an element may impact the indexes of other elements as well.

    int remove_element(int*from, int total, int index) {
            if((total - index - 1) > 0) {
                      memmove(from+i, from+i+1, sizeof(int)*(total-index-1));
            }
            return total-1; // return the new array size
    }

Note that memcpy will not work in this case because of the overlapping memory.

One of the efficient way (better than memory move) to remove one random element is swapping with the last element.

    int remove_element(int*from, int total, int index) {
            if(index != (total-1))
                    from[index] = from[total-1];
            return total; // **DO NOT DECREASE** the total here
    }

But the order is changed after the removal.

Again if the removal is done in loop operation then the reordering may impact processing. Memory move is one expensive alternative to keep the order while removing an array element. Another of the way to keep the order while in a loop is to defer the removal. It can be done by validity array of the same size.

    int remove_element(int*from, int total, int*is_valid, int index) {
            is_valid[index] = 0;
            return total-1; // return the number of elements
    }

It will create a sparse array. Finally, the sparse array can be made compact(that contains no two valid elements that contain invalid element between them) by doing some reordering.

    int sparse_to_compact(int*arr, int total, int*is_valid) {
            int i = 0;
            int last = total - 1;
            // trim the last invalid elements
            for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements from last

            // now we keep swapping the invalid with last valid element
            for(i=0; i < last; i++) {
                    if(is_valid[i])
                            continue;
                    arr[i] = arr[last]; // swap invalid with the last valid
                    last--;
                    for(; last >= 0 && !is_valid[last]; last--); // trim invalid elements
            }
            return last+1; // return the compact length of the array
    }
Improve this answer

Comments

0

Try this simple code:

#include <stdio.h>
#include <conio.h>
void main(void)
{ 
    clrscr();
    int a[4], i, b;
    printf("enter nos ");
    for (i = 1; i <= 5; i++) {
        scanf("%d", &a[i]);
    }
    for(i = 1; i <= 5; i++) {
        printf("\n%d", a[i]);
    }
    printf("\nenter element you want to delete ");
    scanf("%d", &b);
    for (i = 1; i <= 5; i++) {
        if(i == b) {
            a[i] = i++;
        }
        printf("\n%d", a[i]);
    }
    getch();
}
Improve this answer

2 Comments

Code only answers are discouraged. Please add some explanation as to how this solves the problem, or how this differs from the existing answers. From Review
This code has many disadvantages, and cannot compete for "best way to remove elements". Moreover, this algorithm is incorrect doesn't move all elements (just copies makes one duplicate). To say nothing about the undefined behaviour in a[i] = i++; and awful coding style. I advise you to remove this answer.
0

I usually do this and works always.

/try this/

for (i = res; i < *size-1; i++) { 

    arrb[i] = arrb[i + 1];
}

*size = *size - 1; /*in some ides size -- could give problems*/
Improve this answer

2 Comments

Hey, can you please explain what this code snippet does?
It deletes a value from an array once you have found that value is in it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.