C++ Multiset

In C++, multisets play a crucial role within the STL (Standard Template Library). Multisets serve as associative containers that are closely related to sets, facilitating the storage of sorted values where the value itself acts as the key of type T. Unlike sets, multisets can accommodate duplicate keys. By default, it employs the < operator to compare the multiple keys. The value of the elements in a multiset can be inserted or deleted but cannot be altered.

Syntax

It has the following syntax:

_PRESERVE0__

In this syntax,

• ✅ T: It represents the type of element that is stored in the container multiset.
• ✅ Compare: It represents a comparison class that takes two arguments of the same type, bool, and returns a value. This argument is optional, and the binary predicate is the default value.
• ✅ Alloc: It represents the type of the allocator object that is used to define the storage allocation model.

Declaration and Initialization

In C++ , we can initialize and declare a multiset in several different ways, as in the following example:

Example

_PRESERVE1__

Output:

_PRESERVE2__

Explanation:

In this example, we have taken the required headers and a multiset of integers that have been initialized with some repeated values. After that, the multiset stores the elements in order by default, and duplicates are also allowed. The for loop traverses through the multiset and prints out all the elements, which displays them in ascending order.

Basic Operations of C++ Multiset

There are several operations that can be performed on a multiset. Some of them are as follows:

Inserting Elements

In C++, we can insert elements within a multiset by employing the insert method . The multiset will automatically maintain the elements in the order they are added.

Syntax

It has the following syntax:

_PRESERVE3__

C++ Example to Insert Element in Multiset

Let us take an example to illustrate how to insert an element in a multiset in C++.

Example

_PRESERVE4__

Output:

_PRESERVE5__

Explanation:

In this example, a multiset<int> identifier within the main function. The elements 10, 20, 10, and 30 are added using the insert method. As multisets permit duplicates and maintain sorted elements, the output will display the values in ascending order, including the duplicated 10. Subsequently, a for loop is utilized to iterate through the multiset and display each of its stored values.

Accessing Elements

In a multiset data structure, we must retrieve elements by their positions using an iterator. For example, if we wish to access the 3rd element, we have to move the begin iterator two positions forward by incrementing it. Alternatively, we can use the next or advance function instead of directly incrementing or decrementing the iterator.

C++ Example to Access Element in Multiset

Let's consider a scenario to demonstrate how to retrieve an item from the multiset in C++.

Example

#include <iostream>

#include <set>

using namespace std;  //using standard namespace

int main() {   //main function

    multiset<int> numbers = {40, 10, 30, 20, 10};

    cout << "Multiset elements: ";

    for (auto it = numbers.begin(); it != numbers.end(); ++it) {

        cout << *it << " ";

    }

    cout << endl;

    return 0;

}

Output:

Multiset elements: 10 10 20 30 40

Explanation:

In this instance, we create a multiset<int> containing elements {40, 10, 30, 20, 10}. Since a multiset organizes elements in ascending order and permits duplicates, the elements are sorted automatically. Subsequently, an iterator-based for loop traverses the multiset from start to finish, displaying each value by dereferencing the iterator with *it.

Finding Elements

In C++, the multiset data structure enables efficient value lookups using the find method. When called, the find function provides an iterator pointing to the located element or an end iterator if the element is not found.

Syntax

It has the following syntax:

iterator find(const value_type& val) const;

Here, we can conveniently retrieve the initial and final element by utilizing the begin and end iterators.

C++ Example to Find the Elements in Multiset

Let's consider an example to demonstrate how to locate elements within a multiset in C++.

Example

#include <iostream>

#include <set>

using namespace std;   //using standard namespace

int main() {   //main function

    multiset<int> numbers = {10, 20, 30, 40, 20};

    int key = 20;

    auto it = numbers.find(key);

    if (it != numbers.end()) {

        cout << "Element " << key << " found in the multiset." << endl;

    } else {

        cout << "Element " << key << " not found." << endl;

    }

    return 0;

}

Output:

Element 20 found in the multiset.

Explanation:

In this instance, we create a multiset that includes various integers and try to find the number 20 by employing the find function. If the value is discovered, a notification confirming the element's presence is displayed; otherwise, a message indicating it was not found is shown. Since multiset allows for duplicates, the find method will provide an iterator pointing to one of the instances of the specified value.

Traversing Elements

In C++, navigating through containers follows a familiar pattern, and multisets can be effectively looped through using a range-based for loop or by leveraging the begin and end iterators. To iterate over all elements with identical keys, substitute begin and end with the range provided by the equal_range function.

