Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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();
Question
Given a vector of type integer, is it possible to copy a range from vector to multiset ?
With this article at OpenGenus, you must have the complete idea of multiset container in C++. Enjoy.
