Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Methods of Set
3.
 
4.
 
5.
 
6.
 
7.
 
8.
 
9.
 
10.
 
11.
 
12.
 
12.1.
C++ Implementation
13.
FAQs
14.
Key Takeaways
Last Updated: Mar 27, 2024

Implementing Sets Without C++ STL Containers

Author Anant Dhakad
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

A collection of unique elements is referred to as a set. Once an element has been added, it cannot be changed. The operations union, intersection, power set, cartesian product, set difference, complement, and equality are all linked with sets. By set, we mean a mathematical set storing N unique elements.

 

Intersection(A∩B)

Union(A⋃B)

Complement of A (AC)

 

Difference (B - A)

Difference (A - B)

Source: https://simple.wikipedia.org/wiki/Venn_diagram

 

Methods of Set

Method

Description

Time & Space Complexity

insert(value) 

Inserts element with value as a key in the set.

Time: O(h), where ‘h’  is the height of the tree.

Space: O(1)

_union(s) 

Returns a set created by performing union with ‘set s’.

Time: O((n+m)*h), where ‘h’  is the height of the tree and n&m is the number of elements in sets.

Space: O(n+m)

_intersection(s)

Returns a set created by performing intersection with ‘set s’.

Time: O(n*h), where ‘h’  is the height of the tree and n&m is the number of elements in sets.

Space: O(n)

_complement(U)

Returns complement of a set with Universal ‘Set U’.

Time: O(n*h), where ‘h’  is the height of the tree and n&m is the number of elements in sets.

Space: O(n)

_array()

Returns an array, which contains all the elements of the set.

Time: O(n)

Space: O(n)

_size()

Returns the number of elements in the set.

Time: O(1)

Space: O(1)

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

 

 

 

 

 

 

 

 

 

 

Also see, Euclid GCD Algorithm

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

/* A node of a BST */
template <typename T>
struct Node {

   T val; /* Node's val */
   Node* left; /* Left child's Pointer */
   Node* right; /* Right child's Pointer */

public:
   /* To display Inorder traversal of the BST */
   void inorder(Node* root){
       if (root == NULL)return;
       inorder(root->left);
       cout << root->val << " ";
       inorder(root->right);
   }

   /**
       Function to check if BST contains a node with the given val
     
       @param root pointer to the root node
       @param key the val to search
       @return if present -> 1, if not present -> 0
   */
   int haveNode(Node* root, T key){
       if (root == NULL)return 0;
       int x = root->val == key ? 1 : 0;
       return x | haveNode(root->left, key) | haveNode(root->right, key);
   }

   /**
       Function to insert a node with given val into the BST
     
       @param root pointer to the root node
       @param key the val to insert
       @return root of new bst
   */
   Node* insert(Node* root, T key){

       /* When a NULL node is discovered, add the node */
       if (root == NULL){
           Node<T>* newNode = new Node<T>;
           newNode->val = key;
           newNode->left = newNode->right = NULL;
           return newNode;
       }

       /* If val is smaller than the current node, go to the left subtree. */
       if (key < root->val){
           root->left = insert(root->left, key);
           return root;
       }

       /* If val is greater than the current node, traverse the right subtree. */
       else if (key > root->val) {
           root->right = insert(root->right, key);
           return root;
       }
     
       return root;
   }
};

/* Set class (implemented using BST) */
template <typename T>
class Set {

   Node<T>* root; /* pointer to the root the BST tree */
   int size; /* number of elements in the set */

public:
   /* Default constructor initializing the root and size. */
   Set(){
       root = NULL;
       size = 0;
   }

   Set(const Set& s){
       root = s.root;
       size = s.size;
   }

   /**
       function to insert an element to the set.

       @param val the element to add to the set
   */
   void insert(const T val){
       if (root->haveNode(root, val) == 1)return;

       root = root->insert(root, val);
       size++;
   }

