MultiSet in C++ (STL)

Welcome to today’s deep dive into the multiset container within the C++ Standard Template Library (STL).

What is a MultiSet in C++?

In C++, the Standard Template Library (STL) offers a container called multiset. It’s similar to a set but allows for duplicate elements. This means a multiset can contain multiple instances of the same element. Like the set, a multiset stores its elements in sorted order, ascending by default. In a set, each element acts as a unique key. However, in contrast, the multiset container accommodates duplicate entries.

Difference between Set and MultiSet in C++

The primary distinction between set and multiset lies in their handling of duplicate elements. In a set, duplicate elements are not permitted. If you attempt to insert a duplicate into a set, it simply won’t be added. On the other hand, the multiset container embraces duplicate entries. Inserting a duplicate element into a multiset results in a new, distinct entry in the container.

Both Set and Multiset stores the elements in ascending order by default, although we can make it to store elements in descending order, with little customization.

Syntax of MultiSet in C++

To create a multiset object, you must first include the set header file. Like this,

#include <set>

The syntax for creating a multiset object requires specifying the data type as a template parameter. Like this,

std::multiset<data_type> obj;

This ensures that the multiset can only hold elements of that specific type i.e. data_type.

Creating & Initializing MultiSet in C++

For instance, one could create a multiset of integers, like this,

std::multiset<int> numbers;

or a multiset of strings, like this,

std::multiset<std::string> words;

Both the multiset objects created till now are empty, meaning it contains no elements. you can create a multiset and initialize it with hardcoded values using an initializer list. Like this,

std::multiset<int> numSet {11, 22, 33, 44, 33, 44, 33, 55};

It will instantiate a multiset of integers and initialize it with eight integer values. Since a multiset can accommodate duplicates and stores elements in ascending order by default, the content of the multiset created above will be:

11, 22, 33, 33, 33, 44, 44, 55.

Insert Elements in MultiSet

The multiset also provides an insert() function, which accepts a value and adds it to the multiset. For example,

#include <iostream>
#include <set>

int main()
{
    // Creating an empty multiset
    std::multiset<int> numSet;

    // Adding elements in multiset
    numSet.insert(4);
    numSet.insert(4);
    numSet.insert(2);

    return 0;
}

We inserting two duplicate values and a unique value into the multiset, all the values will be added, since it allows duplicate entries. Given its inherent nature, the multiset arranges its elements in a particular order, which is ascending by default. So, the elements in multiset will be stored like this,

2, 4, 4

Furthermore, we can iterate over all elements of a multiset using a range-based for loop and display each element on the console.

Iterate over all elements of MultiSet in C++

We can iterate over all the elements of a multiset using iterators. First, acquire an iterator pointing to the beginning of the multiset and continue incrementing it until it equals the iterator returned by the end() function of the multiset. During iteration, access each multiset element using the current iterator. Like this,

#include <iostream>
#include <set>

int main()
{
    std::multiset<int> numSet {11, 22, 33, 44, 33, 44, 33, 55, 66, 77, 88};

    // Iterate over all elements in MultiSet using iterators
    for(auto it = numSet.begin(); it != numSet.end(); it++)
    {
        std::cout<< *it << ", ";
    }
    std::cout<<std::endl;

    return 0;
}

Output:

11, 22, 33, 33, 33, 44, 44, 55, 66, 77, 88,

Additionally, with the introduction of the range-based for-loop in C++11, we can access each element individually within the for-loop, eliminating the need for explicit iterators. Like this, we can seamlessly traverse through every item in the multiset.

#include <iostream>
#include <set>

int main()
{
    std::multiset<int> numSet {11, 22, 33, 44, 33, 44, 33, 55, 66, 77, 88};

    // Iterate over all elements in MultiSet 
    // using Raneg Based for-loop
    for(const auto& elem : numSet)
    {
        std::cout<< elem<< ", ";
    }
    std::cout<<std::endl;

    return 0;
}

Output:

11, 22, 33, 33, 33, 44, 44, 55, 66, 77, 88,

Remove an element from MultiSet in C++

To remove an element from the multiset, we can use either a value or an iterator. To remove by value, we pass the desired value to the erase member function, which removes all occurrences of the given value. Like this,

#include <iostream>
#include <set>

int main()
{
    std::multiset<int> numSet {11, 22, 33, 44, 33, 44, 33, 55};

    // Remove all occurrences of value 44 in multiset
    numSet.erase(44);


    // Iterate over set and print elements
    for(const auto& elem : numSet)
    {
        std::cout<< elem<< ", ";
    }
    std::cout<<std::endl;

    return 0;
}

Output:

11, 22, 33, 33, 33, 55,

If we aim to remove an element based on an iterator, we pass the iterator to the erase() function, which then removes the element the iterator points to. For example, if we have a multiset of integers and want to remove the value 5, we can use the find() member function. This function searches for the specified value in the multiset and returns an iterator pointing to that value. If the value doesn’t exist in the multiset, it returns an iterator pointing to the end. After calling find(), we need to verify if the returned iterator is valid. If it’s valid, passing it to the erase() member function will remove that specific instance, not all occurrences of the value. For example, in the below example, we will remove the first occurrence of value 33 from the multiset in C++.

#include <iostream>
#include <set>

int main()
{
    std::multiset<int> numSet {11, 22, 33, 44, 33, 44, 33, 55};

    // Look for value 33 in multiset
    // Returns the first occurrence of element
    auto it = numSet.find(33);

    // Check if iterator is valid
    if(it != numSet.end())
    {
        // removes the element pointed by iterator
        numSet.erase(it);
    }

    // Iterate over set and print elements
    for(const auto& elem : numSet)
    {
        std::cout<< elem<< ", ";
    }
    std::cout<<std::endl;

    return 0;
}

