Set - C P P

• Ordered set
• Multiset
• Unordered Set

Ordered set

• Theory
  • Implemented using balanced BST
  • Contains unique elements
  • Elements are in sorted order
  • Random access is not possible
• STL Commands
  • #include <set> => Header file to include
  • set<dataType> var => Initialize a set
  • set<int, greater<int>> var => Stores in descending order, Custom Comparator
  • var.insert(n) => Inserts a value, Time Complexity is O(logn)
  • var.erase(s.begin) => Delete the element which iterator is pointing to, Time Complexity is O(logn)
  • var.count(value) => Returns boolean 1 if element is present, 0 if not present, Time Complexity is O(logn)
  • *var.lower_bound(n) => Returns a number greater than or equal to given number
  • *var.upper_bound(n) => Returns a number greater than given number
  • var.size() => Returns the size of the set, Time Complexity is O(1)
  • var.begin() => Returns iterator to first element, Time Complexity is O(1)
  • var.end() => Returns iterator to last element, Time Complexity is O(1)
  • var.empty() => Returns boolean value true if set is empty, Time Complexity is O(1)
  • set<int>::iterator itr = var.find(n) => Gives the iterator to the element "n" if it is found otherwise returns s.end()
    • itr++ => Moves forward by one position
    • *itr => Returns value
• Other Commands
  • Print all distinct elements

      for(auto var1 : var) {
        cout << var1;
      }
    

  • Iterate from starting element to end and print

      for (auto i = var.begin(); i != var.end(); i++) {
        cout << *i;
      }
    

  • Iterate from end element to start and print in reverse, var.rbegin() gives reverse iterator from end

      for (auto i = var.rbegin(); i != var.rend(); i++) {
        cout << *i;
      }
    

Multiset

• Theory
  • Like ordered set but Can contain duplicates
• STL Commands
  • multiset<dataType> var
  • var.insert(value)
  • for(auto var1 : var) {cout << var1; } => Prints all even duplicates
  • var.erase(n) => Deletes all occurrences of this element, To delete specific give pointer to that specific element
  • var.find(n) => Returns pointer to the first element

Unordered Set

• Theory
  • Implemented using Hashing
  • Contains unique elements
  • Elements are not in sorted order
• STL Commands
  • #include <unordered_set> => Header file to include
  • unordered_set<dataType> var => Initialize
  • for(auto var1 : var) {cout << var1;} => Prints all elements in random order
  • var.insert(value)
  • var.find(value) => Returns iterator of the element if found, Returns var.end() if not found
  • var.begin()
  • var.end()
  • var.count(value) => Returns 1 if element is present, 0 if not present
  • var.size()
  • var.clear()
  • var.erase(value)
  • var.erase(var.begin(), var.end()) => Erase range of elements, 2nd parameter is exclusive