Basics of std::multiset in C++

std::multiset is associative type of STL container. It comes under set header. These header contains two types of class templates:

a) set - store unique elements only.
b) multiset - accept duplicate elements also.

We have explored the basics of multiset container in C++ in depth. We have covered initialize, accessing elements, member functions, modifiers like emplace, its iterators, observers and much more.

Features :

a) Upon insertion of elements, they always follows strict weak ordering.strict weak ordering is a binary predicate that compares two objects and returns true if first precedes the second.
b) Inserted values cannot be modified.
c) Inserted values can be removed.

In order to get understanding of features of multiset, first get started with initializing, insert and accessing the values. It is just a small introduction, after getting your multiset ready you can perform other operations explained in later post.

1. Initalize

multiset<int> mset;
mset.insert(0);
mset.insert(-1);
mset.insert(-2);

or we can just copy values from existing array or vector.

vector<int> myvector(3);
for(int i=0; i< 3; i++){
    myvector[i] i+1;
} // myvector contains 1,2,3

int myarray[] = {4,5,6}; // 4,5,6
int sizeMyarray = sizeof(myarray)/sizeof(myarray[0]);

Now adding vector and array content to multiset using range constructor.

mset.insert(myvector.begin(), myvector.end());
// now set contains -2,-1,0,1,2,3
mset.insert(myarray, myarray+sizeMyarray);
// now set contains -2,-1,0,1,2,3,4,5,6

2. accessing values

To acces the values from multiset, we can use find method, or iterate through content.
For example,

// Using find operation
    multiset<int>::iterator it = mset.find(6);
    if(it!=it.end()){
        cout<<*it;
    }else{
        cout<<"Not Found";
    }
    
 // Using iterators
 for(auto a: mset){
     cout<<a<<" ";
 }
 cout<<'\n';
 
 multiset<int>::iterator it = mset.begin();
 for(; it!=mset.end(); it++)
 {
     cout<<*it<<" ";
 }

Based of conditions to look for element, there are many implicit methods.
For example, if you want to find largest element then you can access iterator to end element and to get smaller element you can access to iterator at beginning.
Similary for getting a next greater number, we can use upper_bound() method. The description of methods are explained below along with example code.

Member Functions :

1. multiset::multiset

Constructor for multiset.
We can define:
a. Empty constructor - empty object is created.
e.g. multiset<int> myset
b. Range constructor - object with values copied from range/pointers of array.
e.g. multiset<int> myset(iterator1, iterator2), secondset(array, array+arr_size)

2. multiset::~multiset

Destroys the container object.

 #include<iostream>
 #include<set>

 int main ()
 { 
   int myints[]= {20,10,30,20,20};
   std::multiset<int> second (myints,myints+5);
   std::multiset<int> third(second.begin(), second.end());
   for(auto a: second) std::cout<<a<<" ";
   std::cout<<'\n';
   for(auto b: third) std::cout<<b<<" ";
   return 0;
 }

Output

10 20 20 20 30 
10 20 20 20 30 

3. multiset::get_allocator

Allocator handles dynamic memory request. When user program create an object of some class, allocator is responsible for allocating space. Here get_allocator() method returns the allocator associated with multiset. Allocator object then can be used to allocate some 'n' blocks of memory.
e.g. allocator(n)

In the below example, p is assigned the 5 blocks of memory using allocator provided by multiset.

      #include <iostream>
      #include <set>

      using namespace std;
      int main()
      {
          char *p;
          multiset<char> all;

          p = all.get_allocator().allocate(5);

          char c = 'a';
          for(int i=0; i< 5; i++) p[i]=c++;
          
          while(*p){
              cout<<*(p++)<<" ";
          }
          cout<<'\n';
          
          return 0;
      }

output

a b c d e

4. multiset::operator=

Copy content of one to another set.

    #include<iostream>
    #include<set>
    
    using namespace std;
    int main(){
        char *p;
        multiset<char> all = {'a', 'b', 'c'};
        multiset<char> copied = all;
        for(auto a: copied){
         cout<<a<<" ";
        }
     }

