Set  

  • Set:

    • a collection of unique elements

  • Examples:

    • { 2, 3, 5, 7 }                        // prime numbers < 10
    • {"A", "E", "I", "O", "U"}    // vowels

  • Set operations:

    • Union = combine the elements from both sets

    • Intersection = finds the common elements in both sets

    • Difference = finds the elements in the first set that is not in the second set

  Sets in C++  

  • Defining a set: 

      #include <set>

  set<int> set1;
  // Defines an empty set

  set<int> set2 = {3, 5, 2, 1};
  // Defines the set {1,2,3,5}

  • Accessing values stored in a set: 

      Cannot access a single element in a set

  Traversing a set:

    for ( auto p = set2.begin(); p != set2.end(); p++ )
         cout << *p << " ";

Demo: set.cc

  Set in C++  

  • Inserting values into a set:   (note: set2 = {1,2,3,5}) 

      set2.insert(3);    // No change because:  3 ∈ set2
  set2.insert(4);    // result: {1,2,3,4,5}

  • Removing values from a set:   (note: set2 = {1,2,3,4,5}) 

      set2.erase(0);     // No change because:  0 ∉ set2
  set2.erase(4);     // result: {1,2,3,5}

  • Updating values stored in a set:

    • Values in a set cannot be updated.     Replace a value by:

      1. Remove the value and then
      2. Insert the new value

  Set operations in C++  

  • Membership test: 

        // test if 0 is in set2
    if ( set2.find(0) != set2.end() )
        cout << "0 is in set2" << endl;
    else
        cout << "0 is NOT in set2" << endl;

  • Union: 

      #include <algorithm>   // Must use this library
		       
  set<int> set1 = {5,6,7};
  set<int> set2 = {1,2,3,5}
  set<int> out;                             // Output

  set_union( set1.begin(), set1.end(),
	     set2.begin(), set2.end(),
	     inserter(out, out.begin())  ); // out = {1,2,3,5,6,7}

  Set operations in C++  

  • Intersection:  (Must use algorithm library) 

      set<int> set1 = {5,6,7};
  set<int> set2 = {1,2,3,5}
  set<int> out;                             // Output

  set_intersection( set1.begin(), set1.end(),
	            set2.begin(), set2.end(),
	            inserter(out, out.begin())  ); // out = {5}

  • Difference:   set2 − set1  (Must use algorithm library) 

      set<int> set1 = {5,6,7};
  set<int> set2 = {1,2,3,5}
  set<int> out;                             // Output

  set_difference( set2.begin(), set2.end(),
	          set1.begin(), set1.end(),
	          inserter(out, out.begin())  ); // out = {1,2,3}

  Sets in Python  

  • Defining a set: 

      set1 = set()
  # Defines an empty set
  # Note: do not use {}, it's a dictionary !

  set2 = {3, 5, 2, 1};
  # Defines the set {1,2,3,5}

  • Accessing values stored in a set: 

      Cannot access a single element in a set

  Traversing a set:

    for i  in  set2:
         print(i)

  Set in Python  

  • Inserting values into a set:   (note: set2 = {1,2,3,5}) 

      set2.add(3);    # No change because:  3 ∈ set2
  set2.add(4);    # result: {1,2,3,4,5}

  • Removing values from a set:   (note: set2 = {1,2,3,4,5}) 

      set2.remove(0);     # No change because:  0 ∉ set2
                      # Warning: will cause KeyError exception
  
  set2.remove(4);     # result: {1,2,3,5}

  • Updating values stored in a set:

    • Values in a set cannot be updated.

      ( Replace a value by remove followed by insert)

  Set operations in Python  

  • Membership test: 

        // test if 0 is in set2
    if  0 in set2:
        print("0 is in set2")
    else:
        print("0 not in set 2")

  • Union: 

      set1 = {5,6,7};
  set2 = {1,2,3,5}

  out = set1.union(set2)     # out = {1,2,3,5,6,7}

  Set operations in Python  

  • Intersection:  (Must use algorithm library) 

      set1 = {5,6,7};
  set2 = {1,2,3,5}

  out = set1.intersection(set2)   # out = {5}

  • Difference:   set2 − set1 

      set1 = {5,6,7};
  set2 = {1,2,3,5}

  out = set2.difference(set1)    # out = {1,2,3}

Demo: set.py