When is it better to use an NSSet over an NSArray?

Question

I have used NSSets many times in my apps, but I have never created one myself.

When is it better to use an NSSet as opposed to an NSArray and why?

score 183 · Answer 1 · edited Jan 31 '19 at 08:45

183

The image from Apple's Documentation describes it very well:

Objective-C Collections

Array is an ordered (order is maintained when you add) sequence of elements

[array addObject:@1];
[array addObject:@2];
[array addObject:@3];
[array addObject:@4];
[array addObject:@6];
[array addObject:@4];
[array addObject:@1];
[array addObject:@2];

[1, 2, 3, 4, 6, 4, 1, 2]

Set is a distinct (no duplicates), unordered list of elements

[set addObject:@1];
[set addObject:@2];
[set addObject:@3];
[set addObject:@4];
[set addObject:@6];
[set addObject:@4];
[set addObject:@1];
[set addObject:@2];

[1, 2, 6, 4, 3]

edited Jan 31 '19 at 08:45

Iulian Onofrei

9,188
10
67
113

answered Jun 12 '12 at 13:17

James Webster

31,873
11
70
114

2

In your example, you are adding primitives to an array and a set. Neither is possible because they can only contain objects. – FreeAsInBeer Jun 12 '12 at 13:28
10

Thanks for your edit @Zaheer, but it was actually invalid. I wasn't adding primitives. I was adding literals. – James Webster Feb 24 '14 at 08:41
For ordered collection of data and no duplicates you can use NSOrderedSet which is already introduces in iOS 5 and later. – Pradeep Singh Apr 18 '21 at 12:36

score 174 · Accepted Answer · edited Jul 03 '13 at 13:15

174

When the order of the items in the collection is not important, sets offer better performance for finding items in the collection.

The reason is that a set uses hash values to find items (like a dictionary) while an array has to iterate over its entire contents to find a particular object.

edited Jul 03 '13 at 13:15

James Webster

31,873
11
70
114

answered Jun 12 '12 at 13:14

Ole Begemann

135,006
31
278
256

25

@rohan-patel Correct is O(1) vs O(n) – Ruslan Mansurov Mar 04 '15 at 09:47
1

If ordered: O(1) vs O(logn) since binary search is applicable. If unordered, then O(1) vs O(n) – baskInEminence May 25 '16 at 21:26

woz · Answer 3 · 2013-11-07T13:11:49.437

67

The best answer is to this is Apple's own documentation.

enter image description here

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. However, in many cases, you need to do things that only an NSArray can do, so you sacrifice the speed for those abilities.

NSSet

Primarily access items by comparison
Unordered
Does not allow duplicates

NSArray

Can access items by index
Ordered
Allows duplicates

That's all there really is to it! Let me know if that helps.

edited Nov 07 '13 at 13:11

answered Jun 12 '12 at 13:18

woz

10,888
3
34
64

You don't have to always sacrifice `NSSet` for the sake of indexing. It's common to use two different data structures for the same data. Or you build and index on that array :) But then it's better to use a DB which has it alredy implemented. – Sulthan Jun 12 '12 at 13:37
"Build an index on that array". You cannot make an index on a NSSet. There are many different techniques you can use. And if you need to make sacrifices in BOTH memory and processing power, then you are doing it wrong. – Sulthan Jun 12 '12 at 13:53
Since the question is about `NSSet` and `NSArray`, my answer is accurate and complete. Yes, you can build other data structures, but I'm just comparing these two. – woz Jun 12 '12 at 13:58
I did upvote but your answer is incorrect when you speak about sacrifices. If you need some functionality from `NSArray` and some functioanlity from `NSSet`, the correct answer is not "use `NSArray` and sacrifice performance". The answer is combine both or use a different data structure. – Sulthan Jun 12 '12 at 14:14
I would have said the main difference is set is for unique objects where as an array can have duplicates. The order aspect is secondary to that fact. – malhal Dec 22 '15 at 19:16
"If you're iterating through an unordered collection, NSSet is great." - this is inaccurate. According to the article that you linked, NSArray is more efficient when it comes to the iterations, whether it's ordered or not: "Lesson: if you only need to iterate contents, don't use an NSSet." When you have to do a lot of lookups - then NSSet should be the data structure of choice. – Ilya Vinogradov Oct 04 '16 at 16:06

score 12 · Answer 4 · answered Feb 08 '13 at 14:26

12

NSOrderedSet is available in iOS 5+ so with that the main difference becomes whether you want duplicate objects in the data structure.

answered Feb 08 '13 at 14:26

Jason

1,323
14
19

score 9 · Answer 5 · edited Dec 08 '15 at 09:29

9

NSArray:

Ordered collection of data
Allows duplicates
It is collection type object

NSSet:

Unordered collection of data
Does not allow duplicates
It is also collection type object

edited Dec 08 '15 at 09:29

Jiri Tousek

12,211
5
29
43

answered Dec 08 '15 at 08:28

iOS Lifee

2,091
23
32

score 7 · Answer 6 · answered Jun 12 '12 at 13:25

7

