lets say I've an array

int size=6;
int a[size]={0,1,2,3,4,5};

and I wanted to delete k=3 element.

for(i=k;i<size-1;i  )
a[k]=a[k 1];
size=size-1;

here I've just removed the element from index k, for sure that value would not be present in the array, but if not in the array then where is the data, that value.

CodePudding user response：

Nothing is deleted.

The line a[k]=a[k 1]; sets the value of a[k] to the value of a[k 1].

So if the array starts with {0,1,2,3,4,5} and k is 3, then afterwards the array holds {0,1,2,4,4,5}.

CodePudding user response：

You cannot "delete" items in an array, just overwrite them with other data. C is close to the hardware and in physical RAM there is no "deleted" state of a cell, it must always hold a value.

Deleting one item is therefore done by moving all items behind the one you wish to delete one step forward (which is quite inefficient to do). The allocated size will still be the same though. So you'll need a counter variable to keep track of the actual data size used.

• Given an array int array[]={0,1,2,3,4,5};

• Then the number of items is sizeof array / sizeof *array;

  size_t items = sizeof array / sizeof *array;
  

  items will be the above mentioned counter variable.

• We wish to remove one item at a certain index:

  size_t index = 3;
  

• The size of the chunk behind the item you wish to remove is then expressed as:

  size_t size_to_move = (items-index-1) * sizeof *array;
  

  Which on a 32 bit computer is (6-3-1) * 4 = 8 bytes.

• We are moving data inside the same array, which means there are overlapping memory segments. In case of overlaps we can't use memcpy, so we have to used the specialized function memmove instead, which uses temporary buffers internally to deal with overlaps.

Complete example:

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

int main() 
{
  int array[]={0,1,2,3,4,5};
  size_t items = sizeof array / sizeof *array;
  size_t index = 3;
  size_t size_to_move = (items-index-1) * sizeof *array;
  
  memmove(&array[index], &array[index 1], size_to_move);
  items--;

  for(size_t i=0; i<items; i  )
  {
    printf("%d ", array[i]);
  }
}

Output:

0 1 2 4 5

Note that if we don't decrease the item counter with item--, we would get 0 1 2 4 5 5. The allocated array size remains 6 so we can still access the last item, and that one used to hold a 5, so it still contains it, because items aren't actually "moved" but copied.

CodePudding user response：

In C language, an array has a fixed size. That means that you can neither add nor remove elements to an array. You can only re-write them.

What is closest to an array of dynamic size is a dynamic array which can be obtained by malloc. It can later be resized by realloc but:

• the standard library if free to ignore any shrinking call and keep the array with its maximum size
• released memory can be returned to the operating system to be accessible to other processes or can remain stuck to the current process
• an extending call can involve a full copy of the existing elements

Reallocing dynamic arrays is indeed a common idiom in C language, but you must be aware of its limits an not abuse it. In your example it would be overkill.

Dynamic allocated memory has to be released by free. After calling free:

• the pointer keeps its previous value and is called a dangling pointer because it points to unallocated memory and dereferencing it explicitely invokes Undefined Behaviour (the hell for C programmers...)

• the implementation of the standard library is free to do what it wants with the released memory:

  • it can be returned to the Operating System
  • if can be recycled to become available to later malloc calls or even become no longer usable. The underlying algorithm used to manage the dynamic memory is not specified by the standard

That being said a common algorithm is to exchange pages of a certain size with the OS, and allocate memory for the program from those pages. The empty blocs are often handled as a list, and a new released bloc is concatenated with an adjacent free bloc to try to have as large blocs as possible. And only when a page is contained in a free bloc, it can be returned to the OS. But this is the problem of the implementer of the standard library, not the one of the C programmer.