Best way to remove from NSMutableArray while iterating?

Question

In Cocoa, if I want to loop through an NSMutableArray and remove multiple objects that fit a certain criteria, what's the best way to do this without restarting the loop each time I remove an object?

Thanks,

Edit: Just to clarify - I was looking for the best way, e.g. something more elegant than manually updating the index I'm at. For example in C++ I can do;

iterator it = someList.begin();

while (it != someList.end())
{
    if (shouldRemove(it))   
        it = someList.erase(it);
}

Onus

Loop from the back to the front. – Hejira

No one answer the "WHY" – Grinnell

@HotLicks One of my all-time favorites and the most underestimated solution in programming generally :D – Hopefully

Answer 1

For clarity I like to make an initial loop where I collect the items to delete. Then I delete them. Here's a sample using Objective-C 2.0 syntax:

NSMutableArray *discardedItems = [NSMutableArray array];

for (SomeObjectClass *item in originalArrayOfItems) {
    if ([item shouldBeDiscarded])
        [discardedItems addObject:item];
}

[originalArrayOfItems removeObjectsInArray:discardedItems];

Then there is no question about whether indices are being updated correctly, or other little bookkeeping details.

Edited to add:

It's been noted in other answers that the inverse formulation should be faster. i.e. If you iterate through the array and compose a new array of objects to keep, instead of objects to discard. That may be true (although what about the memory and processing cost of allocating a new array, and discarding the old one?) but even if it's faster it may not be as big a deal as it would be for a naive implementation, because NSArrays do not behave like "normal" arrays. They talk the talk but they walk a different walk. See a good analysis here:

The inverse formulation may be faster, but I've never needed to care whether it is, because the above formulation has always been fast enough for my needs.

For me the take-home message is to use whatever formulation is clearest to you. Optimize only if necessary. I personally find the above formulation clearest, which is why I use it. But if the inverse formulation is clearer to you, go for it.

Androcles

Beware that this could create bugs if objects are more than once in an array. As an alternative you could use an NSMutableIndexSet and -(void)removeObjectsAtIndexes. – Cummins

It actually is faster to do the inverse. The performance difference is pretty huge, but if your array isn't that big then the times are going to be trivial either way. – Soapwort

I used revers... made array as nil.. then only added what I wanted and reload data... done... created dummyArray which is mirror of main array so that we have main actual data – Escallop

Extra memory needs to be allocated to do inverse. It's not an in-place algorithm and not a good idea in some cases. When you remove directly you just shift the array (which is very efficient since it won't move one by one, it can shift a big chunk), but when you create a new array you need all the allocate and assignment. So if you only delete a few items, inverse will be much slower. It's a typical seems-right algorithm. – Chainman

Answer 2

One more variation. So you get readability and good performace:

NSMutableIndexSet *discardedItems = [NSMutableIndexSet indexSet];
SomeObjectClass *item;
NSUInteger index = 0;

for (item in originalArrayOfItems) {
    if ([item shouldBeDiscarded])
        [discardedItems addIndex:index];
    index++;
}

[originalArrayOfItems removeObjectsAtIndexes:discardedItems];

Pliocene

This is awesome. I was trying to remove multiple items from the array and this worked perfectly. Other methods were causing problems :) Thanks man – Furst

Corey, this answer (below) said that, removeObjectsAtIndexes is the worst method to remove the objects, are you agree with that? I am asking this because your answer is too old now. Still it be good to choose the best? – Anadromous

I like this solution very much in terms of readability. How is it in terms of performance when compared to @HotLicks answer? – Pellicle

This method should be definitely encouraged while deleting objects from array in Obj-C. – Heshum

enumerateObjectsUsingBlock: would get you the index increment for free. – Clerissa

Answer 3

This is a very simple problem. You just iterate backwards:

for (NSInteger i = array.count - 1; i >= 0; i--) {
   ElementType* element = array[i];
   if ([element shouldBeRemoved]) {
       [array removeObjectAtIndex:i];
   }
}

This is a very common pattern.

Hejira

would have missed Jens answer, cuz he didnt write out the code :P.. thnx m8 – Fordo

This is the best method. Important to remember that the iteration variable should be a signed one, despite that array indices in Objective-C are declared as unsigned (I can imagine how Apple regrets that now). – Froehlich

Answer 4

Some of the other answers would have poor performance on very large arrays, because methods like removeObject: and removeObjectsInArray: involve doing a linear search of the receiver, which is a waste because you already know where the object is. Also, any call to removeObjectAtIndex: will have to copy values from the index to the end of the array up by one slot at a time.

