
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.



Task

Show each of these set operations:

 Set creation
 Test m ∈ S -- "m is an element in set S"
 A ∪ B -- union; a set of all elements either in set A or in set B.
 A ∩ B -- intersection; a set of all elements in both set A and set B.
 A ∖ B -- difference; a set of all elements in set A, except those in set B.
 A ⊆ B -- subset; true if every element in set A is also in set B.
 A = B -- equality; true if every element of set A is in set B and vice versa.


As an option, show some other set operations.

(If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.)

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 and some dummy value as the values).

One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators).

The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.



See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


 
procedure display_set (s)
  writes ("[")
  every writes (!s || " ")
  write ("]")
end
 
# fail unless s1 and s2 contain the same elements
procedure set_equals (s1, s2)
  return subset(s1, s2) & subset(s2, s1)
end
 
# fail if every element in s2 is not contained in s1
procedure subset (s1, s2)
  every (a := !s2) do {
    if not(member(s1,a)) then fail
  }
  return s2
end
 
procedure main ()
  a := set(1, 1, 2, 3, 4)
  b := set(2, 3, 5)
  writes ("a: ")
  display_set (a)
  writes ("b: ")
  display_set (b)
  # basic set operations
  writes ("Intersection: ")
  display_set (a ** b)
  writes ("Union: ")
  display_set (a ++ b)
  writes ("Difference: ")
  display_set (a -- b)
  # membership
  if member(a, 2) then
    write ("2 is a member of a")
  else
    write ("2 is not a member of a")
  if member(a, 5) then
    write ("5 is a member of a")
  else
    write ("5 is not a member of a")
  # equality
  if set_equals(a, set(1,2,3,4,4)) then
    write ("a equals set(1,2,3,4,4)")
  else
    write ("a does not equal set(1,2,3,4,4)")
  if set_equals(a, b) then
    write ("a equals b")
  else
    write ("a does not equal b")
  # subset
  if subset(a, set(1,2)) then
    write ("(1,2) is included in a")
  else
    write ("(1,2) is not included in a")
  if subset(a, set(1,2,5)) then
    write ("(1,2,5) is included in a")
  else
    write ("(1,2,5) is not included in a")
end
 