Set

containers.Set( of T ) holds each value at most once and answers "is it in?" in constant time on average. It is a Map with keys and no values.

#import "std/containers"

'' A Set has no order: copy its items into an Array and sort them.
sub Show( byref label as ustring, byref s as containers.Set( of int32 ) )
    var items = s.Items( )
    containers.Sort( items )
    print label; ":";
    for each x in items
        print x;
    next
    print
end sub

dim evens as containers.Set( of int32 ) = { 2, 4, 6, 8 }
dim small as containers.Set( of int32 ) = { 1, 2, 3, 4 }

'' Add says whether the value was new.
print "add 10: "; evens.Add( 10 )
print "add 4:  "; evens.Add( 4 )
print "contains 6: "; evens.Contains( 6 ); ", contains 7: "; evens.Contains( 7 )
evens.Remove( 10 )

'' The set operations change the set they are called on, so copy first.
dim both as containers.Set( of int32 ) = evens
both.IntersectWith( small )
Show( "evens and small", both )

dim either as containers.Set( of int32 ) = evens
either.UnionWith( small )
Show( "evens or small", either )

dim onlyEven as containers.Set( of int32 ) = evens
onlyEven.ExceptWith( small )
Show( "evens, not small", onlyEven )

Show( "evens itself", evens )

Output

add 10: true
add 4:  false
contains 6: true, contains 7: false
evens and small: 2 4
evens or small: 1 2 3 4 6 8
evens, not small: 6 8
evens itself: 2 4 6 8

Add returns true when the value is new and false when it was already there, so if seen.Add( x ) then is the natural way to do something once per distinct value. Contains asks without changing anything, and Remove returns whether there was something to remove.

The three operations change the set they are called on. Declaring dim both as containers.Set( of int32 ) = evens copies evens, so the example can apply each operation to a fresh copy and evens itself is unchanged at the end.

Like a Map, a Set has no order. Items( ) copies the values into an Array, which Show sorts before printing. When you want the values kept in order all the time, use an OrderedSet.

Activities

1. Use a Set( of ustring ) to print each distinct word of a sentence once.
2. Compute the values in exactly one of evens and small (the symmetric difference) from the operations above.