Question

In this problem we consider a data structure for maintaining a multi-set M. We want to support the following operations:

• Init(M): create an empty data structure M.

• Insert(M, i): insert (one copy of) i in M.

• Remove(M, i): remove (one copy of) i from M.

• F requency(M, i): return the number of copies of i in M.

• Select(M, k): return the kth element in the sorted order of elements in M.

Answer 1

Code in C++ using STL :-

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

void Insert(multiset <int>& M, int i)
{
        M.insert(i);
        cout<<i<<" Inserted \n";
}

void Remove(multiset <int>& M, int i)
{
        int num = M.erase(i);
        cout<<"("<<num<<") values matching "<<i<<" Removed \n";
}

int Frequency(multiset <int>& M, int i)
{
        int freq = M.count(i);
        return freq;
}

int Select(multiset <int>& M, int k)
{
        multiset <int> :: iterator it = M.begin();
        for(int i=0; i<k-1; i++)
                it++;
        return *it;
}

void PrintSet(multiset <int>& M)
{
        multiset <int> :: iterator it;
        cout<<"Printing the multiset: ";
        for (it = M.begin(); it != M.end(); ++it) 
    { 
        cout<< *it << '\t';
    } 
    cout << endl;
}

int main() 
{ 
        // empty multiset container Init()
        multiset <int> M; 
        
        // insert elements 
        Insert(M, 40);   
        Insert(M, 30);   
        Insert(M, 60);   
        Insert(M, 20);   
        Insert(M, 30);   
        Insert(M, 40);
        Insert(M, 10);
        Insert(M, 30);
        Insert(M, 60);
        Insert(M, 50);
        // Print the Multiset
        PrintSet(M);
        
        // Remove Elements
        Remove(M, 40);
        Remove(M, 10);
        PrintSet(M);
        
        // Check frequency of an element
        cout<<"Frequency of 30 in multiset: "<<Frequency(M, 30)<<endl;
        
        // Select a Kth element from the multiset
        cout<<"Element at Position 3: "<<Select(M, 3)<<endl;
        
        return 0;
} 

Hope this helps.

Good Luck :-)