output

a b c

Modifiers :

1. multiset::emplace

The method is similar to multiset::insert.Only difference is insert moves/copy data to its container where as emplace treat data as arguments and construct internally in the container.

        #include <iostream>
        #include <set>
        using namespace std;
        int main() {
            multiset<int> all = {1,4,7,5,0};
            cout<<"insert: 3\n";
            multiset<int>::iterator it =
            all.emplace(3);
            cout<<"return pointer to: "<<*it<<endl;
            for(auto x: all) cout<<x<<" ";
            return 0;
        }

2. multiset::emplace_hint

Same as multiset::emplace method.Additional parameter is
provided to help in indicating position in multiset to begin
serach for insertion operation.

#include <iostream>
#include <set>
using namespace std;
int main() {
    multiset<int> all = {1,3,4,5,3,9,8,45,67,89};
    multiset<int>::iterator it = all.cbegin();
    cout<<"emplace 10, search begin from starting 
    location of set\n";
    all.emplace_hint(it, 10);
    it = all.cend();
    cout<<"emplace 87, search begin from 
         ending location of set\n";
         all.emplace_hint(it, 87);
    for(auto x: all) cout<<x<<" ";
    return 0;
 }

output

emplace 10, search begin from starting location of set
emplace 87, search begin from ending location of set
        1 3 3 4 5 8 9 10 45 67 87 89

3. multiset::insert

a) iterator insert(data)
b) iterator insert(position, data) - insert data, position only helps in improving insertion by allowing multiset to start seraching from it for favorable position to insert(same as multiset::emplace_hint).
c)void insert(iterator &a, iterator &b)- Copy data between range given by pointers.

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

int main() {

  vector<int> collection;
  cout<<"vector elements: ";
  for(int i=0; i< 5; i++){
      collection.push_back(i+10);
      cout<<(i+10)<<' ';
  }

  multiset<int>::iterator it;
  multiset<int> all;

  all.insert(collection.begin(), collection.end());
  all.insert(9);
  all.insert(99);
  it = all.insert(999);
  it = all.insert(it, 0);

  cout<<"\nmultiset elements: ";
  for(auto x: all) cout<<x<<" ";

  return 0;
}

output

vector elements: 10 11 12 13 14 
multiset elements: 0 9 10 11 12 13 14 99 999

4. multiset::erase

The erase method remove elements by value, pointed by a iterator or range of iterators.
for example,
erase by value, mset.erase(1) will remove value 1.
erase by iterator it, mset.erase(it) will remove by iterator it
erase by range it1, it2, mset.erase() will remove elements in range it1 and it2

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

void print(string msg, multiset<int>& all){

 cout<<msg<<": ";
 for(auto x: all) cout<<x<<" ";
 cout<<'\n';
}
int main() {

 multiset<int> all = {1,1,3,4,5,5,5,8,10,10};

 print("content", all);
 // erase by value
 all.erase(1);
 print("Erase by value", all);

 // erase by pointer/iterator
 multiset<int>::iterator it = all.begin();
 it++;
 all.erase(it);
 print("Erase by pointer", all);

 it = all.begin();
 all.erase(++it, all.end());
 print("Erase by range", all);

 return 0;
}

Output

content: 1 1 3 4 5 5 5 8 10 10 
Erase by value: 3 4 5 5 5 8 10 10 
Erase by pointer: 3 5 5 5 8 10 10 
Erase by range: 3 

5. multiset::swap

Swap contents of two multiset.

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

void print(string msg, multiset<int>& all){

    cout<<msg<<": ";
    for(auto x: all) cout<<x<<" ";
    cout<<'\n';
}
int main() {

    multiset<int> first = {1,1,3,4,5,5,5,8,10,10};
    multiset<int> second = {100, 1000, 10000};

    cout<<"Before swap \n";
    print("first: ", first);
    print("second: ", second);

    first.swap(second);
    cout<<"After swap \n";
    print("first: ", first);
    print("second: ", second);
    return 0;
}

output