   /**
       This function returns the union of two sets.
     
       @param s set to find union with
       @return the union set
   */
   Set _union(Set& s){
       Set<T> res;

       /* Return 2nd set if 1st set is empty */
       if (root == NULL) return s;
       /* Return 1st set if 2nd set is empty */
       if (s.root == NULL)return *this;

       /* Adding the elements of the 1st set in the resultant set */
       stack<Node<T>*> utilstack;
       utilstack.push(root);

       /* Preorder traversal of the BST */
       while (!utilstack.empty()){
           Node<T>* node;
           node = utilstack.top();
           utilstack.pop();

           // Adding val to the resultant set
           res.insert(node->val);

           if(node->right)utilstack.push(node->right);
           if(node->left)utilstack.push(node->left);
       }

       /* Adding the elements of the 2nd set in the resultant set */
       stack<Node<T>*> utilstack1;
       utilstack1.push(s.root);

       while (!utilstack1.empty()){
           Node<T>* node;
           node = utilstack1.top();
           utilstack1.pop();

           // Adding val to the resultant set
           res.insert(node->val);

           if(node->right)utilstack1.push(node->right);
           if(node->left)utilstack1.push(node->left);
       }

       return res;
   }

   /**
       This function returns the intersection of two sets.
     
       @param s the set to find the intersection with
       @return the intersection set
   */
   Set _intersection(Set& s){
       Set<T> res;
       stack<Node<T>*> utilstack;
       utilstack.push(root);

       while (!utilstack.empty()){
           Node<T>* node;
           node = utilstack.top();
           utilstack.pop();
           if (s.contains(node->val)){
               res.insert(node->val);
           }
           if(node->right)utilstack.push(node->right);
           if(node->left)utilstack.push(node->left);
       }
       return res;
   }

   /**
       This function returns the complement of the sets.
     
       @param U the universal set
       @return the complement set
   */
   Set _complement(Set& U){
       return (U - *this);
   }

   /**
       Overloading '-' operator to find the difference of two sets
     
       @param s the set to be subtracted
       @return the Difference set
   */
   Set operator-(Set& s){
       Set<T> res;
       stack<Node<T>*> utilstack;
       utilstack.push(this->root);

       while (!utilstack.empty()){
           Node<T>* node;
           node = utilstack.top();
           utilstack.pop();
           if (s.contains(node->val) == 0)res.insert(node->val);

           if(node->right)utilstack.push(node->right);
           if(node->left)utilstack.push(node->left);
       }
       return res;
   }

   /**
       Function to check if set are equal
     
       @param s set to check equality with
       @return if equal -> true, if not equal -> false
   */
   bool operator==(Set& s){
       if (s._size() != size)return false;

       stack<Node<T>*> utilstack;
       utilstack.push(this->root);

       while (!utilstack.empty()){
           Node<T>* node;
           node = utilstack.top();
           utilstack.pop();
           if (!s.contains(node->val))return false;

           if(node->right)utilstack.push(node->right);
           if(node->left)utilstack.push(node->left);
       }
       return true;
   }

   /**
       Function to display the cartesian product of two sets
     
       @param s the set to find product with
   */
   void printProduct(Set& s){
       int size2 = s._size();
       T *A = _array(), *B = s._array();

       cout << "{ ";
       for(int i = 0; i < size; i++){
           for(int j = 0; j < size2 ; j++){
               cout << "{ " << A[i] << " " << B[j] << " } ";
           }
       }
       cout << "}" << endl;
   }

   /**
       Function to display the power set of the set
   */
   void printPowerSet(){
       int n = pow(2, size);
       T* A = _array();
       while(n-- > 0){
           cout << "{ ";
           for(int i = 0; i < size; i++){
               if((n & (1 << i)) == 0){
                   cout << A[i] << " ";
               }
           }
           cout << "}" << endl;
       }
   }

   /**
       Function to convert the set into an array.
     
       @return array of set elements
   */
   T* _array(){
       T* A = new T[size];
       int i = 0;
       stack<Node<T>*> utilstack;
       utilstack.push(this->root);

       while(!utilstack.empty()){
           Node<T>* node;
           node = utilstack.top();
           utilstack.pop();

           A[i++] = node->val;

           if(node->right)utilstack.push(node->right);
           if(node->left)utilstack.push(node->left);
       }
       return A;
   }

   /**
       Function to check whether the set contains an element
     
       @param key the element to search
       @return if exist -> true, not exist -> false
   */
   bool contains(T key){
       return root->haveNode(root, key) ? true : false;
   }

   // Function to print the contents of the set
   void printSet(){
       cout << "{ ";
       root->inorder(root);
       cout << "}" << endl;
   }

