Read Discuss Practice Video Courses

Multiset in C++ Standard Template Library

(STL)
Difficulty Level : Easy ● Last Updated : 24 Jul, 2022

Multisets are a type of associative containers similar to the set, with the

exception that multiple elements can have the same values. Some Basic

Functions associated with multiset :

begin() – Returns an iterator to the first element in the multiset –> O(1)

end() – Returns an iterator to the theoretical element that follows the last

element in the multiset –> O(1)

size() – Returns the number of elements in the multiset –> O(1)

max_size() – Returns the maximum number of elements that the multiset can

hold –> O(1)

empty() – Returns whether the multiset is empty –> O(1)

inser t (x) – Inser ts the element x in the multiset –> O(log n)

clear () – Removes all the elements from the multiset –> O(n)

erase(x) – Removes all the occurrences of x –> O(log n)

Implementation:

CPP

// CPP Program to demonstrate the

// implementation of multiset
#include <iostream>
#include <iterator>
#include <set>

using namespace std;

int main()
{
// empty multiset container
multiset<int, greater<int> > gquiz1; ▲
Start Your elements
// insert CodinginJourney Now!
random order Login Register
gquiz1.insert(40);
Read Discuss Practice
gquiz1.insert(30); Video Courses
gquiz1.insert(60);
gquiz1.insert(20);
gquiz1.insert(50);

// 50 will be added again to

// the multiset unlike set
gquiz1.insert(50);
gquiz1.insert(10);

// printing multiset gquiz1

multiset<int, greater<int> >::iterator itr;
cout << "\nThe multiset gquiz1 is : \n";
for (itr = gquiz1.begin(); itr != gquiz1.end(); ++itr) {
cout << *itr << " ";
}
cout << endl;

// assigning the elements from gquiz1 to gquiz2

multiset<int> gquiz2(gquiz1.begin(), gquiz1.end());

// print all elements of the multiset gquiz2

cout << "\nThe multiset gquiz2 \n"
"after assign from gquiz1 is : \n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << *itr << " ";
}
cout << endl;

// remove all elements up to element

// with value 30 in gquiz2
cout << "\ngquiz2 after removal \n"
"of elements less than 30 : \n";
gquiz2.erase(gquiz2.begin(), gquiz2.find(30));
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << *itr << " ";
}

// remove all elements with value 50 in gquiz2

int num;
num = gquiz2.erase(50);
cout << "\ngquiz2.erase(50) : \n";
cout << num << " removed \n";
for (itr = gquiz2.begin(); itr != gquiz2.end(); ++itr) {
cout << *itr << " ";
}

cout << endl;

// lower bound and upper bound for multiset gquiz1

 cout << "\ngquiz1.lower_bound(40) : \n"
Start Your Coding Journey Now!
<< *gquiz1.lower_bound(40) << endl;
cout << "gquiz1.upper_bound(40) : \n"
Read << Discuss Practice Video<< endl;
*gquiz1.upper_bound(40) Courses

// lower bound and upper bound for multiset gquiz2

cout << "gquiz2.lower_bound(40) : \n"
<< *gquiz2.lower_bound(40) << endl;
cout << "gquiz2.upper_bound(40) : \n"
<< *gquiz2.upper_bound(40) << endl;

return 0;
}

Output

The multiset gquiz1 is :

60 50 50 40 30 20 10

The multiset gquiz2

after assign from gquiz1 is :
10 20 30 40 50 50 60

gquiz2 after removal

of elements less than 30 :
30 40 50 50 60
gquiz2.erase(50) :
2 removed
30 40 60

gquiz1.lower_bound(40) :
40
gquiz1.upper_bound(40) :
30
gquiz2.lower_bound(40) :
40
gquiz2.upper_bound(40) :
60

Removing Element From Multiset Which Have Same Value :

a.erase() – Remove all instances of element from multiset having the same

value
Start Your Coding Journey Now!
a.erase(a.find()) – Remove only one instance of element from multiset having

same value

Read Discuss Practice Video Courses

The time complexities for doing various operations on Multisets are –

Inser tion of Elements- O(log N)

Accessing Elements – O(log N)

Deleting Elements- O(log N)

C++

// CPP Code to remove an element from multiset which have

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

int main()
{
multiset<int> a;
a.insert(10);
a.insert(10);
a.insert(10);

// it will give output 3

cout << a.count(10) << endl;

// removing single instance from multiset

// it will remove only one value of

// 10 from multiset
a.erase(a.find(10));

// it will give output 2

cout << a.count(10) << endl;

// removing all instance of element from multiset

// it will remove all instance of value 10
a.erase(10);

// it will give output 0 because all

// instance of value is removed from
// multiset
cout << a.count(10) << endl;

return 0;
}
Start Your Coding Journey Now!
Output

3
Read Discuss Practice Video Courses
2
0

List of Functions of Multiset

Function Definition

