How has Apple implemented NSSet?

Question

Apple's docs currently DO NOT DOCUMENT NSSet's concept of "identity".

I have some bugs that appear to come from Apple's code. For instance, "[NSMutableSet minusSet]" never works for me as documented - but I'm pretty sure it's because of "identity".

e.g. from: http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/Reference/Reference.html#//apple_ref/occ/cl/NSSet

containsObject:

Returns a Boolean value that indicates whether a given object is present in the set.

YES if anObject is present in the set, otherwise NO.

What does that MEAN?

FYI things I've tried:

1. implemented "isEqual:" on all classes in the set
2. checked that all classes are the same class (no subclass / superclass confusion)
3. implementd NSCopying on all classes in the set (no effect)

Answer 1

In Cocoa, object equality is done by using isEqual: and hash:

https://developer.apple.com/library/ios/#documentation/Cocoa/Reference/Foundation/Protocols/NSObject_Protocol/Reference/NSObject.html

From the notes for isEqual::

If two objects are equal, they must have the same hash value. This last point is particularly important if you define isEqual: in a subclass and intend to put instances of that subclass into a collection. Make sure you also define hash in your subclass.

Your subclasses will need to implement both of these, so that they return the same thing. Once they do this, then they can be used correctly in Cocoa Collections.

The reason your NSSet equality wouldn't work, is because sets use hashes (it's stored as a hash table), hence if you only implemented isEqual:, then theres a chance (a good chance) that their hashes would be different.

Answer 2

NSSet is a hash set in the classical sense, so you have to implement the hash method to make sure that objects are recognized as being equal. By default, hash simply returns the pointer of the object casted to an unsigned integer, which is unique for every object, so even objects that return true for isEqual: won't recognized as such. If you are interested in the workings of NSSet, you can take a look into the CFSet source code, which is the toll-free bridged Core Foundation counter part of NSSet.