Multiset in C++: Definition and Usage with Examples

In this blog, we will go through:

° What is a multiset in C++?

° A multiset key properties

° Syntax and declaration

° Common operations with examples

° The multiset use cases

° Comparison with other STL containers

° Tips and best practices

° Learn more with professional courses from Uncodemy 

What is a Multiset in C++? 

The multiset is an associative container that is supplied by the C++ Standard Template Library (STL) that is designed to carry elements whose values are not unique. In other words, while a set is a collection of unique elements, a multiset is a collection of elements that can repeat.

The storage of multiset elements is sequentially arranged according to a sorting order, which in most cases is implemented with a balanced binary search tree (such as Red-Black Tree).

Key Characteristics:

• Colloquially, elements are stored in an order that is by default ascending.
• The repetition of elements is permitted.
• Good performance of operations: time complexity is logarithmic during insertion, deletion, and search.
• Associative container – each element is automatically repositioned according to its value.
•  

Syntax and Declaration

To use a multiset in C++, you need to include the <set> header.

#include <iostream>

#include <set>

using namespace std;

int main() {

    multiset<int> ms;

    return 0;

}

Declaration Variants:

multiset<int> ms;                        // ascending order

multiset<int, greater<int>> ms_desc;     // descending order

Basic Operations with Examples

Let’s explore how to use multiset operations effectively.

1. Insertion

#include <iostream>

#include <set>

using namespace std;

int main() {

    multiset<int> ms;

    ms.insert(10);

    ms.insert(20);

    ms.insert(10); // duplicate allowed

    ms.insert(30);

    for (auto x : ms) {

        cout << x << " ";

    }

    return 0;

}

Output:

10 10 20 30

Elements are sorted and duplicates preserved.

2. Size and Count

cout << "Size: " << ms.size();            // 4

cout << "\nCount of 10: " << ms.count(10); // 2

3. Erase Elements 

ms.erase(10); // removes all occurrences of 10

Or to remove only a single instance:

auto it = ms.find(10);

if (it != ms.end())

    ms.erase(it); // removes one instance of 10

4. Find an Element 

if (ms.find(20) != ms.end())

    cout << "20 is present";

5. Iterators and Traversal

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

    cout << *it << " ";

Or use a range-based loop:

for (int val : ms)

    cout << val << " ";

6. Lower Bound and Upper Bound 

auto low = ms.lower_bound(10); // first element ≥ 10

auto up = ms.upper_bound(10);  // 

first element > 10

 7. Clear and Empty 

ms.clear();         // removes all elements

ms.empty();         // checks if empty

Real-Life Use Cases 

Use Case 1: Frequency Management 

Imagine a voting scenario where you need to account for duplicate entries. Multisets allow you to not only keep track of the frequencies but also tally the counts in an ordered manner. 

multiset<string> votes = {"Alice", "Bob", "Alice", "Charlie"};

cout << "Alice got: " << votes.count("Alice") << " votes\n";

Use Case 2: Handling Events with Same Timestamps

Multisets can store multiple events occurring at the same time, automatically sorted.

multiset<pair<int, string>> events;

events.insert({10, "Alarm"});

events.insert({10, "Notification"});

Use Case 3: Sliding Window Maximums or Minimums

In competitive programming, multisets are often used in problems like sliding window maximum/minimum where duplicates exist.  

Multiset vs Set vs Vector

Best Practices When Using Multisets

•  Instead of looping manually to count duplicates, use count().
•  To avoid invalid iterators, use find() before erase().
•  For in-place construction of complex data types, use emplace() instead of insert().
•  Do not use operator[] – multisets do not support key-based access like maps do.
•  Be careful when you directly modify the elements – it may break the sorting.
•  

Practice Questions to Master Multiset  

1. Use the multiset to count the frequency of elements in the array.
2. Use the multiset to find the k-th smallest/largest element.
3. Delete only one instance of a repeated item.
4. Find the sliding window maximum when there are duplicates.
5. Keep a list of events sorted by timestamp, allowing for duplicates.

These sorts of problems are very popular at software engineering interviews of leading companies like Google, Amazon, and Microsoft.  

Learn STL and C++ with Uncodemy

If you want to master the C++ STL and become a top-notch professional, there is no better place than Uncodemy. They provide practical training and also have real-world projects that help you understand better.

Reasons to pick Uncodemy?

•  Certification by the industry
•  Trainers who have experience
•  Modules for C++ and DSA from start to finish
•  Sessions where you can code live, and solve doubts
• Help with interviews, resumes, etc.

 Check out Uncodemy's C++ course to advance your programming skills!

Conclusion

Multisets in C++ give you a nice balance of performance as well as flexibility when you are dealing with sorted data that may have duplicates. Be it your algorithm-heavy application, data science work, or interview practice, knowing the multiset inside out will help you do such tasks with confidence and high efficiency.

Remember:

° Use it when duplicates matter.

° Take advantage of sorted storage.

° Combine with other STL tools like map, vector, and priority_queue for complex problems.

Looking for A way to learn STL and c++ through live projects and guidance from experts? Why not enroll  in an Uncodemy c++ Programming course now !