for loop iterations in c++

Question

I'm building a simple list using a dynamically allocated array in C++. I have a function remove(int item) that should remove all occurrences of item in the list. However, if I make a loop that iterates from 0 to length in the array, I'm worried I will exceed the boundaries of my array because length changes as I delete items:

int List::pop(int index)
{
  int retval = data[index];
  for (int i = index; i < length; i++)
    data[i] = data[i+1];
  length--;
  return retval;
}

void List::remove(int item)
{
  for (int i = 0; i < length; i++) {
    if (data[i] == item)
      pop(i);
}

So, if I called remove(6) on array[6][4][2][6][1][3][5][6], would C++ update the for loop in remove() with the updated value of length after a pop()? Or would it remain the same value that was originally passed to it when remove() was called?

Answer 1

Another solution would be to search the reverse. Only keep those which are not equal to the item to be removed.

void List::remove(int item)
{
    int insert = 0;
    for (int i = 0; i < length; i++) {
        if (data[i] != item)
          data[insert++] = data[i];
    }
    length = insert;
}

Answer 2

Start at the end of the array and work backwards to the start position. Alternatively, call pop(i--) instead of pop(i). This backs up i so you don't skip any elements of the list (including the last item).

The advantage of the first method is that you don't waste time shifting down elements that are eventually going to be removed.

Answer 3

The conditional expression i < length is evaluated in it's entirety before every iteration of the loop. The C++ compiler will not cache i nor will it cache length for this evaluation. So long as the length variable is properly updated this expression won't allow i to be beyond the bounds of the array.

This won't help with the skipping elements problem though. To do that I would switch to a while loop.

int i = 0;
while (i < length) {
  if (data[i] == item) {
    pop(i);
  } else {
    i++;
  }
}

In this case we don't increment if we pop an item. This way the index remains in the same place and will be able to catch duplicate items which appear next to each other in the array