Multisets

In C++, a multiset is a container class template from the Standard Template Library (STL) that stores elements in a sorted order.

A multiset stores multiple elements of the same value and allows duplicates. Each element in a multiset is sorted according to their comparison operator, which is by default the less-than operator.

Multisets are implemented as binary search trees, which provides efficient insertion, deletion, and searching of elements. They have a time complexity of O(log n) for these operations.

Multisets are useful in situations where you need to store multiple elements of the same value in a sorted order. For example, you could use a multiset to store the grades of all students in a class. The multiset would automatically sort the grades and allow duplicate grades.

You can also use a multiset to implement various algorithms such as finding the median or mode of a set of numbers. The multiset container provides a set of member functions to perform these operations.


#include <iostream>
#include <set>
using namespace std;

int main() {
    // Create a multiset of integer values
    multiset<int> myMultiset;

    // Insert elements in the multiset
    myMultiset.insert(10);
    myMultiset.insert(20);
    myMultiset.insert(20);
    myMultiset.insert(30);
    myMultiset.insert(30);

    // Print the elements in the multiset
    cout << "Current multiset elements: " << endl;
    for (auto it = myMultiset.begin(); it != myMultiset.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // Count the number of occurrences of a value in the multiset
    int count = myMultiset.count(20);
    cout << "Number of occurrences of 20 in the multiset: " << count << endl;
    cout << endl;

    // Search for an element in the multiset
    auto it = myMultiset.find(30);
    if (it != myMultiset.end()) {
        cout << "Element found in the multiset: " << *it << endl;
    }
    else {
        cout << "Element not found in the multiset" << endl;
    }

    // Erase all occurrences of a value from the multiset
    myMultiset.erase(20);

    // Print the modified multiset
    cout << "Modified multiset after erasing all occurrences of 20: " << endl;
    for (auto it = myMultiset.begin(); it != myMultiset.end(); it++) {
        cout << *it << endl;
    }
    cout << endl;

    // Clear all of the elements of the multiset
    myMultiset.clear();

    // Check if the multiset is empty
    if (myMultiset.empty()) {
        cout << "Multiset is empty" << endl;
    }
    else {
        cout << "Multiset is not empty" << endl;
    }

    return 0;
}

This implementation creates an empty multiset of integer values myMultiset. It then adds elements to the multiset using the insert() function. The elements are printed to the console using a for loop and the begin() and end() functions of the multiset. Note that the multiset can contain multiple occurrences of the same value.

The count() function is used to count the number of occurrences of a value in the multiset. The find() function is used to search for an element in the multiset. If the element is found, its value is printed to the console.

The erase() function removes all occurrences of a value from the multiset. The modified multiset is printed to the console.

The clear() function deletes all of the elements of the multiset, and the empty() function checks if the multiset is empty. Finally, the program returns 0.

PRACTICE PROBLEMS :

Max chunks to make sorted