More efficient would be the following:

NSMutableArray *array = ...
NSMutableArray *itemsToKeep = [NSMutableArray arrayWithCapacity:[array count]];
for (id object in array) {
    if (! shouldRemove(object)) {
        [itemsToKeep addObject:object];
    }
}
[array setArray:itemsToKeep];

Because we set the capacity of itemsToKeep, we don't waste any time copying values during a resize. We don't modify the array in place, so we are free to use Fast Enumeration. Using setArray: to replace the contents of array with itemsToKeep will be efficient. Depending on your code, you could even replace the last line with:

[array release];
array = [itemsToKeep retain];

So there isn't even a need to copy values, only swap a pointer.

Vidicon

This algo proves good to be in terms of time complexity. I am trying to understand it in terms of space complexity. I have the same implementation going around where I set the capacity for 'itemsToKeep' with the actual 'Array count'. But say I don't want few objects from array so I don't add it to itemsToKeep. So that capacity of my itemsToKeep is 10, but I actually store only 6 objects in it. Does this mean I am wasting space of 4 objects? P.S. am not finding faults, just trying to understand the algo complexity. :) – Intersection

Yes, you have space reserved for four pointers that you are not using. Keep in mind the array only contains pointers, not the objects themselves, so for four objects that means 16 bytes (32 bit architecture) or 32 bytes (64 bit). – Vidicon

Note that any of the solutions are going to be at best require 0 additional space (you delete items in place) or at worst double the original array size (because you make a copy of the array). Again, because we are dealing with pointers and not full copies of objects, this is pretty cheap under most circumstances. – Vidicon

According to this post, the hint of the arrayWithCapacity: method about the size of the array is not actually being used. – Alexandriaalexandrian

@Alexandriaalexandrian On the road, yellow paint is powerless to stop oncoming traffic from entering your lane. But we use it all the same. – Vidicon

I am not advising against using arrayWithCapacity: as it is indeed helpful for understanding the code :) . What I am saying is that from what I understand, using it does not seem to prevent wasting time copying values during a resize as you suggested. – Alexandriaalexandrian

This is not a good solution. Allocate extra memory and do assignment are much slower than remove and shift array. – Chainman

Answer 5

You can use NSpredicate to remove items from your mutable array. This requires no for loops.

For example if you have an NSMutableArray of names, you can create a predicate like this one:

NSPredicate *caseInsensitiveBNames = 
[NSPredicate predicateWithFormat:@"SELF beginswith[c] 'b'"];

The following line will leave you with an array that contains only names starting with b.

[namesArray filterUsingPredicate:caseInsensitiveBNames];

If you have trouble creating the predicates you need, use this apple developer link.

Riotous

Requires no visible for loops. There is a loop in the filter operation, you just don't see it. – Hejira

Answer 6

I did a performance test using 4 different methods. Each test iterated through all elements in a 100,000 element array, and removed every 5th item. The results did not vary much with/ without optimization. These were done on an iPad 4:

(1) removeObjectAtIndex: -- 271 ms

(2) removeObjectsAtIndexes: -- 1010 ms (because building the index set takes ~700 ms; otherwise this is basically the same as calling removeObjectAtIndex: for each item)

(3) removeObjects: -- 326 ms

(4) make a new array with objects passing the test -- 17 ms

So, creating a new array is by far the fastest. The other methods are all comparable, except that using removeObjectsAtIndexes: will be worse with more items to remove, because of the time needed to build the index set.

Soapwort

Did you count the time to make a new array and deallocate it afterwards. I don't believe it can do that alone in 17 ms. Plus 75,000 assignment? – Chainman

The time needed to create and deallocate a new array is minimal – Soapwort

You apparently didn't measure the reverse loop scheme. – Hejira

The first test is equivalent to the reverse loop scheme. – Soapwort

what happens when you are left with your newArray, and your prevArray is Nulled? You'd have to copy the newArray to what the PrevArray was named to ( or rename it ) otherwise how would your other code reference it? – Riegel

Answer 7

Either use loop counting down over indices:

