Лучший способ удалить из NSMutableArray во время итерации?

В Какао, если я хочу перебрать NSMutableArray и удалить несколько объектов, которые соответствуют определенным критериям, каков наилучший способ сделать это без перезапуска цикла каждый раз, когда я удаляю объект?

Спасибо,

Изменить: Просто чтобы уточнить - я искал лучший способ, например, что-то более элегантное, чем обновление индекса вручную, в котором я нахожусь. Например, в C ++ я могу сделать;

iterator it = someList.begin();

while (it != someList.end())
{
    if (shouldRemove(it))   
        it = someList.erase(it);
}
21.09.2008 19:43:20
Петля от задней части к передней.
Hot Licks 27.08.2013 04:16:44
Никто не отвечает на вопрос «ПОЧЕМУ»
onmyway133 10.09.2014 08:41:18
@HotLicks Один из моих самых любимых и самых недооцененных решений в программировании в целом: D
Julian F. Weinert 6.07.2015 14:37:46
20 ОТВЕТОВ
РЕШЕНИЕ

Для ясности я хотел бы сделать начальный цикл, где я собираю элементы для удаления. Затем я удаляю их. Вот пример с использованием синтаксиса Objective-C 2.0:

NSMutableArray *discardedItems = [NSMutableArray array];

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

[originalArrayOfItems removeObjectsInArray:discardedItems];

Тогда не возникает вопроса о том, правильно ли обновляются индексы, или о других небольших бухгалтерских деталях.

Отредактировано, чтобы добавить:

В других ответах было отмечено, что обратная формулировка должна быть быстрее. т.е. если вы перебираете массив и создаете новый массив объектов для хранения, а не объектов для отбрасывания. Это может быть правдой (хотя как насчет затрат на память и обработку при выделении нового массива и отбрасывании старого?), Но даже если он быстрее, он может оказаться не таким уж большим, как для наивной реализации, потому что NSArrays не ведите себя как "нормальные" массивы. Они говорят, говорят, но ходят по-другому. Смотрите хороший анализ здесь:

Обратная формулировка может быть быстрее, но мне никогда не нужно было заботиться о том, так ли это, потому что приведенная выше формулировка всегда была достаточно быстрой для моих нужд.

Для меня главная идея - использовать любую формулировку, которая вам наиболее понятна. Оптимизируйте только при необходимости. Я лично считаю вышеупомянутую формулировку более ясной, поэтому я использую ее. Но если обратная формулировка вам понятнее, сделайте это.

387
21.06.2018 02:33:51
Помните, что это может привести к ошибкам, если объекты находятся в массиве более одного раза. В качестве альтернативы вы можете использовать NSMutableIndexSet и - (void) removeObjectsAtIndexes.
Georg Schölly 19.06.2009 20:47:15
Это на самом деле быстрее сделать обратное. Разница в производительности довольно велика, но если ваш массив не такой большой, тогда время будет тривиальным в любом случае.
user1032657 3.06.2013 21:16:34
Я использовал revers ... made array как nil ... затем только добавил то, что хотел, и перезагрузил данные ... done ... создал dummyArray, который является зеркалом основного массива, чтобы у нас были основные фактические данные
Fahim Parkar 13.11.2013 11:45:10
Дополнительная память должна быть выделена для обратного. Это не алгоритм на месте и в некоторых случаях не очень хорошая идея. Когда вы удаляете напрямую, вы просто сдвигаете массив (что очень эффективно, поскольку он не перемещается один за другим, он может сдвигать большой кусок), но когда вы создаете новый массив, вам нужны все выделения и присваивания. Так что, если вы удалите только несколько элементов, обратное будет намного медленнее. Это типичный, кажется, правильный алгоритм.
jack 17.09.2014 07:05:36

Добавьте объекты, которые вы хотите удалить, во второй массив и после цикла используйте -removeObjectsInArray :.

5
21.09.2008 19:50:41

Почему бы вам не добавить объекты для удаления в другой NSMutableArray. Когда вы закончите итерацию, вы можете удалить объекты, которые вы собрали.

