Sequences as sets
Factor handbook » The language » Collections » Sets » Set implementations

Next:Hash sets


Any sequence can be used as a set. The members of this set are the elements of the sequence. Calling the word members on a sequence returns a copy of the sequence with only one listing of each member. Destructive operations adjoin and delete only work properly on growable sequences like vectors.

Care must be taken in writing efficient code using sequence sets. Testing for membership with in?, as well as the destructive set operations, take time proportional to the size of the sequence. Another representation, like Hash sets, would take constant time for membership tests. But binary operations like union are asymptotically optimal, taking time proportional to the sum of the size of the inputs.

As one particular example, f is a representation of the empty set, since it is an empty sequence.