Grouping duplicates in NSArray

Question

I have an NSArray containing custom objects, for example:

[A, A, B, C, A, D, E, B, D]

What is the best way to group these items so the end result resembles this?

A: 3
B: 2
C: 1
D: 2
E: 1

Please note that the duplicates are all different instances that have the same properties, but I have overridden isEqual: for this.

Your desired result looks more like a dictionary than an array, do you want the count associated with the letter? — Chris Wagner, Dec 05 '11 at 20:22
@ChrisWagner Yes, but they are not letters. They are custom objects. — pixelfreak, Dec 05 '11 at 22:08

score 8 · Accepted Answer · answered Dec 05 '11 at 20:25

8

The simplest way is probably to use an NSCountedSet. You can use [NSCountedSet setWithArray:myArray] to produce a counted set of your array, and then you can iterate over the set's contents to find out the count of each object in the set. Note that it won't be sorted.

Also note that you'll need to provide a sensible implementation of -hash for this to work, since you only said you overrode -isEqual:. You also need to override -compare: if you need a sorted list of results.

Here's a quick method that takes your array and prints the count of each element, sorted:

void printCountOfElementsInArray(NSArray *ary) {
    NSCountedSet *set = [NSCountedSet setWithArray:ary];
    NSArray *objs = [[set allObjects] sortedArrayUsingSelector:@selector(compare:)];
    for (id obj in objs) {
        NSLog(@"%@: %d", obj, [set countForObject:obj]);
    }
}

answered Dec 05 '11 at 20:25

Lily Ballard

182,031
33
381
347

Thanks, I am new to hash. Could you point me in the right direction on how to override it? And why do I need to override `hash` as well? I thought `isEqual` would be sufficient... – pixelfreak Dec 05 '11 at 22:15
@pixelfreak: The one thing about `-hash` that *must* be true is two objects that are equal (i.e. that return `YES` from `-isEqual:`) *must* return the same value from `-hash`. However, the reverse is not true. Two objects that return the same value from `-hash` are *not necessarily* equal. This means that you could implement this method as `- (NSUInteger)hash { return 1; }`. If you want. However, this will lead to extremely inefficient dictionaries/sets. The [wikipedia page on hash functions](http://en.wikipedia.org/wiki/Hash_function) has useful information. – Lily Ballard Dec 05 '11 at 22:20
@pixelfreak: For reference, I *believe* the default implementation of `-hash` on `NSObject` just returns the object pointer. This means that you *must* override it if you implement a custom `-isEqual:` (and expect the object to be used as a key to a dictionary or as part of a set). – Lily Ballard Dec 05 '11 at 22:21
Thanks! Also found this link: http://stackoverflow.com/a/254380/58505 about generating a good hash – pixelfreak Dec 05 '11 at 22:28
1

@pixelfreak: If my object is composed of other objects which have decent `-hash` implementations, then I tend to just XOR their `hash`es together. The link you provided is good if you have C primitives (e.g. `int`s) though. – Lily Ballard Dec 05 '11 at 22:30
Actually, wouldn't the result of your code be more like: A: 3 A: 3 A: 3 B: 2 B: 2 ... and so on...? What could you do to remove the duplicate outputs? – pixelfreak Dec 05 '11 at 22:32
@pixelfreak: No. An `NSSet` only includes each unique object once. An `NSCountedSet` keeps a count of how many times a unique object has been added to the set, but it still only persists one instance of that object. The accessor `-countForObject:` tells you how many instances of that object were added, but iterating over the set (or using `-allObjects`) still only returns unique instances. – Lily Ballard Dec 05 '11 at 22:34
@pixelfreak: You can think of an `NSCountedSet` like an `NSDictionary` where the added objects are the keys and the count is the value. – Lily Ballard Dec 05 '11 at 22:35
One last question, I assume if I modify any object already added into an `NSCountedSet`, it'll not work as expected? – pixelfreak Dec 05 '11 at 23:41
@pixelfreak: Correct. Mutable objects that are inserted into hashed containers must not change their `-hash` while in the container. Sometimes this means they have really poor `-hash` implementations to begin with that don't actually change when you mutate them, and sometimes this means it's simply incorrect to mutate the object once added to a collection (`NSMutableString` is the latter). If you can, it's better to use immutable objects with good hashes, and just replace the object wholesale if you need to make a change (though this obviously isn't something you can always do). – Lily Ballard Dec 05 '11 at 23:46

score 7 · Answer 2 · answered Dec 05 '11 at 20:24

7

Use the NSCountedSet class.

NSCountedSet *countedSet = [[NSCountedSet alloc] initWithArray:myArray];
NSUInteger countForA = [countedSet countForObject:@"A"];
NSLog(@"A: %u", countForA);

answered Dec 05 '11 at 20:24

Ole Begemann

135,006
31
278
256

Sorry, I guess the letters are bad example. Those are not letters, they are custom objects. So @Kevin's answer is a closer. – pixelfreak Dec 05 '11 at 22:16

Grouping duplicates in NSArray

2 Answers2