Set

Set is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Data Structure
This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.

A set is a collection of elements, without duplicates and without order.

Show how to create a set, and how to test m ∈ S, true if m is an element in set S. Also show each of these set operations:

• A ∪ B -- union; a set of all elements each in set A or in set B.
• A ∩ B -- intersection; a set of all elements each in both set A and set B.
• A − B -- difference; a set of all elements in set A, except those in B.
• A ⊂ B -- subset; true if every element in set A is also in set B.
• A = B -- equality; true if every element in either set is in other set.

As an option, show some other set operations. As another option, show how to modify a mutable set.

One might implement a set using an associative array (with set elements as array keys), or using a list, a binary search tree or a hash table. The basic test, m ∈ S, is O(n) with a list, O(log n) with a balanced binary search tree, or near O(1) with a hash table.