Multiset in C++ Standard Template Library (STL)

Last Updated : 02 Jan, 2023

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)
insert (x) – Inserts 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;
 
    // insert elements in random order
    gquiz1.insert(40);
    gquiz1.insert(30);
    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"
         << *gquiz1.lower_bound(40) << endl;
    cout << "gquiz1.upper_bound(40) : \n"
         << *gquiz1.upper_bound(40) << endl;
 
    // 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
a.erase(a.find()) – Remove only one instance of element from multiset having same value

The time complexities for doing various operations on Multisets are –

Insertion 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;
}

Output

3
2
0

Time Complexity: O(max(?(log(i)),(K+log(n))), where i is the size of multiset at the time of insertion, K is the total count of integers of the value passed, n is the size of multiset.
Auxiliary Space: O(1).

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 insert(const g)	Adds a new element ‘g’ to the multiset.
iterator insert (iterator position,const g)	Adds a new element ‘g’ at the position pointed by the 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.
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 after 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 insert 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()	Inserts 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.
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.
multiset::crend()	Returns a constant reverse iterator pointing to the position just before the first element in the container.
multiset::get_allocator()	Returns a copy of the allocator object associated with the multiset.

Recent Articles on Multiset

GeeksforGeeks

Improve

multiset begin() and end() function in C++ STL

Similar Reads

The C++ Standard Template Library (STL)

The Standard Template Library (STL) is a set of C++ template classes to provide common programming data structures and functions such as lists, stacks, arrays, etc. It is a library of container classes, algorithms, and iterators. It is a generalized library and so, its components are parameterized. Working knowledge of template classes is a prerequ

Sort in C++ Standard Template Library (STL)

Sorting is one of the most basic functions applied to data. It means arranging the data in a particular fashion, which can be increasing or decreasing. There is a builtin function in C++ STL by the name of sort(). This function internally uses IntroSort. In more details it is implemented using hybrid of QuickSort, HeapSort and InsertionSort.By defa

Set in C++ Standard Template Library (STL)

Sets are a type of associative container in which each element has to be unique because the value of the element identifies it. The values are stored in a specific sorted order i.e. either ascending or descending. The std::set class is the part of C++ Standard Template Library (STL) and it is defined inside the <set> header file. Syntax: std:

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

A C++ priority queue is a type of container adapter, specifically designed such that the first element of the queue is either the greatest or the smallest of all elements in the queue, and elements are in non-increasing or non-decreasing order (hence we can see that each element of the queue has a priority {fixed order}). In C++ STL, the top elemen

Containers in C++ STL (Standard Template Library)

A container is a holder object that stores a collection of other objects (its elements). They are implemented as class templates, which allows great flexibility in the types supported as elements. The container manages the storage space for its elements and provides member functions to access them, either directly or through iterators (reference ob

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

Binary search is a widely used searching algorithm that requires the array to be sorted before search is applied. The main idea behind this algorithm is to keep dividing the array in half (divide and conquer) until the element is found, or all the elements are exhausted.It works by comparing the middle item of the array with our target, if it match

Multimap in C++ Standard Template Library (STL)

Multimap is similar to a map with the addition that multiple elements can have the same keys. Also, it is NOT required that the key-value and mapped value pair have to be unique in this case. One important thing to note about multimap is that multimap keeps all the keys in sorted order always. These properties of multimap make it very much useful i

Map in C++ Standard Template Library (STL)

Maps are associative containers that store elements in a mapped fashion. Each element has a key value and a mapped value. No two mapped values can have the same key values. std::map is the class template for map containers and it is defined inside the <map> header file. Basic std::map Member FunctionsSome basic functions associated with std::

Queue in C++ Standard Template Library (STL)

Queues are a type of container adaptors that operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front. Queues use an encapsulated object of deque or list (sequential container class) as its underlying container, providing a specific set of member functions to access its eleme

Deque in C++ Standard Template Library (STL)

Double-ended queues are sequence containers with the feature of expansion and contraction on both ends. They are similar to vectors, but are more efficient in case of insertion and deletion of elements. Unlike vectors, contiguous storage allocation may not be guaranteed. Double Ended Queues are basically an implementation of the data structure doub

Article Tags :

Practice Tags :