begin() Returns an iterator to the first element in the multiset.

end() Returns an iterator to the theoretical element that

follows the last element in the multiset.

size() Returns the number of elements in the multiset.

max_size() Returns the maximum number of elements that the

multiset can hold.

empty() Returns whether the multiset is empty.

pair inser t(const g) Adds a new element ‘g’ to the multiset.

iterator inser t (iterator Adds a new element ‘g’ at the position pointed by the

position,const g) iterator.

erase(iterator position) Removes the element at the position pointed by the

iterator.

erase(const g) Removes the value ‘g’ from the multiset.

clear() Removes all the elements from the multiset.

key_comp() / value_comp() Returns the object that determines how the elements

in the multiset are ordered ( ‘<‘ by default).

find(const g) Returns an iterator to the element ‘g’ in the multiset if

found, else returns the iterator to end.

Start Your Coding Journey Now!
Function Definition

Read Discuss Practice Video Courses

count(const g) Returns the number of matches to element ‘g’ in the

multiset.

lower_bound(const g) Returns an iterator to the first element that is

equivalent to ‘g’ or definitely will not go before the

element ‘g’ in the multiset if found, else returns the

iterator to end.

upper_bound(const g) Returns an iterator to the first element that will go af ter

the element ‘g’ in the multiset.

multiset::swap() This function is used to exchange the contents of two

multisets but the sets must be of the same type,

although sizes may differ.

multiset::operator= This operator is used to assign new contents to the

container by replacing the existing contents.

multiset::emplace() This function is used to inser t a new element into the

multiset container.

multiset equal_range() Returns an iterator of pairs. The pair refers to the range

that includes all the elements in the container which

have a key equivalent to k.

multiset::emplace_hint() Inser ts a new element in the multiset.

multiset::rbegin() Returns a reverse iterator pointing to the last element

in the multiset container.

multiset::rend() Returns a reverse iterator pointing to the theoretical

element right before the first element in the multiset

container.

multiset::cbegin() Returns a constant iterator pointing to the first element

in the container.
 Start Your Coding Journey Now!
Function Definition

Read Discuss Practice Video Courses

multiset::cend() Returns a constant iterator pointing to the position past

the last element in the container.

multiset::crbegin() Returns a constant reverse iterator pointing to the last

element in the container.

DSA Data Structures

multiset::crend()
Algorithms Interview Preparation Data Science Topic-wise Practice
Returns a constant reverse iterator pointing to the
C++ Ja
position just before the first element in the container.

multiset::get_allocator() Returns a copy of the allocator object associated with

the multiset.

Recent Ar ticles on Multiset

C++ Programming Language Tutorial | Multiset in …

Please write comments if you find anything incorrect, or you want to share more

information about the topic discussed above.

Like 90

Previous Next
Unordered Sets in C++ Standard Map in C++ Standard Template
Start Your Coding Journey Now!
Template Library Library (STL)
Read Discuss Practice Video Courses

Related Articles

1. Multimap in C++ Standard Template Library (STL)

2. List in C++ Standard Template Library (STL)

3. Queue in C++ Standard Template Library (STL)

4. Sort in C++ Standard Template Library (STL)

5. Deque in C++ Standard Template Library (STL)

6. Priority Queue in C++ Standard Template Library (STL)

7. The C++ Standard Template Library (STL)

8. Map in C++ Standard Template Library (STL)

9. Set in C++ Standard Template Library (STL)

10. Binary Search in C++ Standard Template Library (STL)

Ar ticle Contributed By :

GeeksforGeeks

Vote for difficulty

Current difficulty : Easy

Start
Easy Your Coding
Normal Journey
Medium Hard Now!
Expert

Read Discuss Practice Video Courses

Improved By : samridhzor23, striver02, gabaa406, anshikajain26,

utkarshgupta110092, divyanshmishra101010, sweetyty,
nirajjadhav5596
Article Tags : cpp-containers-library, cpp-multiset, STL, C++
Practice Tags : CPP, STL

Improve Article Report Issue

A-143, 9th Floor, Sovereign Corporate Tower,

Sector-136, Noida, Uttar Pradesh - 201305

[email protected]

Company Learn
About Us DSA
Careers Algorithms
In Media Data Structures
Contact Us SDE Cheat Sheet
Privacy Policy Machine learning
Copyright Policy CS Subjects
Advertise with us Video Tutorials
Courses

News Languages
Top News
Python
Technology
Java
Work & Career
CPP
Business
Golang
 Finance C#
Start Your Coding
Lifestyle Journey Now! SQL
Read Discuss Practice
Knowledge Video Courses Kotlin

Web Development Contribute

Web Tutorials Write an Article
Django Tutorial Improve an Article
HTML Pick Topics to Write
JavaScript Write Interview Experience
Bootstrap Internships
ReactJS Video Internship
NodeJS

@geeksforgeeks , Some rights reserved