CODEWITHSUNDEEP
c++arrays
Andrew
Andrew

Reputation: 1071

for loop iterations in c++

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?

Upvotes: 2

Views: 359

Answers (3)

jfs
jfs

Reputation: 16798

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;
}

Upvotes: 3

JaredPar
JaredPar

Reputation: 755397

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

Upvotes: 2

Ted Hopp
Ted Hopp

Reputation: 234857

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.

Upvotes: 2

Related Questions