1
21.09.2008 19:51:40

Либо используйте цикл обратного отсчета по индексам:

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

или сделайте копию с объектами, которые вы хотите сохранить.

В частности, не используйте for (id object in array)цикл или NSEnumerator.

17
21.08.2018 20:22:28
Вы должны написать свой ответ в коде m8. хаха почти пропустил это.
FlowUI. SimpleUITesting.com 1.10.2013 23:33:58
Это неправильно. «for (идентификатор объекта в массиве)» быстрее, чем «for (NSInteger i = array.count - 1; i> = 0; --i)», и называется быстрой итерацией. Использование итератора определенно быстрее, чем индексирование.
jack 17.09.2014 07:31:58
@jack - Но если вы удаляете элемент из-под итератора, вы обычно создаете хаос. (И «быстрая итерация» не всегда намного быстрее.)
Hot Licks 17.09.2014 15:45:17
Ответ с 2008 года. Быстрых итераций не было.
Jens Ayton 22.09.2014 16:13:42

это должно сделать это:

    NSMutableArray* myArray = ....;

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

надеюсь это поможет...

5
21.09.2008 19:55:11
Несмотря на то, что это неортодоксально, я обнаружил, что итерация в обратном направлении и удаление по мере того, как я иду, является чистым и простым решением. Обычно один из самых быстрых методов.
rpetrich 1.08.2009 07:03:44
Что с этим не так? Он чистый, быстрый, легко читаемый и работает как шарм. Для меня это выглядит как лучший ответ. Почему у него отрицательный счет? Я что-то здесь упускаю?
Steph Thirion 20.12.2009 18:29:47
@Steph: в вопросе говорится «что-то более элегантное, чем обновление индекса вручную».
Steve Madsen 11.05.2010 16:45:39
ой. Я пропустил часть "я абсолютно не хочу обновлять индекс вручную". спасибо Стив. По моему мнению, это решение более элегантно, чем выбранное (временный массив не требуется), поэтому отрицательные голоса против него кажутся несправедливыми.
Steph Thirion 12.05.2010 19:16:39
@Steve: Если вы проверяете изменения, эта часть была добавлена ​​после того, как я отправил свой ответ ... если нет, я бы ответил «Итерация назад - это самое элегантное решение» :). Хорошего дня!
Pokot0 1.06.2010 15:16:51

В более декларативной форме, в зависимости от критериев, соответствующих удаляемым элементам, вы можете использовать:

[theArray filterUsingPredicate:aPredicate]

@ Натан должен быть очень эффективным

8
28.01.2015 14:03:27

Как насчет замены элементов, которые вы хотите удалить, на «n'th element», «n-1» и т. Д.?

Когда вы закончите, вы измените размер массива на «предыдущий размер - количество свопов»

1
21.09.2008 21:12:19

Если все объекты в вашем массиве уникальны или вы хотите удалить все вхождения объекта при его обнаружении, вы можете быстро перечислить копию массива и использовать [NSMutableArray removeObject:], чтобы удалить объект из оригинала.

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

for (NSObject *anObject in myArrayCopy) {
    if (shouldRemove(anObject)) {
        [myArray removeObject:anObject];
    }
}
1
22.09.2008 05:06:19
что произойдет, если исходный myArray будет обновлен во +arrayWithArrayвремя выполнения?
bioffe 16.03.2011 19:01:30
@bioffe: Тогда у вас есть ошибка в вашем коде. NSMutableArray не является потокобезопасным, ожидается, что вы будете контролировать доступ через блокировки. Смотрите этот ответ
dreamlax 28.08.2013 03:52:42

Некоторые из других ответов будут иметь плохую производительность на очень больших массивах, потому что такие методы, как 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];

Таким образом, нет даже необходимости копировать значения, а только менять указатель.