Before swap 
first: : 1 1 3 4 5 5 5 8 10 10 
second: : 100 1000 10000 
After swap 
first: : 100 1000 10000 
second: : 1 1 3 4 5 5 5 8 10 10 

In the above code, as you can see contents are swaped between first and second multiset.

6. multiset::clear

Removes all the elements.

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

    multiset<int> first = {1,1,3,4,5,5,5,8,10,10};
    cout<<"Before: "<<first.size()<<endl;
    first.clear();
    cout<<"After: "<<first.size();
    return 0;
}

Output

Before: 10
After: 0

In the above code, as you can see size of multiset before and after.
clear() function has completely emptied the multiset.

Iterators :

1. multiset::begin and multiset::end

2. multiset::rbegin and multiset::rend

3. multiset::crbegin and multiset::crend

• begin(), cbegin() gives pointer to first element.
• end(), cend() gives pointer to last elment in the set.
• rbegin(), crbegin() gives pointer to last element, and can be increment to visit other elements from end.
• rend(), crend() gives pointer to first element.
• All the iterators are constant type in multiset as it is not allowed to change elements once inserted.

#include <bits/stdc++.h>
using namespace std;

int main(){

  multiset<int> all = {1,5,4,3};

  multiset<int>::iterator it = all.begin();

  cout<<"using begin(), end() "<<endl;
  for(; it!=all.end(); it++){
    cout<<*it<<" ";
  }
  cout<<'\n';

  cout<<"using rbegin(), rend() "<<endl;
  multiset<int>::reverse_iterator itr = all.rbegin();
  for(; itr!=all.rend(); itr++){
    cout<<*itr<<" ";
  }
  cout<<'\n';

  cout<<"using cbegin(), cend() "<<endl;
  it = all.cbegin();
  for(; it!=all.cend(); it++){
    cout<<*it<<" ";
  }
  cout<<'\n';

  //
  cout<<"using crbegin(), crend() "<<endl;
  itr = all.crbegin();
  for(; itr!=all.crend(); itr++){
    cout<<*itr<<" ";
  }
  cout<<'\n';

  return 0;
}

Output

using begin(), end() 
1 3 4 5 
using rbegin(), rend() 
5 4 3 1 
using cbegin(), cend() 
1 3 4 5 
using crbegin(), crend() 
5 4 3 1 

Capacity :

1. multiset::count

count(x)- Returns integer value, count number of elements in container equivalent to x.

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

int main() {
  multiset<int> first = {1,1,3,4,5,5,5,8,10,10};
  cout<<"Count of 5: "<<first.count(5)<<endl;
  return 0;
}

Output

Count of 5: 3

2. multiset::empty

empty() - Checks whether container is empty. Returns true if empty, otherwise false.

3. multiset::size

size() - Returns integer variable, representing size of set.

#include <iostream>
#include <set>
using namespace std;
int main() {
      multiset<int> first = {1,1,3,4,5,5,5,8,10,10};
      cout<<"Before: "<<first.size()<<endl;
      first.clear();
      cout<<"After: "<<first.size();
      return 0;
}

Output

Before: 10
After: 0

4. multiset::max_size

max_size() - Returns integer value, represent possible maximum size of multiset.

#include <iostream>
#include <set>
using namespace std;
int main() {
 multiset<int> first = {1,1,3,4,5,5,5,8,10,10};
 cout<<"max_size :"<<first.max_size()<<endl;
 return 0;
}

Output

max_size :461168601842738790

Lookup :

1. multiset::lower_bound

lower_bound(x), returns iterator representing lower bound of x.
If a multiset contains, elements 1,2,0,4, and if we try to find lower bound of multiset.

We will consider two cases

Finding lower bound of present and absent element :

a)

3 is not preset in the multiset. Let's find its lower bound.

multiset<int>::iterator it = myset.lower_bound(3);
cout<<"Lower Bound of 3 is: "<<*it<<endl;

These will output 4.

b)

2 is present, let's find it's lower bound;