for (NSInteger i = array.count - 1; i >= 0; --i) {

or make a copy with the objects you want to keep.

In particular, do not use a for (id object in array) loop or NSEnumerator.

Borstal

you should write out your answer in code m8. haha almost missed it. – Fordo

This is not right. "for(id object in array)" is faster than "for (NSInteger i = array.count - 1; i >= 0; --i)", and is called fast iteration. Using iterator is definitely faster than indexing. – Chainman

@Chainman -- But if you remove an element out from under an iterator you usually create havoc. (And "fast iteration" is not always that much faster.) – Hejira

The answer is from 2008. Fast iteration did not exist. – Borstal

Answer 8

For iOS 4+ or OS X 10.6+, Apple added passingTest series of APIs in NSMutableArray, like – indexesOfObjectsPassingTest:. A solution with such API would be:

NSIndexSet *indexesToBeRemoved = [someList indexesOfObjectsPassingTest:
    ^BOOL(id obj, NSUInteger idx, BOOL *stop) {
    return [self shouldRemove:obj];
}];
[someList removeObjectsAtIndexes:indexesToBeRemoved];

Royall

Answer 9

Nowadays you can use reversed block-based enumeration. A simple example code:

NSMutableArray *array = [@[@{@"name": @"a", @"shouldDelete": @(YES)},
                           @{@"name": @"b", @"shouldDelete": @(NO)},
                           @{@"name": @"c", @"shouldDelete": @(YES)},
                           @{@"name": @"d", @"shouldDelete": @(NO)}] mutableCopy];

[array enumerateObjectsWithOptions:NSEnumerationReverse usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    if([obj[@"shouldDelete"] boolValue])
        [array removeObjectAtIndex:idx];
}];

Result:

(
    {
        name = b;
        shouldDelete = 0;
    },
    {
        name = d;
        shouldDelete = 0;
    }
)

---

another option with just one line of code:

[array filterUsingPredicate:[NSPredicate predicateWithFormat:@"shouldDelete == NO"]];

Bergstein

Is there any guarantee that array would not be reallocated? – Evesham

What do you mean with reallocation? – Bergstein

While removing element from linear structure it might be effective to allocate new contiguous memory block and move all elements there. In this case all pointers would be invalidated. – Evesham

As the deletion operation wouldn't know how many elements will bet deleted at the end, it wold not make sense to do so during removal. Anyway: implementation detail, w have to trust apple to write reasonable code. – Bergstein

First is not nicer (because you have to think to much about how it works in the first place) and second is not refactoring safe. So in the end I ended with classic accepted solution that is quite readable actually. – Behan

@ReneDohan I have no idea what you mean with “refactoring safe”. And „thinking too much“ is a very personal experience that depends on personal capacities. – Bergstein

@Bergstein 1 "refactoring safe" means that I use objective c editor that can do safe refactorings like rename change signature etc and if I use something like this "obj[@"shouldDelete"]" it will just confuse editor because to rename correctly it has to search for strings and I have to be more careful to not introduce bugs by refactoring if I use constructs like this that are unsafe. 2 "Thinking to much is not so personal" its alway better to write your code most simple and understandable way possible and save your memory and energy for important difficult parts and app logic. – Behan

@ReneDohan: if you write must understandable code, you would just write your code from top to bottom. But code reusability, testability and maintainability requires modular code that you can stick together, exchange and put into libraries. This is not possible without some indirections. Also you seem to have a problem with enumeration. It is preferable as it eliminates several problems that might occur in simple for looping. Also subscripting is a valid and easy to understand language syntax. If you don’t use it because of refactoring, maybe you are refactoring too often. – Bergstein

Answer 10

In a more declarative way, depending on the criteria matching the items to remove you could use:

[theArray filterUsingPredicate:aPredicate]

@Nathan should be very efficient

Yeoman

Answer 11

Here's the easy and clean way. I like to duplicate my array right in the fast enumeration call:

for (LineItem *item in [NSArray arrayWithArray:self.lineItems]) 
{
    if ([item.toBeRemoved boolValue] == YES) 
    {
        [self.lineItems removeObject:item];
    }
}

This way you enumerate through a copy of the array being deleted from, both holding the same objects. An NSArray holds object pointers only so this is totally fine memory/performance wise.

Taite

Or even simpler - for (LineItem *item in self.lineItems.copy) – Fawn

Answer 12

this should do it:

    NSMutableArray* myArray = ....;

    int i;
    for(i=0; i<[myArray count]; i++) {
        id element = [myArray objectAtIndex:i];
        if(element == ...) {
            [myArray removeObjectAtIndex:i];
            i--;
        }
    }

hope this helps...

Leisha

Although unorthodox, I've found iterating backwards and deleting as I go to be a clean and simple solution. Usually one of the fastest methods as well. – Melodymeloid

