Sets: Unordered Collections of Objects

A set is an unordered collection of objects, as shown in Figure 1. You can use sets as an alternative to arrays when the order of elements isn’t important and performance of testing whether an object is in the set is important. Even though arrays are ordered, testing them for membership is slower than testing sets.

Figure 1  Example set

Set Fundamentals

An NSSet object manages an immutable set of distinct objects—that is, after you create the set, you cannot add, remove, or replace objects. You can, however, modify individual objects themselves (if they support modification). The mutability of the collection does not affect the mutability of the objects inside the collection. You should use an immutable set if the set rarely changes, or changes wholesale.

NSMutableSet, a subclass of NSSet, is a mutable set of distinct objects, which allows the addition and deletion of entries at any time, automatically allocating memory as needed. You should use a mutable set if the set changes incrementally, or is very large—as large collections take more time to initialize.

NSCountedSet, a subclass of NSMutableSet, is a mutable set to which you can add a particular object more than once; in other words, the elements of the set aren’t necessarily distinct. A counted set is also known as a bag. The set keeps a counter associated with each distinct object inserted. NSCountedSet objects keep track of the number of times objects are inserted and require that objects be removed the same number of times to completely remove the object from the set. Thus, there is only one instance of an object in a counted set, even if the object has been added multiple times. The countForObject: method returns the number of times the specified object has been added to this set.

The objects in a set must respond to the NSObject protocol methods hash and isEqual: (see NSObject for more information). If mutable objects are stored in a set, either the hash method of the objects shouldn’t depend on the internal state of the mutable objects or the mutable objects shouldn’t be modified while they’re in the set. For example, a mutable dictionary can be put in a set, 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).

NSSet provides a number of initializer methods, such as setWithObjects: and initWithArray:, that return an NSSet object containing the elements (if any) you pass in as arguments. Objects added to a set are not copied (unless you pass YES as the argument to initWithSet:copyItems:). Rather, a strong reference to the object is added to the set. For more information on copying and memory management, see “Copying Collections.”

Sets, excluding NSCountedSet, are the preferred collections if you want to be assured that no object is represented more than once, and there is no net effect for adding an object more than once.

Mutable Sets

You can create an NSMutableSet object using any of the initializers provided by NSSet. You can create an NSMutableSet object from an instance of NSSet (or vice versa) using setWithSet: or initWithSet:.

The NSMutableSet class provides methods for adding objects to a set:

The NSMutableSet class additionally provides these methods to remove objects from a set:

Because NSCountedSet is a subclass of NSMutableSet, it inherits all of these methods. However, some of them behave slightly differently with NSCountedSet. For example:

Using Sets

The NSSet class provides methods for querying the elements of the set:

The NSSet method objectEnumerator lets you traverse elements of the set one by one. And themakeObjectsPerformSelector: and makeObjectsPerformSelector:withObject: methods provide for sending messages to individual objects in the set. In most cases, fast enumeration should be used because it is faster and more flexible than using an NSEnumerator or the makeObjectsPerformSelector: method. For more on enumeration, see “Enumeration: Traversing a Collection’s Elements.”

Hash Tables

The NSHashTable class is configured by default to hold objects much like NSMutableSet does. It also allows additional storage options that you can tailor for specific cases, such as when you need advanced memory management options, or when you want to hold a specific type of pointer. For example, the map table in Figure 2 is configured to hold weak references to its elements. You can also specify whether you want to copy objects entered into the set.

Figure 2  Hash table object ownership

You can use an NSHashTable object when you want an unordered collection of elements that uses weak references. For example, suppose you have a global hash table that contains some objects. Because global objects are never collected, none of its contents can be deallocated unless they are held weakly. Hash tables configured to hold objects weakly do not own their contents. If there are no strong references to objects within such a hash table, those objects are deallocated. For example, the hash table in Figure 2 holds weak references to its contents. Objects A, C, and Z will be deallocated, but the rest of the objects remain.

To create a hash table, initialize it using the initWithOptions:capacity: method and the appropriate pointer functions options. Alternatively, you can initialize it using initWithPointerFunctions:capacity: and appropriate instances of NSPointerFunctions. For more information on the various pointer functions options, see “Pointer Function Options.”

The NSHashTable class also defines the hashTableWithWeakObjects convenience constructor for creating a hash table with weak references to its contents. It should only be used if you are storing objects.

To configure a hash table to use arbitrary pointers, initialize it with both the NSPointerFunctionsOpaqueMemory and NSPointerFunctionsOpaquePersonality options. When using a hash table to contain arbitrary pointers, the C function API for void * pointers should be used. For more information, see “Hash Tables” in Foundation Functions Reference. For example, you can add a pointer to an int value using the approach shown in Listing 1.

Listing 1  Hash table configured for non-object pointers

NSHashTable *hashTable=[[NSHashTable alloc] initWithOptions:
    NSPointerFunctionsOpaqueMemory |NSPointerFunctionsOpaquePersonality
    capacity: 1];
 
NSHashInsert(hashTable, someIntPtr);

When configured to use arbitrary pointers, a hash table has the risks associated with using pointers. For example, if the pointers refer to stack-based data created in a function, those pointers are not valid outside of the function, even if the hash table is. Trying to access them will lead to undefined behavior.