Removing duplicates from NSMutableArray

Question

I have this problem with removing duplicate objects from an array. I tried these already:

noDuplicates = _personalHistory.personalHistory;

for (int i=[noDuplicates count]-1; i>0; i--) {
    if ([noDuplicates indexOfObject: [noDuplicates objectAtIndex: i]]<i)
        [noDuplicates removeObjectAtIndex: i];
}


for (PersonalHistory_artikels *e in _personalHistory.personalHistory) {
    if (![noDuplicates containsObject:e]) {
        NSLog(@"Dubplicates");
        [noDuplicates addObject:e];
    }
}


for (i=0; i<_personalHistory.personalHistory.count; i++) {
    PersonalHistory_artikels *test = [_personalHistory.personalHistory objectAtIndex:i];
    for (j=0; j<_personalHistory.personalHistory.count; j++) {
        PersonalHistory_artikels *test2 = [_personalHistory.personalHistory objectAtIndex:j];
        if (! [test.nieuwsTITLE_personal isEqual:test2.nieuwsTITLE_personal]) {
            NSLog(@"Add test = %@", test.nieuwsTITLE_personal);
            [noDuplicates addObject:test];
        }
    }
}

But none of the above gave me the right array. The last one was the best, but it still showed duplicate values. Can someone help me with this problem? Thank you very much.

Solution 1

Just convert the array to an NSSet and back again. A set can't have duplicates by design.

EDIT:

Note that a set doesn't have a sorting order. Therefore, you can go cheaper and forgo the order, or go for a slightly more expensive operation but keep the order.

NSArray *hasDuplicates = /* (...) */;
NSArray *noDuplicates = [[NSSet setWithArray: hasDuplicates] allObjects];

Solution 2

In OS X 10.7 and iOS 5.0 and later:

newArray = [[NSOrderedSet orderedSetWithArray:oldArray] array];

Solution 3

If you want to maintain ordering, you could do something like this

@interface NSArray (OrderedDuplicateElimination)

- (NSArray *)arrayByEliminatingDuplicatesMaintainingOrder
{
  NSMutableSet *addedObjects = [NSMutableSet set];
  NSMutableArray *result = [NSMutableArray array];

  for (id obj in self) {
    if (![addedObjects containsObject:obj]) {
      [result addObject:obj];
      [addedObjects addObject:obj];
    }
  }

  return result;
}

@end

This solution has lower computational complexity than most of the others so far suggested; for an array with N elements of which M are unique, it should have worst-case complexity O(N log M), rather than O(N^2). The simpler solutions might be faster for short arrays, however, since this method does have some additional overhead.

Of course, it does rely on your -isEqual: and -hash methods being implemented correctly.

Solution 4

How about this category?

@implementation NSArray (Unique)

- (NSArray*) arrayByDroppingDuplicates
{
    NSMutableArray *tmp = [NSMutableArray array];
    for (id item in self)
        if (![tmp containsObject:item])
            [tmp addObject:item];
    return [NSArray arrayWithArray:tmp];
}

@end

You can use it like this:

NSArray *items = [NSArray arrayWithObjects:@"foo", @"bar", @"foo", nil];
NSArray *unique = [items arrayByDroppingDuplicates]; // [@"foo", @"bar"]

Solution 5

I think your problem lies in how you define the equality of your PersonalHistory_artikels objects.

Regardless of the algorithm you use to remove duplicates in an array, make sure you provide adequate -isEqual: and -hash method implementations. See the Apple documentation for those two methods, particularly this paragraph:

If two objects are equal (as determined by the isEqual: method), they must have the same hash value. This last point is particularly important if you define hash in a subclass and intend to put instances of that subclass into a collection.

If a mutable object is added to a collection that uses hash values to determine the object’s position in the collection, the value returned by the hash method of the object must not change while the object is in the collection. Therefore, either the hash method must not rely on any of the object’s internal state information or you must make sure the object’s internal state information does not change while the object is in the collection. Thus, for example, a mutable dictionary can be put in a hash table but you must not change it while it is in there. (Note that it can be difficult to know whether or not a given object is in a collection.)

Hope this helps.

View more solutions

Comments

[zoul]

-1. That was my first idea, too, but the set does not guarantee item ordering.

[Alexsander Akers]

Yes, but if you're going to remove duplicates from the array, you're not going to guarantee item ordering because you're either keeping the first or last instance of each item.

[zoul]

Depends on what the poster is trying to do. His array is called history, so that it’s quite probable that he’s trying to turn something like aaabbca into abc. That’s why the naive solution seems better to me. But you’re right, set might do, it just would be nice to give a warning about the resulting item order.

[zoul]

In that case you might have problems with equality checking, see octy’s answer. (Are you sure the source array wasn’t nil?)

[al45tair]

This has complexity O(N^2), since -containsObject: is O(N). That is, the time taken to execute this method will increase with the square of the length of the array (which is quite bad).

[al45tair]

This also has complexity O(N^2), though it might in some cases be faster than the other O(N^2) approach as it does at least avoid considering items it’s already dealt with. However, it has greater overhead because it starts by copying the entire input array.

[zoul]

Good suggestion. This probably won’t be an issue until there are several hundreds of items (finishes in 0.03s for 1000 randomly generated strings on my iMac), but it’s good to know.

[JeremyP]

Similar to the answer I would use, but I would start with an empty set and add objects that are not in the set both to the set and the new array.

[user750079]

I tried it, but I got a "Program received signal: “EXC_BAD_ACCESS”." message.

[user750079]

Hi, I tried this option: but I got a warning: NSMutableArray may not respond to removeDuplicates. (I tried it with a NSArray also).

[zoul]

Show us the new code so that we don’t have to guess what’s wrong.

[al45tair]

@JeremyP I’ve updated the code to reflect that idea, since I think I agree with you that it’s better. Interestingly, reversing the sense of the set does avoid having to create a set full of objects up front, though it also means that you can’t test for completion so easily; however, since the set already had to iterate the entire array, that probably wasn’t a win overall anyway.

[Smilin Brian]

Same solution as provided by Alexsander Akers

[Anikeev Gennadiy]

One problem I have with this solution is that order is not necessarily maintained (this threw me for awhile).

[hatfinch]

I must admit I've never actually tried it. Could you please elaborate on the circumstances in which order is not maintained?