
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


record
union(record a, record b)
{
    record c;
    r_copy(c, a);
    r_wcall(b, r_add, 1, 2, c);
    return c;
}
 
record
intersection(record a, record b)
{
    record c;
    text s;
    for (s in a) {
        if (r_key(b, s)) {
            c[s] = 0;
        }
    }
    return c;
}
 
record
difference(record a, record b)
{
    record c;
    r_copy(c, a);
    r_vcall(b, r_resign, 1, c);
    return c;
}
 
integer
subset(record a, record b)
{
    integer e;
    text s;
    e = 1;
    for (s in a) {
        if (!r_key(b, s)) {
            e = 0;
            break;
        }
    }
    return e;
}
 
integer
equal(record a, record b)
{
    return subset(a, b) && subset(b, a);
}
 
integer
main(void)
{
    record a, b;
    text s;
 
    r_fit(a, "apple", 0, "cherry", 0, "grape", 0);
    r_fit(b, "banana", 0, "cherry", 0, "date", 0);
 
    s = "banana";
 
    o_(" ", s, " is ", r_key(a, s) ? "" : "not ", "an element of A\n");
    o_(" ", s, " is ", r_key(b, s) ? "" : "not ", "an element of B\n");
 
    r_vcall(union(a, b), o_, 1, " ");
    o_newline();
 
    r_vcall(intersection(a, b), o_, 1, " ");
    o_newline();
 
    r_vcall(difference(a, b), o_, 1, " ");
    o_newline();
 
    o_(" ", subset(a, b) ? "yes" : "no", "\n");
 
    o_(" ", equal(a, b) ? "yes" : "no", "\n");
 
    return 0;
}