How to remove every second value from a C++ array without making a copy of the array?

Question

Problem: I want to get an array A[6] = {6, 5, 4, 3, 2, 1} to be A[6] = {5, 3, 1, 1, 1, 1}. In other words - "delete" every second value starting with 0th and shift all other values to the left.

My Attempt:

To do that I would use this code, where a - length of the relevant part of an array A (the part with elements that are not deleted), ind - index of the value that I want to delete.

for (int j = ind; j < n; j++)
    A[j] = A[j+1];

However, I couldn't get this to work, using the code like that:

void deleting(int A[], int& a, int ind){
    for (int j = ind; j < a; j++)
        A[j] = A[j+1];

    a--;
}

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

for (int i = 0; i < a; i+=2)
    deleting(A, a, i);

After running this code I was getting A[6] = {5, 4, 2, 1, 1507485184, 1507485184}. So, it deleted the elements at indexes 0, 3. Why did it delete the 3rd index?

Answer 1

There are two ways to do this:

1. walk the array, copying the last n-i elements forward one place for every even i, or

2. figure out the eventual state and just go straight to that. The eventual state is the first n/2 places are array[i]=array[2*i + 1], and the last n/2 places are just copies of the last element.

The first method is what you asked for, but it does multiple redundant copy operations, which the second avoids.

As for your implementation problems, examine what happens when j=n-1, and remember A[n] is not a valid element of the array. I suggest making the copy-everything-forward operation its own function anyway (or you can just use memcpy)

Answer 2

For these kinds of problems (in-place array manipulation), it's a good idea to just keep an index or pointer into the array for where you are "reading" and another where you are "writing." For example:

void odds(int* a, size_t len) {
  int* writep = a;
  int* readp = a + 1;
  while (readp < a + len) { // copy odd elements forward
    *writep++ = *readp;
    readp += 2;
  }
  while (writep < a + len - 1) { // replace rest with last
    *writep++ = a[len - 1];
  }
}