Sets

Array elements are ordered, but can contain duplicates, that is, the same value can occur at different indices. In a dictionary, keys have to be unique, but the values do not, and the keys are not ordered. If you want a collection where order does not matter, but where the elements have to be unique, then use a Set. Creating a set is as easy as this:

// code in Chapter 5\sets.jl: 
s = Set([11, 14, 13, 7, 14, 11])

The Set() function creates an empty set Set(Any[]). The preceding line returns Set([7, 14, 13, 11]), where the duplicates have been eliminated.

Operations from the set theory are also defined for s1 = Set([11, 25]) and s2 = Set([25, 3.14]) as follows:

• union(s1, s2) produces Set([3.14,25,11])
• intersect(s1, s2) produces Set([25])
• setdiff(s1, s2) produces Set{Any}([11]), whereas setdiff(s2, s1) produces Set([ 3.14])
• issubset(s1, s2) produces false, but issubset(s1, Set([11, 25, 36])) produces true

To add an element to a set is easy: push!(s1, 32) adds 32 to set s1. Adding an existing element will not change the set. To test whether a set contains an element, use in. For example, in(32, s1) returns true and in(100, s1) returns false.

Set([1,2,3]) produces a set of integers Set([2,3,1]) of the Set{Int64} type. To get a set of arrays, use Set([[1,2,3]]), which returns Set(Array{Int64,1}[[1, 2, 3]]).

Sets are commonly used when we need to keep track of objects in no particular order. For instance, we might be searching through a graph. We can then use a set to remember which nodes of the graph we have already visited in order to avoid visiting them again. Checking whether an element is present in a set is independent of the size of the set. This is extremely useful for very large sets of data, for example:

x = Set(collect(1:100)) 
@time 2 in x   
#> 0.003186 seconds (33 allocations: 2.078 KiB) 
x2 = Set(collect(1:1000000)) 
@time 2 in x2  
# 0.000003 seconds (4 allocations: 160 bytes) 

The second statement executes much faster using much less memory, despite the fact that x2 is four orders of magnitude larger than x.

Take a look at the Collections module if you need more specialized containers. It contains a priority queue as well as some lower-level heap functions.