Anatomy of std::multiset

In C++, a std::multiset is an associative container that allows storage of multiple elements with the same value. It is defined in the <set> header. Unlike a std::set, which stores unique elements only, a std::multiset can store multiple instances of the same value.

C++ multisets are STL containers that store elements of the same type in sorted order, where multiple elements can have equivalent values. In other words, duplicate values are allowed.

The value of each element acts as its own key.

Properties

1. Associative: Elements are referenced by their key and not by their absolute position in the container.
2. Sorted: Elements are stored in a sorted manner.
3. Equivalent keys: Multiple elements in the container can have equivalent keys.
4. Immutable: The value of elements can't be modified after they have been stored in the multiset.

Declaration and Initialization

To use std::multiset, include the necessary header and declare it with the desired data type:

#include <set>

std::multiset<data_type> multiset_name = {key1, key2, key3, ...};

Here,

• std::multiset - declares an STL container of type multiset.
• data_type - the data type of the values to be stored in the multiset.
• multiset_name - a unique name given to the multiset.
• key1, key2, key3, … - key/value to be stored in the multiset.

For example,

// initialize multiset with elements
std::multiset<int> myMultiset = {1, 2, 5, 4, 3};

// create an empty multiset
std::multiset<int> myMultiset2;

Complete Example:

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

int main() {

    multiset<int> my_multiset = {5, 3, 8, 1, 3};
    
    for(int val : my_multiset) {
        cout << val << " ";
    }
    
    return 0;
}

// Output
1 3 3 5 8

Here, we create a multiset of type int.

The multiset returned the values in a sorted manner and included the duplicate instances of 3.

Sort the multiset in descending order:

To get the elements of the multiset in descending order, we can modify our syntax as:

std::multiset<int, greater<int>> myMultiset;

For example:

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

int main() {

    multiset<int, greater<int>> my_multiset = {5, 3, 8, 1, 3};
    
    for(int val : my_multiset) {
        cout << val << " ";
    }
    
    return 0;
}

// Output
8 5 3 3 1

The multiset now returns the elements in descending order.

Functions

1. Modifiers Functions:

insert():

• Inserts elements into the multiset.
• Can insert a single element, a range of elements, or elements from another container.

myMultiset.insert(7); // insert a single element

erase():

• Removes elements from the multiset.
• Can erase a specific element or a range of elements.

myMultiset.erase(5); // removes all occurrences of 5

clear():

• Removes all elements from the multiset.

myMultiset.clear();

2. Capacity Functions:

empty():

• Returns true if the multiset is empty; otherwise, return false. (1 true, 0 false)

if (!myMultiset.empty()) {
    // multiset is not empty
}

size():

• Returns the maximum number of elements in the multiset.

int size = myMultiset.size();

max_size():

• Returns the maximum number of elements that the multiset can hold.

auto max = myMultiset.max_size();

Complete Example:

#include <iostream>     
#include <set>          
using namespace std;
   
int main () {

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

    // print multiset before clearing all values
    cout << "The multiset before clear: ";
    for (int i : my_multiset) {
        cout << i << "  ";
    }
    
    // check if the multiset is empty
    cout << "\nEmpty: " << my_multiset.empty() << endl;

    // check the size of the multiset
    cout << "Size: " << my_multiset.size() << endl;
    
    // delete all values from the multiset
    my_multiset.clear();
    
    // multiset after clear
    cout << "\nThe multiset after clear: ";
    for (int i : my_multiset) {
        cout << i << "  ";
    }
    
    // use the capacity methods again
    cout << "\nEmpty: " << my_multiset.empty() << endl;
    cout << "Size: " << my_multiset.size() << endl;

    return 0;
}

// Output
The multiset before clear: 10  20  20  20  30  40  
Empty: 0
Size: 6

The multiset after clear: 
Empty: 1
Size: 0

3. Lookup:

count():

• Returns the number of elements with a specific value.

int countOfFive = myMultiset.count(5);

find():

• Returns an iterator to the first element equal to a specified value, or end() if not found.

auto found = myMultiset.find(4);
if (found != myMultiset.end()) {
    // element found
}