multiset<int>::iterator it = myset.lower_bound(2);
cout<<"Lower Bound of 2 is: "<<*it<<endl;

These will output 3.

So, lower bound identifies value either equal if present or the higher corresponding value if present.

2. multiset::upper_bound

upper_bound(x), return iteartor representing upper bound of x.
Lets consider, few elements : 0,1,3,4.

Finding upper bound of present and absent element

For both of the cases, upper bound will always return next greater element.

multiset<int>::iterator it = myset.upper_bound(2);
cout<<"Upper Bound of 2 is: "<<*it<<endl;
it = myset.upper_bound(3);
cout<<"Upper Bound of 3 is: "<<*it<<endl;

These will output :

Upper Bound of 2 is: 3
Upper Bound of 3 is: 4

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

void print(string msg, multiset<int>& all){
   cout<<msg<<": ";
   for(auto x: all) cout<<x<<" ";
   cout<<'\n';
}
int main() {
    multiset<int> first = {1,1,3,4,5,5,5,8,10,10};
    multiset<int>::iterator it1, it2;

            print("set", first);
            cout<<"if use greater element not in set (1100): \n";
            it1 = 
            first.lower_bound(1100); // gives max element of set
            it2 = first.upper_bound(1100);
            cout<<"lower_bound: "<<*it1<<"\nupper_bound: 
               "<<*it2<<endl;

            cout<<"\nif use smallest element not in set (0):\n";
            it1 = 
            first.lower_bound(0); // gives min element of set
            it2 = first.upper_bound(0);
            cout<<"lower_bound: "<<
            *it1<<"\nupper_bound: "<<*it2<<endl;

            cout<<"\nlower bound of 4:\n";
            it1 = first.lower_bound(4);
            cout<<*it1<<endl;

            cout<<"\nupper bound of 4:\n";
            it2 = first.upper_bound(4);
            cout<<*it2<<endl;

            return 0;
        }

Output

set: 1 1 3 4 5 5 5 8 10 10 
if use greater element not in set (1100): 
lower_bound: 10
upper_bound: 10

if use smallest element not in set (0):
lower_bound: 1
upper_bound: 1

lower bound of 4:
4

upper bound of 4:
5

3. multiset::find

iterator find(x) - Returns iterator to the element x.
Consider, a multiset conatining values: 1,5,3,6.
We will query for present element(5) and absent element(90).

int myarray[] = {1,5,3,6};
multiset<int> mset(myarray, myarray+(sizeof(myarray)/ sizeof(myarray[0]));
multiset<int>::iterator it;

As you can see from above code, an iterator on multiset has been created. If element is found in the multiset then the multiset will return iterator to the correspoding element, by derefrencing we can get its value.

it = mset.find(5);
if(it != mset.end()){
    cout<<"Found: "<<*it;
}else{
    cout<<"Not found\n";
}

In the above case it will return, pointer to iterator.
Output contains Found: 5.
Otherwise if return iterator is past to end element, then Not found
will be in the output.

4. multiset::equal_range

pair<iterator, iterator> equal_range(x) - Returns pair of iterator, representing bound of equal value elements x.

 #include <iostream>
 #include <set>
 using namespace std;           
 typedef multiset<int>::iterator It;
 int main() {
     multiset<int> first = {1,1,3,4,5,5,5,8,10,10};
     multiset<int>::iterator it1, it2;
     pair<It, It> pair = first.equal_range(5);
     for(it1 = pair.first; it1!=pair.second; it1++){
                    cout<<*it1<<" ";
     }

  return 0;
 }

output

5 5 5

In the above example, It type is defined to use it in pair<It, It> as equal_range(x) will return a pair of iterators.

Observers :

1. multiset::value_comp

2. multiset::key_comp

Both the methods, returns the comparision object for multiset. Comparision object uses value as a key to sort the elements.
They can be invoke as for example:

multiset<int> mset;
multiset<int>::value_compare val_comp = mset.value_comp();
multiset<int>::key_compare key_comp = mset.key_comp();

With this article at OpenGenus, you must have the complete idea of multiset container in C++. Enjoy.