
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


package main
 
import "fmt"
 
// Define set as a type to hold a set of complex numbers.  A type
// could be defined similarly to hold other types of elements.  A common
// variation is to make a map of interface{} to represent a set of
// mixed types.  Also here the map value is a bool.  By always storing
// true, the code is nicely readable.  A variation to use less memory
// is to make the map value an empty struct.  The relative advantages
// can be debated.
type set map[complex128]bool
 
func main() {
    // task: set creation
    s0 := make(set)             // create empty set
    s1 := set{3: true}          // create set with one element
    s2 := set{3: true, 1: true} // create set with two elements
 
    // option: another way to create a set
    s3 := newSet(3, 1, 4, 1, 5, 9)
 
    // option: output!
    fmt.Println("s0:", s0)
    fmt.Println("s1:", s1)
    fmt.Println("s2:", s2)
    fmt.Println("s3:", s3)
 
    // task: element predicate
    fmt.Printf("%v ∈ s0: %t\n", 3, s0.hasElement(3))
    fmt.Printf("%v ∈ s3: %t\n", 3, s3.hasElement(3))
    fmt.Printf("%v ∈ s3: %t\n", 2, s3.hasElement(2))
 
    // task: union
    b := set{4: true, 2: true}
    fmt.Printf("s3 ∪ %v: %v\n", b, union(s3, b))
 
    // task: intersection
    fmt.Printf("s3 ∩ %v: %v\n", b, intersection(s3, b))
 
    // task: difference
    fmt.Printf("s3 \\ %v: %v\n", b, difference(s3, b))
 
    // task: subset predicate
    fmt.Printf("%v ⊆ s3: %t\n", b, subset(b, s3))
    fmt.Printf("%v ⊆ s3: %t\n", s2, subset(s2, s3))
    fmt.Printf("%v ⊆ s3: %t\n", s0, subset(s0, s3))
 
    // task: equality
    s2Same := set{1: true, 3: true}
    fmt.Printf("%v = s2: %t\n", s2Same, equal(s2Same, s2))
 
    // option: proper subset
    fmt.Printf("%v ⊂ s2: %t\n", s2Same, properSubset(s2Same, s2))
    fmt.Printf("%v ⊂ s3: %t\n", s2Same, properSubset(s2Same, s3))
 
    // option: delete.  it's built in.
    delete(s3, 3)
    fmt.Println("s3, 3 deleted:", s3)
}
 
func newSet(ms ...complex128) set {
    s := make(set)
    for _, m := range ms {
        s[m] = true
    }
    return s
}
 
func (s set) String() string {
    if len(s) == 0 {
        return "∅"
    }
    r := "{"
    for e := range s {
        r = fmt.Sprintf("%s%v, ", r, e)
    }
    return r[:len(r)-2] + "}"
}
 
func (s set) hasElement(m complex128) bool {
    return s[m]
}
 
func union(a, b set) set {
    s := make(set)
    for e := range a {
        s[e] = true
    }
    for e := range b {
        s[e] = true
    }
    return s
}
 
func intersection(a, b set) set {
    s := make(set)
    for e := range a {
        if b[e] {
            s[e] = true
        }
    }
    return s
}
 
func difference(a, b set) set {
    s := make(set)
    for e := range a {
        if !b[e] {
            s[e] = true
        }
    }
    return s
}
 
func subset(a, b set) bool {
    for e := range a {
        if !b[e] {
            return false
        }
    }
    return true
}
 
func equal(a, b set) bool {
    return len(a) == len(b) && subset(a, b)
}
 
func properSubset(a, b set) bool {
    return len(a) < len(b) && subset(a, b)
}