Ruby didn't loop all elements?

Question

I am trying to remove all 7s from an array:

a = [1,2,3,4,5,7,7,7,7,7,7,7,7,7,9,10,11,12,13]

I did:

a.each_with_index do |item, index|
  if item == 7
    a.delete_at(index)
  end
end
a # => [1, 2, 3, 4, 5, 7, 7, 7, 7, 9, 10, 11, 12, 13]  

How did this happen?

Answer 1

The fact that only about half (5/9) of your items have disappeared is a dead giveaway that the problem is deleting while iterating over the collection.

The iteration will be processing indexes 1, 2, 3, 4 and so on. If you delete index 2 while processing it, that will shift all later indexes down by one.

So, when you then move on to index 3 in the next iteration, you will skip the original index 3 because that will have been shifted down to index 2.

In other words, let's start with a simpler example with two consecutive items to remove:

index | 0 | 1 | 2 | 3 |
value | 1 | 7 | 7 | 9 |

You check the first index and the value is 1 so you do nothing. You then check the second index and the value is 7 so you delete it, giving:

index | 0 | 1 | 2 |
value | 1 | 7 | 9 |

You then check the third index and the value is 9 so you do nothing. You've also reached the end so it stops.

So you can see there that you actually skipped the second item you wanted to delete, because you shifted things around while iterating. This isn't a Ruby-specific problem, a great many languages have this same issue.

In general, each complete pair of adjacent items will only have the first of the pair deleted while an item on its own (not followed by another of the same value) will be deleted normally. That's why only 5/9 of your 7s are deleted, one for each of the four pairs and the final standalone one.

The correct way (in Ruby) to delete all items of a single given value is to use the array delete method:

a.delete(7)

You can also use conditional delete for more complex conditions such as deleting everything greater than 7:

a.delete_if {|val| val > 7}

---

And, if you really want to do it yourself (as an educational exercise), you just have to realise that the problem is because you process the array in a forward manner - when you do that, changes beyond where you're deleting may cause issues.

If you were to find some way to process the array in a backwards manner, this issue would not occur. Luckily, Ruby has such a beast:

a.to_enum.with_index.reverse_each do |item, index|

That line will process the array in such a way that deletions will not affect future operations. Just be aware that deleting while iterating can still be a problem if the data structure you're processing is not a simple indexed array.

I still warrant that delete and delete_if are the correct way to go since they're baked into Ruby already, and therefore incredibly unlikely to have bugs.