Removing item from array by property value

Question

I'm looking for the most efficient and memory friendly way.

Let's say I have an array of Person objects. Each person has a hair color represented by an NSString. Let's then say I want to remove all Person objects from the array where their hair color is brown.

How do I do this?

Keep in mind that you cannot remove an object from an array that is being enumerated upon.

Answer 1

There are two general approaches. We can test each element and then immediately remove the element if it meets the test criteria, or we can test each element and store the indexes of elements meeting the test criteria, and then remove all such elements at once. With memory usage a real concern, the storage requirements for the latter approach may render it undesirable.

With the "store all indexes to remove, then remove them" approach off the table, we need to consider the details involved in the former approach, and how they will effect the correctness and speed of the approach. There are two fatal errors waiting in this approach. The first is to remove the evaluated object not based on its index in the array, but rather with the removeObject: method. removeObject: does a linear search of the array to find the object to remove. With a large, unsorted data set, this will destroy our performance as the time increases with the square of the input size. By the way, using indexOfObject: and then removeObjectAtIndex: is just as bad, so we should avoid it also. The second fatal error would be starting our iteration at index 0. NSMutableArray rearranges the indexes after adding or removing an object, so if we start with index 0, we'll be guaranteed an index out of bounds exception if even one object is removed during the iteration. So, we have to start from the back of the array, and only remove objects that have lower indexes than every index we've checked so far.

Having laid that out, there's really two obvious choices: a for loop that starts at the end rather than the beginning of the array, or the NSArray method enumerateObjectsWithOptions:usingBlock: method. Examples of each follow:

[persons enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(Person *p, NSUInteger index, BOOL *stop) {
    if ([p.hairColor isEqualToString:@"brown"]) {
        [persons removeObjectAtIndex:index];
    }
}];

NSInteger count = [persons count];
for (NSInteger index = (count - 1); index >= 0; index--) {
    Person *p = persons[index];
    if ([p.hairColor isEqualToString:@"brown"]) {
        [persons removeObjectAtIndex:index];
    }
}

My tests seem to show the for loop marginally faster - maybe about a quarter second faster for 500,000 elements, which is a difference between 8.5 and 8.25 seconds, basically. So I would suggest using the block approach, as it's safer and feels more idiomatic.