What's wrong with this? It's clean, fast, easily readable, and it works like a charm. To me it looks like the best answer. Why does it have a negative score? Am I missing something here? – Unsheathe

@Steph: The question states "something more elegant than manually updating the index." – Needy

oh. I had missed the I-absolutely-don't-want-to-update-the-index-manually part. thanks steve. IMO this solution is more elegant than the one chosen (no temporary array needed), so negative votes against it feel unfair. – Unsheathe

@Steve: If you check the edits, that part was added after I have submitted my answer.... if not, I would have replied with "Iterating backwards IS the most elegant solution" :). Have a nice day! – Leisha

This gets my vote, too. I don't think using a much more inefficient method is warranted to avoid the "complexity" of this one. – Fencesitter

Answer 13

Add the objects you want to remove to a second array and, after the loop, use -removeObjectsInArray:.

Pitchy

Answer 14

Why don't you add the objects to be removed to another NSMutableArray. When you are finished iterating, you can remove the objects that you have collected.

Castaneda

Answer 15

How about swapping the elements you want to delete with the 'n'th element, 'n-1'th element and so on?

When you're done you resize the array to 'previous size - number of swaps'

Voltz

Answer 16

If all objects in your array are unique or you want to remove all occurrences of an object when found, you could fast enumerate on an array copy and use [NSMutableArray removeObject:] to remove the object from the original.

NSMutableArray *myArray;
NSArray *myArrayCopy = [NSArray arrayWithArray:myArray];

for (NSObject *anObject in myArrayCopy) {
    if (shouldRemove(anObject)) {
        [myArray removeObject:anObject];
    }
}

Bannockburn

what happens if original myArray gets updated while +arrayWithArrayis being executed? – Bartie

@bioffe: Then you have a bug in your code. NSMutableArray is not thread-safe, you are expected to control access via locks. See this answer – Uninterrupted

Answer 17

benzado's anwser above is what you should do for preformace. In one of my applications removeObjectsInArray took a running time of 1 minute, just adding to a new array took .023 seconds.

Hyder

Answer 18

I define a category that lets me filter using a block, like this:

@implementation NSMutableArray (Filtering)

- (void)filterUsingTest:(BOOL (^)(id obj, NSUInteger idx))predicate {
    NSMutableIndexSet *indexesFailingTest = [[NSMutableIndexSet alloc] init];

    NSUInteger index = 0;
    for (id object in self) {
        if (!predicate(object, index)) {
            [indexesFailingTest addIndex:index];
        }
        ++index;
    }
    [self removeObjectsAtIndexes:indexesFailingTest];

    [indexesFailingTest release];
}

@end

which can then be used like this:

[myMutableArray filterUsingTest:^BOOL(id obj, NSUInteger idx) {
    return [self doIWantToKeepThisObject:obj atIndex:idx];
}];

Muriate

Answer 19

A nicer implementation could be to use the category method below on NSMutableArray.

@implementation NSMutableArray(BMCommons)

- (void)removeObjectsWithPredicate:(BOOL (^)(id obj))predicate {
    if (predicate != nil) {
        NSMutableArray *newArray = [[NSMutableArray alloc] initWithCapacity:self.count];
        for (id obj in self) {
            BOOL shouldRemove = predicate(obj);
            if (!shouldRemove) {
                [newArray addObject:obj];
            }
        }
        [self setArray:newArray];
    }
}

@end

The predicate block can be implemented to do processing on each object in the array. If the predicate returns true the object is removed.

An example for a date array to remove all dates that lie in the past:

NSMutableArray *dates = ...;
[dates removeObjectsWithPredicate:^BOOL(id obj) {
    NSDate *date = (NSDate *)obj;
    return [date timeIntervalSinceNow] < 0;
}];

Sardanapalus

Answer 20

Iterating backwards-ly was my favourite for years , but for a long time I never encountered the case where the 'deepest' ( highest count) object was removed first. Momentarily before the pointer moves on to the next index there ain't anything and it crashes.

Benzado's way is the closest to what i do now but I never realised there would be the stack reshuffle after every remove.

under Xcode 6 this works

NSMutableArray *itemsToKeep = [NSMutableArray arrayWithCapacity:[array count]];

    for (id object in array)
    {
        if ( [object isNotEqualTo:@"whatever"]) {
           [itemsToKeep addObject:object ];
        }
    }
    array = nil;
    array = [[NSMutableArray alloc]initWithArray:itemsToKeep];

Riegel