   /**
       get the current size of the set
     
       @return size of set
   */
   int _size(){
       return size;
   }
};

int main(){
   Set<int> A;

   /* inserting elements in Set A */
   A.insert(1); A.insert(2); A.insert(3); A.insert(2);

   /* printing the contents of Set A */
   cout << "A = ";
   A.printSet();
   cout << "P(A) = " << '\n';
   A.printPowerSet();

   /* Check if Set A contains some elements */
   cout << "A " << (A.contains(7) ? "contains" : "does not contain") << " 7" << '\n';
   cout << "A " << (A.contains(9) ? "contains" : "does not contain") << " 9" << '\n';
   cout << '\n';

   Set<int> B;

   /* inserting elements in Set B */
   B.insert(1); B.insert(2); B.insert(4);

   /* printing the contents of Set B */
   cout << "B = ";
   B.printSet();
   cout << "P(B) = " << '\n';
   B.printPowerSet();
   cout << '\n';

   Set<int> C;
   C.insert(1); C.insert(2); C.insert(4);

   /* printing the contents of Set C */
   cout << "C = ";
   C.printSet();
   cout << '\n';

   /* F = A - B */
   Set<int> F = A - B;
   cout << "A - B = ";
   F.printSet();
   cout << '\n';

   /* D = A Union B */
   Set<int> D = A._union(B);
   cout << "A union B = ";
   D.printSet();
   cout << '\n';

   /* E = A intersection B */
   Set<int> E = A._intersection(B);
   cout << "A intersection B = ";
   E.printSet();
   cout << '\n';

   /* printing the product */
   cout << "A x B = ";
   A.printProduct(B);
   cout << '\n';

   // Equality tests
   cout << "Equality of Sets:" << '\n';

   cout << "A " << ((A == B) ? "" : "!") << "= B" << '\n';
   cout << "B " << ((B == C) ? "" : "!") << "= C" << '\n';
   cout << "A " << ((A == C) ? "" : "!") << "= C" << '\n';
   cout << '\n';

   Set<int> U;
   U.insert(1); U.insert(2); U.insert(3); U.insert(4);
   U.insert(5); U.insert(6); U.insert(7);

   // Complements of the respective Sets
   Set<int> A1 = A._complement(U);
   Set<int> B1 = B._complement(U);
   Set<int> C1 = C._complement(U);

   cout << "A' = ";
   A1.printSet();
   cout << "B' = ";
   B1.printSet();
   cout << "C' = ";
   C1.printSet();

   return 0;
}

 

Output

A = { 1 2 3 }
P(A) =
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }
A does not contain 7
A does not contain 9

B = { 1 2 4 }
P(B) =
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 4 }
{ 1 4 }
{ 2 4 }
{ 1 2 4 }

C = { 1 2 4 }

A - B = { 3 }

A union B = { 1 2 3 4 }

A intersection B = { 1 2 }

A x B = { { 1 1 } { 1 2 } { 1 4 } { 2 1 } { 2 2 } { 2 4 } { 3 1 } { 3 2 } { 3 4 } }

Equality of Sets:
A != B
B = C
A != C

A' = { 4 5 6 7 }
B' = { 3 5 6 7 }
C' = { 3 5 6 7 }


You can also practice with the help of Online C++ Compiler

FAQs

  1. What is the worst-case time complexity of insertion in the implemented set (BST-based)?
    The time complexity of insertion in a BST-based set is O(h), where h is the height of BST.
     
  2. How to improve insertion time complexity in this implementation?
    To improve the worst-case time complexity of insertion, we can use AVL Tree or Red-Black Tree instead of BST. 
    The worst-case time complexity of insertion in AVL Tree & Red-Black Tree is O(log(n)), where n is the total number of nodes in the tree.
     
  3. What is the time complexity of search, insertion, and deletion in STL set in C++?
    The time complexity for search, insertion and deletion is O(log(n)).
     
  4. What is the underlying data structure of STL set & unordered_set in C++?
    Red-Black Tree is used for implementing the STL set in C++. And the hash table is used for implementing unordered_set.

 

Key Takeaways

Cheers if you reached here!! In this blog, we saw the implementation of a set in C++ without using STL containers.

Check out the following problems - 

 

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!

 

Previous article
Product of array except self
Next article
Count the Total Numbers With No Repeated Digits in a Range
Live masterclass