Output:

11, 22, 33, 33, 44, 44, 55, 

Capacity related Operations on MultiSet in C++

The multiset in C++, provides several handy member functions such as size() and empty(). The size() function returns the number of elements in the multiset, while empty() returns true if the multiset has no elements. Similarly, the clear() member function removes all elements from the multiset.

For illustration, let’s consider an example where we create a multiset of integers, initializing it with five distinct integers. First, we’ll display the number of elements in the multiset using the size() function. Following that, we’ll verify whether the multiset is empty. Subsequently, we’ll utilize the clear() function to eliminate all elements from the multiset, and once more, confirm if the multiset is empty.

#include <iostream>
#include <set>

int main()
{
    // Creating an empty multiset
    std::multiset<int> numSet {22, 55, 11, 33, 44};

    size_t num = numSet.size();

    std::cout<< "Number of elements in Multiset are: " << num <<std::endl;

    if(numSet.empty())
    {
        std::cout << "Multiset is Empty \n";
    }
    else
    {
        std::cout << "Multiset is not Empty \n";
    }

    // Remove all eements from MultiSet
    numSet.clear();

    num = numSet.size();

    std::cout<< "Number of elements in Multiset are: " << num <<std::endl;

    if(numSet.empty())
    {
        std::cout << "Multiset is Empty \n";
    }
    else
    {
        std::cout << "Multiset is not Empty \n";
    }

    return 0;
}

Output:

Number of elements in Multiset are: 5
Multiset is not Empty 
Number of elements in Multiset are: 0
Multiset is Empty 

Finding Elements in Multiset in C++

The multiset provides a find() function. This function takes a value as its argument and returns an iterator that points to the first occurrence of that value within the multiset. If the value isn’t present in the multiset, the function returns an iterator that points to the end of the multiset.

TLet’s consider the following example where we search for the value 33 in the multiset.

#include <iostream>
#include <set>

int main()
{
    std::multiset<int> numSet {11, 22, 33, 44, 33, 44, 33, 55};

    // Look for value 33 in multiset
    std::multiset<int>::iterator it = numSet.find(33);

    // Check if iterator is valid
    if(it != numSet.end())
    {
        std::cout<< "Element: " << *it << std::endl;
    }

    return 0;
}

Output:

Element: 33

Counting Occurrences of Element in Multiset in C++

The multiset also offers a count() function. This function takes a value as its argument and returns the number of occurrences of that particular value within the multiset. Given that a multiset can store duplicate values, the count() function will indicate the number of times a particular value appears. If the value isn’t found in the multiset, the function will return zero.

Suppose you have a multiset initialized with a few values. Here’s how you can use the count() function to find out how many times the value 33 appears in the multiset:

#include <iostream>
#include <set>

int main()
{
    std::multiset<int> numSet{11, 22, 33, 44, 33, 44, 33, 55, 66, 77, 88};

    std::size_t num = numSet.count(33);

    std::cout<< "Count of value 33 is: " << num << std::endl;

    return 0;
}

Output:

Count of value 33 is: 3

Using MultiSet with Custom Comparators

In C++, multiset uses the less-than operator as the default comparator to sort its elements. Therefore, all the elements in the multiset will be stored in ascending order by default. If you want to store elements in descending order, you can provide a custom comparator. For example, you can use the std::greater<int>() function as the comparator. Let’s examine this:

#include <iostream>
#include <set>
#include <functional>

int main()
{
    std::multiset<int, std::greater<int>> setObj = {1, 2, 2, 3, 4, 5, 5, 5};

    for (int num : setObj)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

5 5 5 4 3 2 2 1 

Here, we have created a multiset of integers with std::greater as the comparator. After inserting 10 integers into the multiset, they will be internally stored in descending order. We can verify this by printing all the contents of the multiset.

Instead of using the default std::greater<>() function, you can also use a function object as a comparator.

In this example, we’ll declare a function object and provide an overloaded function that accepts two integers as arguments and compares them using the greater-than operator. We can then use this function object when declaring a multiset as a comparator. As a result, this multiset object will store elements in descending order. Let’s see an example where we create a multiset of integers and use this custom comparator.

#include <iostream>
#include <set>

class CustomComparator {
public:
    bool operator()(const int &a, const int &b) const {
        return a > b;
    }
};

int main() {
    std::multiset<int, CustomComparator> setObj = {1, 2, 2, 3, 4, 5, 5, 5};

    for (int num : setObj) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

5 5 5 4 3 2 2 1 

Additionally, a lambda function can be used as a custom comparator. In the following example, we’ll create a multiset and utilize a lambda function that accepts two integers as arguments and compares them using the greater-than operator. Thus, this multiset will store its integers in descending order.

#include <iostream>
#include <set>

int main()
{
    // Lambda function
    auto comp = [](int a, int b) { 
                        return a > b;
                };

    // Multiset object with lambda function as custom comparator
    std::multiset<int, decltype(comp)> multiSet3(comp);

    multiSet3.insert({1, 2, 2, 3, 4, 5, 5, 5});

    for (int num : multiSet3)
    {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

5 5 5 4 3 2 2 1 

Summary

multiset is a powerful tool in the C++ Standard Template Library (STL) designed for storing duplicate elements while maintaining them in a specific order, either ascending or descending. It facilitates quick searching, deletion, and insertion. Essentially, most operations have logarithmic complexity.

The fundamental distinction between set and multiset is that the latter can store duplicate elements, while the former only accommodates unique elements. The default order of elements in multiset, similar to set, is ascending. However, this behavior can be customized by providing a custom comparator.