39
24.09.2008 08:51:49
Этот алгоритм оказывается хорошим с точки зрения сложности времени. Я пытаюсь понять это с точки зрения сложности пространства. У меня та же реализация, где я установил емкость для itemsToKeep с фактическим значением «Array count». Но, скажем, я не хочу мало объектов из массива, поэтому я не добавляю его в itemsToKeep. Так что емкость моего itemsToKeep равна 10, но я на самом деле храню только 6 объектов. Значит ли это, что я трачу пространство на 4 объекта? PS Я не нахожу ошибки, просто пытаюсь понять сложность алгоритма. :)
tech_human 7.01.2014 20:30:45
Да, у вас есть место для четырех указателей, которые вы не используете. Имейте в виду, что массив содержит только указатели, а не сами объекты, поэтому для четырех объектов это означает 16 байтов (32-битная архитектура) или 32 байта (64-битных).
benzado 8.01.2014 21:01:41
Обратите внимание, что любое из решений в лучшем случае потребует 0 дополнительных пробелов (вы удаляете элементы на месте) или в худшем случае удваивает исходный размер массива (потому что вы делаете копию массива). Опять же, поскольку мы имеем дело с указателями, а не с полными копиями объектов, в большинстве случаев это довольно дешево.
benzado 8.01.2014 21:03:14
Хорошо, понял. Спасибо, Бензадо!
tech_human 9.01.2014 19:24:23
Согласно этому сообщению, подсказка arrayWithCapacity: метод о размере массива фактически не используется.
Kremk 27.01.2014 00:03:15

Вы можете использовать NSpredicate для удаления элементов из вашего изменяемого массива. Это не требует петель.

Например, если у вас есть NSMutableArray из имен, вы можете создать предикат, подобный этому:

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

Следующая строка оставит вас с массивом, который содержит только имена, начинающиеся с b.

[namesArray filterUsingPredicate:caseInsensitiveBNames];

Если у вас возникли проблемы с созданием необходимых предикатов, воспользуйтесь этой ссылкой для разработчиков Apple .

28
24.09.2008 20:59:56
Не требует видимых петель. В работе фильтра есть цикл, вы просто его не видите.
Hot Licks 16.04.2015 16:26:25

Еще один вариант. Таким образом, вы получите удобочитаемость и хорошую производительность:

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

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

[originalArrayOfItems removeObjectsAtIndexes:discardedItems];
82
19.06.2009 20:33:29
Это круто. Я пытался удалить несколько элементов из массива, и это сработало отлично. Другие методы вызывали проблемы :) Спасибо, мужчина
AbhinavVinay 12.03.2013 07:15:55
Кори, этот ответ (ниже) сказал, что removeObjectsAtIndexesэто худший метод удаления объектов, вы согласны с этим? Я спрашиваю об этом, потому что ваш ответ сейчас слишком стар. Все-таки хорошо бы выбрать лучшее?
Hemang 3.07.2013 07:48:03
Мне очень нравится это решение с точки зрения читабельности. Как это с точки зрения производительности по сравнению с ответом @HotLicks?
Victor Maia Aldecôa 27.01.2014 23:00:57
Этот метод обязательно следует поощрять при удалении объектов из массива в Obj-C.
boreas 12.05.2016 15:57:55
enumerateObjectsUsingBlock:получил бы прирост индекса бесплатно.
pkamb 21.08.2018 20:10:20

Ответ Бензадо выше - это то, что вы должны сделать для преформирования. В одном из моих приложений метод removeObjectsInArray занял 1 минуту, просто добавление в новый массив заняло 0,023 секунды.

1
17.06.2010 21:31:00

Я определяю категорию, которая позволяет мне фильтровать, используя блок, например так:

@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

который затем можно использовать так:

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

Для iOS 4+ или OS X 10.6+ Apple добавила passingTestсерию API-интерфейсов NSMutableArray, например – indexesOfObjectsPassingTest:. Решение с таким API будет:

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

Я сделал тест производительности, используя 4 разных метода. Каждый тест повторял все элементы в массиве из 100 000 элементов и удалял каждый 5-й элемент. Результаты не сильно изменились с / без оптимизации. Это было сделано на iPad 4:

(1) removeObjectAtIndex:- 271 мс

