
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


#import <Foundation/Foundation.h>
 
int main (int argc, const char *argv[]) {
  @autoreleasepool {
 
    NSSet *s1 = [NSSet setWithObjects:@"a", @"b", @"c", @"d", @"e", nil];
    NSSet *s2 = [NSSet setWithObjects:@"b", @"c", @"d", @"e", @"f", @"h", nil];
    NSSet *s3 = [NSSet setWithObjects:@"b", @"c", @"d", nil];
    NSSet *s4 = [NSSet setWithObjects:@"b", @"c", @"d", nil];
    NSLog(@"s1: %@", s1);
    NSLog(@"s2: %@", s2);
    NSLog(@"s3: %@", s3);
    NSLog(@"s4: %@", s4);
 
    // Membership
    NSLog(@"b in s1: %d", [s1 containsObject:@"b"]);
    NSLog(@"f in s1: %d", [s1 containsObject:@"f"]);
 
    // Union
    NSMutableSet *s12 = [NSMutableSet setWithSet:s1];
    [s12 unionSet:s2];
    NSLog(@"s1 union s2: %@", s12);
 
    // Intersection
    NSMutableSet *s1i2 = [NSMutableSet setWithSet:s1];
    [s1i2 intersectSet:s2];
    NSLog(@"s1 intersect s2: %@", s1i2);
 
    // Difference
    NSMutableSet *s1_2 = [NSMutableSet setWithSet:s1];
    [s1_2 minusSet:s2];
    NSLog(@"s1 - s2: %@", s1_2);
 
    // Subset of
    NSLog(@"s3 subset of s1: %d", [s3 isSubsetOfSet:s1]);
 
    // Equality
    NSLog(@"s3 = s4: %d", [s3 isEqualToSet:s4]);
 
    // Cardinality
    NSLog(@"size of s1: %lu", [s1 count]);
 
    // Has intersection (not disjoint)
    NSLog(@"does s1 intersect s2? %d", [s1 intersectsSet:s2]);
 
    // Adding and removing elements from a mutable set
    NSMutableSet *mut_s1 = [NSMutableSet setWithSet:s1];
    [mut_s1 addObject:@"g"];
    NSLog(@"mut_s1 after adding g: %@", mut_s1);
    [mut_s1 addObject:@"b"];
    NSLog(@"mut_s1 after adding b again: %@", mut_s1);
    [mut_s1 removeObject:@"c"];
    NSLog(@"mut_s1 after removing c: %@", mut_s1);
 
  }
  return 0;
}