在迭代时从NSMutableArray中删除元素的最佳方法是什么?

199
在Cocoa中,如果我想循环遍历NSMutableArray并删除符合特定条件的多个对象,那么在每次删除对象时不重启循环,最好的方法是什么?
谢谢。编辑:只是为了澄清-我正在寻找最好的方法,例如比手动更新我的索引更优雅的方法。例如,在C++中我可以这样做;
iterator it = someList.begin();

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

9
从后往前循环。 - Hot Licks
没有人回答“为什么”的问题。 - onmyway133
1
@HotLicks 是我所有时间里最喜欢的,也是编程中最被低估的解决方案之一 :D - Julian F. Weinert
20个回答

392

为了清晰明了,我喜欢先创建一个循环来收集要删除的项。然后再进行删除。以下是使用Objective-C 2.0语法的示例:

NSMutableArray *discardedItems = [NSMutableArray array];

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

[originalArrayOfItems removeObjectsInArray:discardedItems];

那么就不存在关于索引是否被正确更新或其他小细节的问题了。

编辑添加:

在其他答案中已经指出,逆向公式应该更快。即,如果你遍历数组并组成一个新的要保留的对象数组,而不是要丢弃的对象数组。这可能是正确的(虽然分配新数组和丢弃旧数组的内存和处理成本又该如何?),但即使它更快,也可能不像对于一个简单的实现那样重要,因为NSArray不像“普通”的数组一样行动。它们说了一套话,但它们走的是不同的路线。在此处查看良好的分析:

逆向公式可能会更快,但我从未需要关心它是否更快,因为上述公式总是足够快,满足我的需求。

对我来说,重要的是使用对自己最清晰的公式。仅在必要时进行优化。我个人发现上述公式最清晰,所以我使用它。但如果逆向公式对您更清晰,请使用它。


48
请注意,如果对象在数组中出现多次,则可能会导致Bug。作为替代方案,您可以使用NSMutableIndexSet和-(void)removeObjectsAtIndexes方法。 - Georg Schölly
1
实际上,执行反向操作会更快。性能差异非常大,但如果您的数组不是很大,那么无论哪种方式时间都将微不足道。 - user1032657
我使用了reverse函数来翻转数组,然后将数组设置为nil。接着只添加我想要的内容并重新加载数据...完成了... 创建了dummyArray,它是主数组的镜像,以便我们拥有主要的实际数据 - Fahim Parkar
需要分配额外的内存来执行反转操作。这不是一个原地算法,在某些情况下也不是一个好主意。当您直接删除时,只需移动数组(非常高效,因为它不会逐个移动,可以移动大块),但是当您创建新数组时,需要分配和赋值所有内容。因此,如果您只删除了几个项目,则反转速度将变慢。这是一个典型的看起来正确的算法。 - jack

83

还有一种变体。这样您就可以获得可读性和良好的性能:

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

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

[originalArrayOfItems removeObjectsAtIndexes:discardedItems];

太棒了!我一直在尝试从数组中删除多个项目,这个方法完美地解决了我的问题。其他方法都会引起麻烦 :) 谢谢你! - AbhinavVinay
Corey,这个答案(下面)说removeObjectsAtIndexes是最差的删除对象的方法,你同意吗?我问这个问题是因为你的回答现在有点旧了。选择最好的仍然是明智的吗? - Hemang
我非常喜欢这个解决方案的可读性。与@HotLicks的答案相比,在性能方面如何? - Victor Maia Aldecôa
在 Obj-C 中删除数组对象时,应该明确鼓励使用这种方法。 - boreas
使用 enumerateObjectsUsingBlock: 方法可以免费获得索引增量。 - pkamb

49

这是一个非常简单的问题。你只需要反向迭代:

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

这是一个非常常见的模式。


我本来会错过Jens的答案,因为他没有写出代码:P..谢谢啊朋友。 - Just a coder
3
这是最好的方法。重要的是记住迭代变量应该是有符号的,尽管在Objective-C中声明数组索引为无符号的(我可以想象苹果公司现在后悔了)。 - mojuba

40

其他答案中的一些方法在处理大型数组时性能较差,因为像removeObject:removeObjectsInArray:这样的方法需要对接收器进行线性搜索,这是一种浪费,因为您已经知道对象在哪里。此外,任何对removeObjectAtIndex:的调用都必须逐个将索引到数组末尾的值复制到上一个插槽中。

更高效的方法如下:

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

由于我们设置了itemsToKeep的容量,因此在调整大小期间不会浪费任何时间复制值。 我们不会直接修改数组,因此可以自由使用快速枚举。 使用setArray:array的内容替换为itemsToKeep将是高效的。 根据您的代码,甚至可以将最后一行替换为:

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

因此,甚至无需复制值,只需交换指针。


