C++ Multiset

In C++, multisets are an essential part of the STL (Standard Template Library) . Multisets are associative containers similar to sets that help to store sorted values (the value is itself the key of type T). Multiset can have duplicate keys, unlike Set , which stores unique keys. By default, it utilizes 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:

template < class T,                             // multiset::key_type/value_type  

           class Compare = less<T>,        // multiset::key_compare/value_compare  

           class Alloc = allocator<T>         // multiset::allocator_type  

           > class multiset;

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

#include <iostream>

#include <set>

using namespace std;  //using standard namespace

int main() {  //main function

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

    cout << "Multiset elements: ";

    for (int num : numbers) {

        cout << num << " ";

    }

    cout << endl;

    return 0;

}

Output:

Multiset elements: 10 10 20 20 30 40

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:

multiset_name.insert(element);

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

#include <iostream>

#include <set>

using namespace std;  //using standard namespace

int main() {    //main function

    multiset<int> numbers;

    numbers.insert(10);

    numbers.insert(20);

    numbers.insert(10); 

    numbers.insert(30);

    cout << "Multiset elements: ";

    for (int num : numbers) {

        cout << num << " ";

    }

    cout << endl;

    return 0;

}

Output:

Multiset elements: 10 10 20 30

Explanation:

In this example, a multiset<int> named number is declared in the main function. Elements 10, 20, 10, and 30 are inserted using the insert function. Since multiset allows duplicates and keeps elements sorted, the output will print the elements in ascending order, which includes the repeated 10. After that, the for loop iterates through the multiset and prints each of its values.

Accessing Elements

In a multiset, we need to access elements by position using an iterator. For instance, if we want to get the 3rd element, we need to advance the begin iterator two positions by incrementing. We can also advance using the next or advance function in place of incrementing or decrementing.

C++ Example to Access Element in Multiset

Let us take an example to illustrate how to access an element in 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 example, we initialize a multiset<int> with values {40, 10, 30, 20, 10}. As multiset stores elements in sorted order and allows duplicates, the elements are automatically arranged. After that, a for loop with an iterator goes from the beginning to the end of the multiset, which prints each value using *it.

Finding Elements

In C++, multiset supports fast search by value operation through the find member function. The find function returns an iterator to the element if found; otherwise, it returns an end iterator.

Syntax

It has the following syntax:

iterator find(const value_type& val) const;

Here, we can easily access the first and last element by using begin and end iterators.

C++ Example to Find the Elements in Multiset

Let us take an example to illustrate how to find the elements in the 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 example, we generate a multiset containing some integers and attempt to locate the value 20 by using the find method. It prints a message stating the element has been found if it is found; otherwise, not found. Because multiset supports duplicates, the find function will return an iterator to one of the occurrences of the value.

Traversing Elements

In C++, traversing is similar to other containers, and multisets can be efficiently iterated by using a range-based for loop or by using the begin and end iterators. In order to iterate over all the elements of the same key, use the range given by the equal_range function in place of begin and end.

C++ Example to Traverse Elements

Let us take an example to demonstrate how to traverse 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 example, as multiset stores elements in sorted order, it automatically arranges them as {10, 20, 30, 40, 50}. After that, a for loop with an iterator goes from begin to end, dereferencing each iterator to access and print the values.

Removing Elements

If we want to remove elements from a multiset, we can use the erase function. It can be called either by providing the value or an iterator. However, if a value is provided, it removes all instances of that value.

C++ Example to Remove Elements

Let us take an example to illustrate how to remove 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 example, we produce a multiset of some integers with duplicates. It deletes one of the two 20s with find and erase(it) and all the 30s with erase(30). Lastly, it prints the remaining elements in ascending order.

Sort the Multiset in Descending Order

If we want to obtain the multiset elements in descending order, we can modify the following syntax as follows:

multiset<int, greater<int>> my_multiset ;

C++ Example to Sort the Multiset in Descending Order

Let us take an example to illustrate how to sort the multiset in descending order in 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 example, we create a multiset with a custom comparator greater<int>, which stores elements in descending order. It initializes the multiset with some values and prints them using a range-based loop. After that, the output will show the elements sorted from highest to lowest.

Swapping Multisets Using swap

In C++, exchanging two multiset containers enables us to swap their contents effectively. The swap function operates in constant time by exchanging inner pointers.

C++ Example to Swap Multisets using the Swap function

Let us take an example to illustrate how to swap 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 example, we initialize two multisets with different values, print both of them and then swap them with swap. When they are swapped, it prints them again to demonstrate that their contents have been swapped.

C++ Multiset empty and size Methods

In C++, we can utilize the capacity methods empty and size with multisets to check whether it is empty or not and its size.

The empty method returns 1 and 0 values.

• ✅ 1 (true) - if the multiset is empty
• ✅ 0 (false) - if the multiset is not empty

C++ Multiset Example using empty and size methods

Let us take an example to illustrate the multiset using empty and size functions in 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 example, we create a multiset with some repeating values, print its content, check and show whether it's empty and its size, and clear all elements with clear. After Post-clearing, it prints the multiset again and checks empty and size again to verify that it's empty now.

Member Functions

Below is the list of all member functions of multiset:

Constructor/Destructor

The given table shows several constructor/destructor functions that are used in C++ Multiset.

Iterators

The given table shows several iterator functions that are used in C++ Multiset.

Capacity

The given table shows several capacity functions that are used in C++ Multiset.

Modifiers

The given table shows several modifiers functions that are used in C++ Multiset.

Observers

The given table shows several modifiers functions that are used in C++ Multiset.

Operations

The given table shows several operations that are used in C++ Multiset.

Allocator

The given table shows several allocation functions that are used in C++ Multiset.

Non-Member Overloaded Functions

The given table shows several non-member overloaded functions that are used in C++ Multiset.

Conclusion

In conclusion, C++ STL has multisets. Multisets are sorted Set containers that store sorted values (the value is the key of type T). Unlike C++ sets, multisets can contain different redundant keys. Multiset allows us to compare the keys by default with the operator. The value of a multiset's items may be inserted or removed but not modified.

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

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