Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

NSSet implementation

This question is just out of curiosity but, how is NSSet implemented? What data structure is behind it and what are the access times for adding and removing elements? If I had to guess, I'd say it was some sort of hashtable/dictionary data structure, but in that case why differentiate between NSSet and NSMutableSet?

like image 716
kodai Avatar asked May 02 '11 23:05

kodai


People also ask

What's a difference between NSArray and NSSet?

The main difference is that NSArray is for an ordered collection and NSSet is for an unordered collection. There are several articles out there that talk about the difference in speed between the two, like this one. If you're iterating through an unordered collection, NSSet is great.

What is NSSet?

NSSet declares the programmatic interface for static sets of distinct objects. You establish a static set's entries when it's created, and can't modify the entries after that. NSMutableSet , on the other hand, declares a programmatic interface for dynamic sets of distinct objects.


1 Answers

Well, as Bavarious pointed out in a comment, Apple's actual CoreFoundation source is open and available for your perusal too. NSSet is implemented on top of CFSet, whose code is generated (as is that of CFDictionary) from a hash table template, using CFBasicHash to do the work.

The difference between mutablility and immutability seems to be the matter of a flag in the structure (line 91 of CFBasicHash.h), and from my reading so far just affects calls to functions such as CFBasicHashAddValue; there's a simple check for the mutability. It seems likely, however, that Cobbal is right about the copy/retain behavior between the two (I just haven't read that far yet).

PREVIOUSLY:
I find it interesting and educational occasionally to peruse the GNUstep sources when I'm wondering about implementation details. They are, of course, not at all guaranteed to be implemented the way that Apple did it, but they can be helpful in some cases. Their version of Foundation: http://gnu.ethz.ch/debian/gnustep/gnustep-base-1.20.0/Headers/Foundation/ (I hope that's the most recent version. If not, someone please correct me.)

like image 161
jscs Avatar answered Sep 17 '22 18:09

jscs