是的,你有为四个指针保留的空间,但你没有使用它们。请记住,该数组仅包含指针,而不是对象本身,因此对于四个对象,这意味着16字节(32位架构)或32字节(64位)。 - benzado
根据这篇文章,arrayWithCapacity:方法中关于数组大小的提示实际上并没有被使用。 - Kremk
@Kremk 在路上,黄色的涂料无法阻止对向车辆进入你的车道。但我们仍然使用它。 - benzado
我并不建议不使用arrayWithCapacity:,因为它确实有助于理解代码 :)。我的意思是,从我的理解来看,使用它似乎并不能防止在调整大小时浪费时间复制值,就像你所建议的那样。 - Kremk
这不是一个好的解决方案。分配额外的内存并进行赋值比删除和移动数组要慢得多。 - jack
显示剩余3条评论

28

你可以使用NSPredicate从可变数组中删除项目,这不需要使用for循环。

例如,如果你有一个名为names的NSMutableArray,你可以创建一个像下面这样的谓词:

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

以下代码将返回一个只包含以字母 b 开头的名字的数组。

[namesArray filterUsingPredicate:caseInsensitiveBNames];

如果您在创建所需的谓词时遇到问题,请使用此苹果开发者链接

3
不需要明显的for循环。在过滤操作中有一个循环,只是你看不到它。 - Hot Licks

19

我使用了4种不同的方法进行性能测试。每个测试都遍历了一个包含100,000个元素的数组中的所有元素,并且删除了其中每5个元素。无论是否进行了优化,结果并没有太大差别。这些测试是在iPad 4上完成的:

(1) removeObjectAtIndex: -- 271毫秒

(2) removeObjectsAtIndexes: -- 1010毫秒(因为构建索引集需要约700毫秒;否则,这基本上与每个项目单独调用removeObjectAtIndex:相同)

(3) removeObjects: -- 326毫秒

(4) 创建一个由通过测试的对象组成的新数组 -- 17毫秒

因此,创建一个新数组远比其他方法快。其他方法都是可比较的,除了使用removeObjectsAtIndexes:将随着要删除的项目数量的增加而变得更劣,因为需要构建索引集所需的时间会更长。


1
你有计算创建新数组和之后释放它所需的时间吗?我不相信仅靠17毫秒就能完成。再加上75000次赋值? - jack
创建和释放新数组所需的时间是最小的。 - user1032657
显然你没有测量反向循环方案。 - Hot Licks
第一个测试等同于反向循环方案。 - user1032657
当您只剩下新数组(newArray),而旧数组(prevArray)被置空时会发生什么?您必须将新数组复制到旧数组原来的名称(或重命名),否则您的其他代码如何引用它? - aremvee

17

可以使用循环下标倒序遍历:

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

或者使用拷贝来保留你所需的对象。

特别注意,不要使用for (id object in array)循环或NSEnumerator


3
你应该用代码写出你的答案,m8。哈哈,差点错过了它。 - Just a coder
这不对。"for(id object in array)"比"for (NSInteger i = array.count - 1; i >= 0; --i)"更快,被称为快速迭代。使用迭代器比索引肯定更快。 - jack
@jack -- 但是如果你在迭代器下面移除一个元素,通常会造成混乱。(而且“快速迭代”并不总是更快。) - Hot Licks
答案来自2008年。快速迭代并不存在。 - Jens Ayton

13

在iOS 4+或OS X 10.6+上,苹果公司在NSMutableArray中添加了一系列passingTest API,例如– indexesOfObjectsPassingTest:。使用此类API的解决方案如下:

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

12

现在可以使用反向块枚举。以下是一个简单的示例代码:

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

结果:

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

只需一行代码的另一个选项:

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

数组不会被重新分配的保证吗? - Cfr
你说的“reallocation”是什么意思? - vikingosegundo
在从线性结构中删除元素时,分配新的连续内存块并将所有元素移动到那里可能是有效的。在这种情况下,所有指针都将失效。 - Cfr
由于删除操作无法知道最终将删除多少个元素,因此在移除期间这样做是没有意义的。无论如何:实现细节,我们必须相信苹果编写合理的代码。 - vikingosegundo
如果你想写易懂的代码,那么你只需要按照从上到下的顺序编写代码。但是,为了实现代码的可重用性、可测试性和可维护性,需要编写模块化的代码,这样可以将它们组合在一起、交换并放入库中。这是不可能没有一些间接性的。此外,你似乎对枚举有问题。使用枚举更好,因为它消除了在简单的for循环中可能出现的几个问题。此外,下标是一种有效且易于理解的语言语法。如果你因为重构而不使用它,那么你可能重构得太频繁了。 - vikingosegundo
显示剩余3条评论

8

更为声明式的方式是,根据匹配要移除的项的条件,您可以使用以下方法:

[theArray filterUsingPredicate:aPredicate]

@Nathan应该非常高效


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接