Separate names with a comma.
Discussion in 'Mac Programming' started by Darkroom, Apr 10, 2009.
Between a Set and an Array? any reason to use one over the other? or is it simply a matter of taste?
A set is unordered, and its elements are unique. An array is ordered, and elements can be duplicated. You'll have to decide which fits your needs per problem. The array is the hammer in the expression "when all you have is a hammer, everything looks like a nail.". A lot of times other data structures are ignored when they are a better fit than an array.
I would say the difference is that sets are associative containers where the element is both the key and value. Arrays on the other hand use an index for accessing elements.
b e n
In Cocoa, what you're describing is called a dictionary. In other languages/environments they are often called hashes or associative arrays. Sets are unordered collections like lee said.
I'll stick by what I said: a set is, (or if you prefer) is like, an associative container. The difference between a set and a map (or dictionary or associative array) is that in a set, the value of an element ***is also*** the key.
Also depending on what language you're using, a set can have duplicate entries.
b e n
That doesn't really make sense to me. In Cocoa, there's no notion of "association" in a set. The same goes for the mathematical definition of a set.
I'll accept that fact that perhaps in some environments a set is implemented as an associative collection where both the key and value are the same object. (My guess is PHP, because isn't every collection implemented as an associative array?) This would work because the mathematical definition of a "set" is implemented with the keys, and since you have to fill the value, why not make it the same as the value (which is redundant)?
But defining a set thus to a new-comer is confusing. The mathematical definition is the clearest: An unordered collection in which each element is unique.
A set is most often used when you need to see if one object is part of a group.
For example, let's say you had an array with 100,000 random numbers. If you wanted to figure out if the array contained a certain number, you would have to walk through the array, checking each element--this could potentially take 100,000 operations!
In a set, the elements are kept in a special data structure that allows fast lookup. Determining if a certain number is present in a group 100,000 will be much, much faster if you use a set than if you used an array.
Since each element must be unique, a set is basically a dictionary of keys with no associated values. Likewise, a dictionary is a set where each element can have a value associated with it.
An NSCountedSet (also known in the computer science world as a "bag" or multiset) is a mix between a set and a dictionary. Each element has a count associated with it that keeps track of how many times that element occurs in the collection. For example, the values "a", "b", "c", "b", "c", "c" would produce a counted set where "a" => 1, "b" => 2, and "c" => 3. Lookups in a counted set are just as fast as with a set or dictionary.
tl;dr: use an NSSet/NSCountedSet/NSDictionary when you need to perform lots of lookups/membership tests and they need to be fast. Use an NSArray for practically everything else. And google "computational complexity theory."
Umm, how does a mathematical description of a set make clear what the difference is between a set and an array in a programming context? All I wanted to get over was that with arrays items are referenced by their index, and in a set items are referenced by their value - not something immediately obvious from the statement that a set is an unordered collection!
b e n
They are different things.
NSSet and CFSet are like mathematical sets: They have elements, but the same value can be contained in a set only once. If you try to add the same object or an object with the same value again, nothing happens (but it takes a bit of time, because whenever you add an object, the set checks whether it has already an element with that value). Note that the objects are compared for equality: If you have two NSNumber objects, say when created with a double 5.0 and another created with an int 5, then they have the same value, and only one of them can be in the set. For that reason, it is also illegal to change an object that is stored in any set (because changing it could make it equal to another object in the set).
NSArray and CFArray just store pointers to objects (at least that is how they are usually used), possibly using retain and release to hold on to objects). You can store the same object multiple times, and the objects are indexed, so you can easily iterate through objects.