C++ Example to Traverse Elements

Let's consider an illustration to showcase the process of navigating elements in C++.

Example

#include <iostream>

#include <set>

using namespace std;   //using standard namespace

int main() {   //main function

    multiset<int> numbers = {50, 10, 30, 20, 40};

    cout << "Multiset elements: ";

    for (auto it = numbers.begin(); it != numbers.end(); ++it) {

        cout << *it << " ";

    }

    cout << endl;

    return 0;

}

Output:

Multiset elements: 10 20 30 40 50

Explanation:

In this instance, since a multiset organizes elements in a sorted manner, it will arrange them as {10, 20, 30, 40, 50} automatically. Subsequently, a for loop utilizing an iterator traverses from begin to end, dereferencing each iterator to retrieve and display the values.

Removing Elements

If we need to eliminate elements from a multiset, the erase function can be employed. This function can be invoked by supplying either the specific value or an iterator. Nonetheless, when a value is specified, it will delete all occurrences of that particular value.

C++ Example to Remove Elements

Let's consider a scenario to demonstrate the process of deleting elements in a C++ multiset.

Example

#include <bits/stdc++.h>

#include <iostream>

#include <set>

using namespace std;    //using standard namespace

int main() {   //main function

    multiset<int> numbers = {10, 20, 20, 30, 40};

    auto it = numbers.find(20);

    if (it != numbers.end()) {

        numbers.erase(it);   //using erase function

    }

    numbers.erase(30);

    cout << "Multiset after deletion: ";

    for (auto x: numbers) cout << x << " ";

    cout << endl;

    return 0;

}

Output:

Multiset after deletion: 10 20 40

Explanation:

In this illustration, we generate a collection of integers containing duplicates. We eliminate one instance of the number 20 using the find function followed by erase(it), and proceed to remove all occurrences of the number 30 using erase(30). Finally, the program displays the remaining elements in sorted order.

Sort the Multiset in Descending Order

If there is a need to retrieve the elements within the multiset in a descending order, the syntax can be adjusted as shown below:

multiset<int, greater<int>> my_multiset ;

Below is a C++ code snippet demonstrating how to sort a multiset in descending order:

#include <iostream>
#include <set>

