Why is iterating through NSArray is faster than iterating through NSSet?

Question

I was wondering Why is iterating through NSArray is faster than iterating through NSSet? I imaging that it has something to do with the fact that NSArray is ordered while the NSSet is not but I what a certified answer instead of just guessing.

Edit:

my question was: why is it faster which is not explained in that topic. and not if its faster.

Answer 1

@Amin's answer is not accurate in some aspects.

1. We are talking about Iterating, not searching.
2. Searching in a Set is of course faster than searching in an Array, as the first takes only O(1) time, while the second takes O(n) time.
3. In my opinion, NSArray is faster than NSSet(Iterating), because NSArray's accessing time is exact O(1), though NSSet is O(1) too, but it's amortized.
4. You can not even insert an object into NSSet

Can you explain a bit more about "Obviously the extra condition for sets is more expensive than the extra condition for arrays."

Answer 2

First: You cannot say that NSArray is faster than NSSet. As you get from the link in the comments, it depends on what you are doing. Searching for an object in an instance of NSSet is faster by far. And this is, what you want to do, when you choose NSSet.

There are two differences between sets and arrays.

• arrays has to keep the order, sets don't.
• sets has to take care about uniqueness, arrays don't.

So it seems to be clever, to have completely different implementations for both. This can lead to different runtime behavior. So the correct Q would be: Where is the surprise?

Obviously the extra condition for sets is more expensive than the extra condition for arrays.

BTW: It is impossible for an instance of NSSet, to fulfill the promise about uniqueness it makes. This is, because uniqueness is only checked, when you insert an object into the set. When you change an object after inserting it, it can become equal to another object in the set.