
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


with javascript_semantics
function is_element(object x, sequence set)
    return find(x,set)!=0
end function
 
function set_union(sequence set1, set2)
    for i=1 to length(set2) do
        if not is_element(set2[i],set1) then
            set1 = append(set1,set2[i])
        end if
    end for
    return set1
end function
 
function set_intersection(sequence set1, set2)
    sequence res = {}
    for i=1 to length(set1) do
        if is_element(set1[i],set2) then
            res = append(res,set1[i])
        end if
    end for
    return res
end function
 
function set_difference(sequence set1, set2)
    sequence res = {}
    for i=1 to length(set1) do
        if not is_element(set1[i],set2) then
            res = append(res,set1[i])
        end if
    end for
    return res
end function
 
function set_subset(sequence set1, set2)
    for i=1 to length(set1) do
        if not is_element(set1[i],set2) then
            return false
        end if
    end for
    return true
end function
 
function set_equality(sequence set1, set2)
    if length(set1)!=length(set2) then
        return false
    end if
    return set_subset(set1,set2)
end function

--test code:
?is_element(3,{1,2,3})              -- 1
?is_element(4,{1,2,3})              -- 0
?set_union({1,2,3},{3,4,5})         -- {1,2,3,4,5}
?set_intersection({1,2,3},{3,4,5})  -- {3}
?set_difference({1,2,3},{3,4,5})    -- {1,2}
?set_subset({1,2,3},{3,4,5})        -- 0
?set_subset({1,2},{1,2,3})          -- 1
?set_equality({1,2,3},{3,4,5})      -- 0
?set_equality({1,2,3},{3,1,2})      -- 1