int main() {
    std::multiset<int, std::greater<int>> myMultiset = {5, 2, 8, 5, 1, 9};

    std::cout << "Multiset elements before sorting: ";
    for (const auto &elem : myMultiset) {
        std::cout << elem << " ";
    }

    std::cout << "\nMultiset elements after sorting in descending order: ";
    for (auto it = myMultiset.rbegin(); it != myMultiset.rend(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

Let's consider an example to demonstrate how to arrange the multiset in a descending order using C++.

Example

#include <iostream>

#include <set>

using namespace std;  //using standard namespace

int main() {   //main function

    multiset<int, greater<int>> numbers = {10, 40, 20, 30, 20};

    cout << "Multiset in descending order: ";

    for (int num : numbers) {

        cout << num << " ";

    }

    cout << endl;

    return 0;

}

Output:

Multiset in descending order: 40 30 20 20 10

Explanation:

In this illustration, we instantiate a multiset employing a personalized comparator greater<int>, arranged to store elements in a descending sequence. The multiset is initialized with specific values and displayed through a range-based loop. Subsequently, the displayed output will exhibit the elements arranged in descending order, from the greatest to the smallest.

Swapping Multisets Using swap

In C++, swapping two multiset containers allows for efficiently exchanging their contents. The swap method performs a constant-time operation by swapping internal pointers.

In the following C++ example, the swap function is utilized to interchange the contents of two multisets:

#include <iostream>
#include <set>

int main() {
    std::multiset<int> firstSet = {1, 2, 3};
    std::multiset<int> secondSet = {4, 5, 6};

    firstSet.swap(secondSet);

    std::cout << "First set after swapping:";
    for (const auto& element : firstSet) {
        std::cout << " " << element;
    }

    std::cout << "\nSecond set after swapping:";
    for (const auto& element : secondSet) {
        std::cout << " " << element;
    }

    return 0;
}

Let's consider an instance to demonstrate the process of exchanging multisets using the swap function in C++.

Example

#include <iostream>

#include <set>

using namespace std;   //using standard namespace

int main() {   //main function

    multiset<int> set1 = {10, 20, 30};

    multiset<int> set2 = {40, 50};

    cout << "Before swap:" << endl;

    cout << "Set1: ";

    for (int val : set1) cout << val << " ";

    cout << "\nSet2: ";

    for (int val : set2) cout << val << " ";

    set1.swap(set2);

    cout << "\n\nAfter swap:" << endl;

    cout << "Set1: ";

    for (int val : set1) cout << val << " ";

    cout << "\nSet2: ";

    for (int val : set2) cout << val << " ";

    return 0;

}

Output:

Before swap:

Set1: 10 20 30 

Set2: 40 50 

After swap:

Set1: 40 50 

Set2: 10 20 30

Explanation:

In this instance, we create two multisets with distinct values, display both of them, and proceed to interchange them using the swap method. After the swap operation, the multisets are displayed once more to illustrate the successful exchange of their contents.

C++ Multiset empty and size Methods

In C++, the capacity functions empty and size can be employed with multisets to determine if the multiset is empty or to retrieve its size.

The empty function provides a return of 1 for true and 0 for false values.

• ✅ 1 (true) signifies that the multiset is devoid of elements.
• ✅ 0 (false) indicates that the multiset contains one or more elements.

C++ Multiset Example using empty and size methods

Let's consider a scenario to demonstrate the multiset by employing the empty and size functions within C++.

Example

#include <iostream>

#include <set>

using namespace std;   //using standard namespace

int main() {   //main function

    multiset<int> data = {5, 15, 15, 25, 35, 35, 35};

    cout << "Multiset contents before clear: ";

    for (int val : data) {

        cout << val << " ";

    }

    cout << "\nIs multiset empty? " << (data.empty() ? "Yes" : "No") << endl;

    cout << "Multiset size: " << data.size() << endl;

    data.clear();

    cout << "\nMultiset contents after clear: ";

    for (int val : data) {

        cout << val << " ";

    }

    cout << "\nIs multiset empty? " << (data.empty() ? "Yes" : "No") << endl;

    cout << "Multiset size: " << data.size() << endl;

    return 0;

}

Output:

Multiset contents before clear: 5 15 15 25 35 35 35 

Is multiset empty? No

Multiset size: 7

Multiset contents after clear: 

Is multiset empty? Yes

Multiset size: 0

Explanation:

In this instance, we instantiate a multiset containing duplicate values, display its elements, verify its emptiness and size, and then remove all elements using the clear method. Subsequently, the multiset is displayed again post-clearing, and its emptiness and size are reassessed to confirm that it is now empty.

Member Functions

Below is the compilation of all member methods of multiset:

Constructor/Destructor

The provided table displays various constructor and destructor functions utilized in C++ Multiset.

Iterators

The provided table displays various iterator functions commonly employed in C++ Multisets.

Capacity

The provided table displays various capacity functions utilized in C++ Multiset.

Modifiers

The provided table displays various modifier functions utilized in C++ Multiset.

Observers

The provided table displays various modifier functions utilized in C++ Multiset.

Operations

The provided table displays various operations commonly utilized in C++ Multiset.

Allocator

The provided table displays various allocation functions utilized in C++ Multiset.

Non-Member Overloaded Functions

The provided table displays various non-member overloaded functions utilized in C++ Multiset.

Conclusion

In summary, C++ STL includes multisets. Multisets are sorted containers similar to sets, but they allow duplicate keys. Multisets enable comparison of keys using the default operator. While items in a multiset can be added or deleted, their values cannot be altered.

C++ STL Multiset MCQs

1) Which of the following is true about multiset in C++?

• ✅ It only stores unique elements
• ✅ It stores unsorted values
• ✅ It allows duplicate values
• ✅ It does not support iterators

2) Which of the following functions is used to find an element in a multiset?

• ✅ search
• ✅ contains
• ✅ locate
• ✅ find

3) What does erase(value) do in a multiset?

• ✅ Removes only one instance of the value
• ✅ Removes all instances of the value
• ✅ Throws an error if duplicates exist
• ✅ Removes the smallest instance

4) Which of the following statements is correct regarding element modification in a multiset?

• ✅ Elements cannot be modified once inserted
• ✅ Elements can be directly modified using iterators
• ✅ Elements can be modified using set function
• ✅ Elements can be accessed and modified via indexing

a) Items are unable to be altered once they have been added.

5) What happens if we use the swap function on two multisets in C++?

• ✅ Only unique values are retained
• ✅ Values are merged
• ✅ The contents are exchanged
• ✅ Nothing happens