Sequences as sets

Factor handbook » The language » Collections » Sets » Set implementations

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 vector s.

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.

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.