An array is used to access items by their index. Any item can be inserted into the array multiple times. Arrays mantain the order of their elements.

A set is used basically only to check if the item is in the collection or not. The items have no concept of order or indexing. You cannot have an item in a set twice.

If an array wants to check if it contains an element, it has to check all its items. Sets are designed to use faster algorithms.

You can imagine a set like a dictionary without values.

Note that array and set are not the only data structures. There are other, e.g. Queue, Stack, Heap, Fibonacci's Heap. I would recommend reading a book about algorithms and data structures.

See wikipedia for more information.

answered Jun 12 '12 at 13:25

Sulthan

128,090
22
218
270

Actually, an array only needs to be checked up to the point that the item is found. If the item IS in the array, very rarely will every item need to be checked. – FreeAsInBeer Jun 12 '12 at 13:26
Yes, as you say "if the item IS in the array". If you expect this, you don't have to check if it's there or not. The complexity of the `contains` operation is `O(n)`. Number of comparisons when not in the array is `n`. The average number of comparisons when the object is in the array is `n/2`. Even if the object is found, the performance is awful. – Sulthan Jun 12 '12 at 13:34
Performance would only be awful with a large array. If you knew the array could become quite large, then there are ways you could improve performance of the array, such as using an array of arrays. – FreeAsInBeer Jun 12 '12 at 16:01
If the equality operation is expensive, you will see the difference even on arrays with 3 items. And the same behaviour as a large array can happen whan you repeat the operation a lot (e.g. use the operation in a 'for' cycle). Have you heard about amortized complexity? The complexity is still linear and the performance is awful compared to a set (usually with constant complexity). – Sulthan Jun 12 '12 at 16:15
Obviously there will be a difference, I'm just stating that the big o notation is exponential; with small arrays, the difference will be minuscule. Also, `NSArray`s have other speed advantages over `NSSet`s. As always, it's a tradeoff. – FreeAsInBeer Jun 12 '12 at 16:21

score 5 · Answer 7 · edited Mar 01 '16 at 07:50

5

NSArray *Arr;
NSSet *Nset;

Arr=[NSArray arrayWithObjects:@"1",@"2",@"3",@"4",@"2",@"1", nil];
Nset=[NSSet setWithObjects:@"1",@"2",@"3",@"3",@"5",@"5", nil];

NSLog(@"%@",Arr);
NSLog(@"%@",Nset);

the array

2015-12-04 11:05:40.935 [598:15730] ( 1, 2, 3, 4, 2, 1 )

the set

2015-12-04 11:05:43.362 [598:15730] { ( 3, 1, 2, 5 )}

edited Mar 01 '16 at 07:50

DeyaEldeen

10,847
10
42
75

answered Dec 04 '15 at 05:44

abc221

51
1
1

score 4 · Answer 8 · answered Dec 14 '14 at 07:36

The main differences have already been given in other answers.

I'd just like to note that because of the way sets and dictionaries are implemented (i.e. using hashes),one should be careful not to use mutable objects for the keys.

If a key is mutated then the hash will (probably) change too, pointing to a different index/bucket in the hash table. The original value won't be deleted and will actually be taken into account when enumerating or asking the structure for its size/count.

This can lead to some really hard to locate bugs.

Che · Answer 9 · 2016-02-16T13:10:17.043

Here you can find a pretty thorough comparison of the NSArray and NSSet datastructures.

Short conclusions:

Yes, NSArray is faster than NSSet for simply holding and iterating. As little as 50% faster for constructing and as much as 500% faster for iterating. Lesson: if you only need to iterate contents, don't use an NSSet.

Of course, if you need to test for inclusion, work hard to avoid NSArray. Even if you need both iteration and inclusion testing, you should probably still choose an NSSet. If you need to keep your collection ordered and also test for inclusion, then you should consider keeping two collections (an NSArray and an NSSet), each containing the same objects.

NSDictionary is slower to construct than NSMapTable — since it needs to copy the key data. It makes up for this by being faster to lookup. Of course, the two have different capabilities so most of the time, this determination should be made on other factors.

Whilst this may theoretically answer the question, [it would be preferable](//meta.stackoverflow.com/q/8259) to include the essential parts of the answer here, and provide the link for reference. — Tunaki, Feb 10 '16 at 13:52

iDevAmit · Answer 10 · 2018-11-26T02:35:04.827

2

You would typically use a Set when access speed is of the essence and order doesn’t matter, or is determined by other means (through a predicate or sort descriptor). Core Data for example uses sets when managed objects are accessed via a to-many relationship

edited Nov 26 '18 at 02:35

answered Jun 24 '16 at 09:38

iDevAmit

1,550
2
21
33

score 1 · Answer 11 · answered May 23 '18 at 10:58

1

Just to add a bit of it i use set sometimes just to remove duplicates from array like :-

NSMutableSet *set=[[NSMutableSet alloc]initWithArray:duplicateValueArray]; // will remove all the duplicate values

answered May 23 '18 at 10:58

tryKuldeepTanwar

3,490
2
19
49

When is it better to use an NSSet over an NSArray?

11 Answers11

Linked