(2) removeObjectsAtIndexes:- 1010 мс (поскольку создание набора индексов занимает ~ 700 мс; в остальном это в основном то же, что и вызов removeObjectAtIndex: для каждого элемента)

(3) removeObjects:- 326 мс

(4) создать новый массив с объектами, прошедшими тест - 17 мс

Таким образом, создание нового массива является самым быстрым. Все остальные методы сопоставимы, за исключением того, что при использовании removeObjectsAtIndexes: будет хуже с удалением большего количества элементов из-за времени, необходимого для создания набора индексов.

18
3.06.2013 21:04:53
Вы посчитали время, чтобы создать новый массив и впоследствии освободить его? Я не верю, что он может сделать это один за 17 мс. Плюс 75000 назначений?
jack 17.09.2014 07:35:21
Время, необходимое для создания и освобождения нового массива, минимально
user1032657 19.09.2014 03:52:50
Вы, очевидно, не измеряли схему обратного цикла.
Hot Licks 16.04.2015 16:27:32
Первый тест эквивалентен схеме обратного цикла.
user1032657 8.05.2015 21:44:05
что происходит, когда вы остаетесь с вашим новым массивом, а ваш предыдущий массив обнуляется? Вам придется скопировать newArray в то, что было названо (или переименовать) в PrevArray, иначе как ваш другой код будет ссылаться на него?
aremvee 10.08.2015 03:24:18

Это очень простая проблема. Вы просто повторяете в обратном направлении:

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

Это очень распространенная модель.

42
21.08.2018 20:55:19
Это лучший метод. Важно помнить, что переменная итерации должна быть со знаком, несмотря на то, что индексы массива в Objective-C объявлены как беззнаковые (я могу представить, как Apple сожалеет об этом сейчас).
mojuba 17.11.2016 10:45:12

Вот простой и чистый способ. Мне нравится дублировать мой массив прямо в вызове быстрого перечисления:

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

Таким образом, вы перечисляете копию удаляемого массива, в котором хранятся одинаковые объекты. NSArray содержит только объектные указатели, так что это совершенно нормально с точки зрения памяти и производительности.

6
21.05.2015 02:26:58
Или даже проще -for (LineItem *item in self.lineItems.copy)
Alexandre G 15.10.2015 07:15:23

В настоящее время вы можете использовать обратное перечисление на основе блоков. Простой пример кода:

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"]];
12
7.05.2014 23:39:29
Есть ли гарантия, что массив не будет перераспределен?
Cfr 7.10.2013 08:01:12
Что вы имеете в виду с перераспределением?
vikingosegundo 7.10.2013 08:37:51
При удалении элемента из линейной структуры может оказаться эффективным выделить новый непрерывный блок памяти и переместить туда все элементы. В этом случае все указатели будут признаны недействительными.
Cfr 7.10.2013 09:42:48
Поскольку операция удаления не будет знать, сколько элементов будет поставлено на удаление в конце, это не имеет смысла делать во время удаления. В любом случае: детали реализации, мы должны доверять Apple, чтобы написать разумный код.
vikingosegundo 7.10.2013 11:09:06
Во-первых, это нехорошо (потому что вы должны много думать о том, как это работает, во-первых), а во-вторых, это не безопасный рефакторинг. В итоге я закончил с классическим принятым решением, которое на самом деле вполне читабельно.
Renetik 13.07.2017 17:48:38

Итерации в обратном направлении были моими любимыми годами, но долгое время я никогда не сталкивался со случаем, когда самый глубокий (самый высокий счет) объект был удален первым. За мгновение до того, как указатель переходит к следующему индексу, ничего не происходит, и он падает.

Путь Бензадо наиболее близок к тому, что я делаю сейчас, но я никогда не думал, что после каждого удаления будет перестановка стека.

под Xcode 6 это работает

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];
0
10.08.2015 07:27:48

Более хорошая реализация могла бы использовать метод категории ниже на 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

Блок предикатов может быть реализован для обработки каждого объекта в массиве. Если предикат возвращает true, объект удаляется.

Пример массива дат для удаления всех дат, которые были в прошлом:

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