Set Structures

Set Structures

A set is a data structure that maintains a collection of elements. The basic operations of sets are element insertion, search and removal. The benefit of the set structure is that it maintains the order of the elements and provides functions that are not available in unordered_set.

The following code creates a set that contains integers, and shows some of the operations. The function 'insert' adds an element to the set, the function 'count' returns the number of occurrences of an element in the set, and the function 'erase' removes an element from the set.

      set<int> s;
      s.insert(3);
      s.insert(2);
      s.insert(5);
      cout << s.count(3) << "\n"; // 1
      cout << s.count(4) << "\n"; // 0
      s.erase(3);
      s.insert(4);
      cout << s.count(3) << "\n"; // 0
      cout << s.count(4) << "\n"; // 1

A set can be used mostly like a vector, but it is not possible to access the elements using the [] notation. The following code creates a set, prints the number of elements in it, and then iterates through all the elements:

      set<int> s = {2,5,6,8};
      cout << s.size() << "\n"; // 4
      for (auto x : s) {
      cout << x << "\n";
      }

An important property of sets is that all their elements are distinct. Thus, the function count always returns either 0 (the element is not in the set) or 1 (the element is in the set), and the function insert never adds an element to the set if it is already there. The following code illustrates this:

      set<int> s;
      s.insert(5);
      s.insert(5);
      s.insert(5);
      cout << s.count(5) << "\n"; // 1

The function erase removes all instances of an element from a multiset:

      s.erase(5);
      cout << s.count(5) << "\n"; // 0

JAVA EQUIVALENT

The set interface present in the "java.util" package and extends the Collection interface is an unordered collection of objects in which duplicate values cannot be stored.

The Set interface is declared as:

     public interface Set extends Collection

Since Set is an interface, objects cannot be created of the type set. We always need a class which extends this list in order to create an object. This type-safe set can be defined as:

     // Ob is the type of the object to be stored in Set
     Set<Ob> set = new HashSet<Ob> ();

In order to add an element to the Set, we can use the add() method.

     Set<String> hs = new HashSet<String>(); 
     hs.add("B"); 
     hs.add("B"); 
     hs.add("A"); // hs = [A,B]

The values can be removed from the Set using the remove() method.

    hs.remove("B"); // hs=[A]

Iterating though the Set:

     for (String value : hs) 
        System.out.print(value + ", "); 

References:

https://www.geeksforgeeks.org/set-in-cpp-stl/

https://www.geeksforgeeks.org/set-in-java/