Multiset in C++
Introduction
Multisets are part of the C++ STL, or Standard Template Library. In C++, a multiset is a set of associative containers that hold ordered items. Items in a multiset can be added or withdrawn, but their values cannot be altered (The items are also known as the values and are always constant).
What is a Set?
A set is a type of data structure that is used in C++ programming to hold the unique values of lists and to automatically order their elements. Ascending order is the default when ordering something.
We use the insert() function to insert the components. The set will only store one instance of an element, and if the same value is inserted more than once, duplicates will be promptly deleted.
Using the erase() method, the Set's components are removed.
The method erase(s.begin(),s.find(x)) removes every element in the set, starting at the beginning and ending with x.
What is Multiset in C++:
In the C++ programming language, a multiset is a container that stores elements in a predetermined sequence and permits many elements to share the same value.
An element's value in a multiset also serves as a means of identification (the value is the key of type T).
If there are more than two items or a large number of components with similar values, you can store them in a multiset in a specific order.
Once added to the multiset, these values cannot be modified; they serve to identify the items with their respective key value and pair value. More elements can be added and removed at any moment. Thus, one condition can be satisfied.
Due to multisets' support for insertion and deletion operations, the storage requirements are dynamically managed.
The key comparison function compare() is utilized while sorting multisets. Search, insert, and remove operations all have logarithmic complexity.
The insertion sequence of the elements that compare equivalents has stayed the same since the release of C++11.
A container, an aware allocator container, an associative container, and a reversible container are essential for multisets.
Binary search trees are where multisets are most commonly used.
Once entered into the container, the value of the elements in multisets cannot be changed; as a result, the items are always constant. But it is possible to conduct the insertion and removal procedure.
Syntax of Multiset:
template<class P, // multiset::key_type/value_type
class Comp = less<P> // multiset::key_compare/value_compare
class Alloc = allocator<P>> // multiset::allocator_type
> class multiset;
where P = multiset:: key_type/value type.
It is crucial for us to include the set's header file when we utilize a multiset.
To enable all of the multiset's features, we use #include <set>.
- Multiset container characteristics:
1 - Associative: Rather than being in the container's absolute position, their key reference elements are present in associative containers.
2- Ordered: The components of the multiset container are always arranged in a specific order. According to a predetermined order, the container assigns a place to every element that is introduced.
3 - Multiple equivalent keys: According to this trait, a number of objects in the multisets may have identical keys.
4 - Allocator-aware: This container often employs an allocator object to address the storage requirements on a dynamic basis.
How to Make a Multiset?
Use C++'s multiset class if require a set's sorting capabilities but also wish to support repetitions in the container. We can apply the same functions we did for sets to multisets.
When you don't need a key/value combination but still require the search features of a set with several elements per key, you can use a multiset in C++.
Multiset-specific functions
- begin(): Responsible for bringing an iterator back to the first item of the multiset.
Parameters: None
Return type: iterator
- end(): Accountable for returning an iterator to the theoretical item following the multiset's last item.
Parameters: None
Return type: iterator
- size(): responsible for returning the multiset's entire number of elements.
Parameters: None
Return type: integer - total number of elements in the multiset
- insert(element): adds a new element to the multiset.
Time Complexity: O(logN) where N is the size of the multiset
Parameters: the element that needs to be inserted
Return type: void
- find(element): If the element is located, the function returns an iterator pointing to it; otherwise, it returns an iterator pointing to the multiset's end.
Parameters: the element which needs to be found
Return type: iterator
- clear(): It eliminates every element of the multiset.
Parameters: None
Return type: void
- empty(): It informs us whether or not the multiset is empty.
Parameters: None
Return type: Boolean; true if a multiset is empty; otherwise, false.
- erase(value): Eliminate components from the multiset.
Time Complexity: O(logN) where N represents the multiset's size.
Parameters: the value to be deleted or iterators indicating the intervals between which the value should be erased.
Return type: void
Example Program
#include<iostream>
#include<set>
using namespace std;
int main() {
multiset <int> c1;
multiset <int, greater <int> > c2;
for (int i = 0; i < 6; i++) {
c1.insert(i + 1);
}
for (int i = 0; i < 6; i++) {
c1.insert(i + 1);
}
for (int i = 0; i < 6; i++) {
c2.insert((i + 1) * 10);
}
for (int i = 0; i < 6; i++) {
c2.insert((i + 1) * 10);
}
set <int> ::iterator sec;
for (sec = c1.begin(); sec != c1.end(); sec++)
cout << * sec << " ";
cout << '\n';
for (sec = c2.begin(); sec != c2.end(); sec++)
cout << * sec << " ";
cout << endl;
c1.erase(2);
c2.erase(c2.begin(), c2.find(15));
cout << "the size of set is after an element has been erased." << c1.size() << '\n';
int value = 8;
if (c1.find(value) != c1.end())
cout << "The set includes " << value << endl;
else
cout << "The set does not include " << value << endl;
cout << "New elements of set are ";
for (sec = c1.begin(); sec != c1.end(); sec++)
cout << * sec << " ";
cout << endl;
c1.clear();
if (c1.empty() == true) {
cout << "set is empty!";
}
return 0;
}
Explanation:
- In the main() function, we have declared a multiset of integer type with the name of “c1”.
- We have declared a second multiset of integer type with the name "c2". This c2 is a std::multiset, storing int and using a comparison functor of the type std::greater<int>.
- In the c2 multiset, we stored the elements in descending order because we have a comparison function.
- In the for loop, we initialized “i” and have a condition that “i” must be less than 6. so in c1, we stored the values from 1 to 6 twice and in c2 from 10, 20 to 60 twice, but in reverse order ( descending order)
- We created an iterator, 'sec', which will iterate over the set to get the values. First, we iterated the c1 set, and from beginning to ending (using being() and end() functions), we printed the values of c1.
- So, we got the output as 1,1,2,2,3,3,4,4,5,5,6,6 in c1.
- In the same way, we iterated the set c2 and printed the values, which are: 60,60,50,50,40,40,30,30,20,20,10,10.
- In the set c1, we deleted values at the second index, which were: 2,2, and printed the size of set c1, which is 12-2 = 10
- for c2, we started deleting the values until we found the value 15, but as we know, 15 is not present in the c2, so all the values from the beginning to end will be deleted in the c2.
- For c1, we compare if the value 8 is present in the set or not since it is not present, so we terminated the if condition and printed the statement of the else condition.
- Now using an iterator, we printed the values of set c1.
- We use the clear() function for the set c1, which will remove all the elements in c1, and c1 is now empty so that it will return true for the function empty().
Program Output:
Removing Element from multiset
Program:
#include <iostream>
#include<set>
using namespace std;
int main()
{
// Integer type multiset with the name x.
multiset<int> x;
// Inserting of integers in the multiset.
x.insert(10);
x.insert(10);
x.insert(10);
x.insert(10);
// the multiset is being updated with the same values.
// the output that is produced is 4.
cout << x.count(10) << endl;
// removing a single instance from a group of numerous instances.
//By using the erase function, it will only remove 1 value of 10 from the multiset.
x.erase(x.find(10));
//the output that is produced is 3.
cout << x.count(10) << endl;
// Let's attempt to remove every element from the multiset.
// deleting every instance of the number 10
x.erase(10);
// Due to the multiset's deletion of every occurrence of a value, the output we receive will be equal to 0.
cout << x.count(10) << endl;
return 0;
}
Explanation:
- In the main() function, we have declared a multiset of integer type with the name of “x”.
- Then we inserted the elements in the multiset.
- In the multiset, we insert the same type of value, which is 10.
- Then we used a count() function to determine the multiple values of the same key. Then we get the output is 4.
- After that we removed the single instance from the numerous multiset instance. For this, we have used erase(find()) function.
- This erase(find()) function erase only 1 value of 10 from the multiset.
- Then we try to remove all instance from the multiset. For this, we used erase() function.
- Due to this, the output we receive will equal 0 because all instance of the value is deleted from the multiset.
Program Output:
Using size(), find the size of a multiset in C++:
#include<iostream>
#include<set>
using namespace std;
int main()
{
// Integer type multiset with the name x.
multiset<int> x;
// with the help of the insert() function, we will insert the element in a multiset container.
// Inserting first element.
x.insert(15);
// Inserting second element.
x.insert(16);
// Inserting third element.
x.insert(17);
cout << "The multiset's size is equivalent to: " << x.size();
// inserting Four elements
x.insert(10);
x.insert(12);
x.insert(14);
x.insert(16);
cout <<endl << "The multiset's size is equivalent to: " << x.size();
x.insert(5);
x.insert(6);
// Calculating the size of the multiset with the help of the size() function.
cout << endl << "The multiset's size is equivalent to: " << x.size();
return 0;
}
Explanation:
- In the main() function, we have declared a multiset of integer type with the name of “x”.
- Then we inserted the elements in the multiset container with the help of the insert() function.
- The first element, which has a value of 15, is inserted first. The second element, which has a value of 16, is inserted next. Finally, the third element, which has a value of 17, is inserted.
- The size of the multiset is then calculated with the aid of the size() function. The size() function gives the size of the multiset is 3.
- Next, the four elements with different types of values—10, 12, 14, and 16—are added to the multiset container.
- Then we again calculated the size of the multiset, using the size() function, and we will get the size of the multiset is 7.
- Next, the two elements with different types of values – 5 and 6 are added to the multiset container.
- And after calculating the size of the multiset, using the size() function, we will get the size of the multiset is 9.
Program Output:
Using the clear() function, all of the elements are removed from the Multiset Container.
Program:
#include <iostream>
#include<set>
using namespace std;
int main()
{
// Initializing the array named b with different values
int b[] = { 1, 2, 3, 4, 5 };
//initializes the set using the values of the b array.
multiset<int> x(b, b + 5);
//printing every element in the set.
cout << "The multiset's elements are listed as follows: ";
for (auto i = x.begin(); i != x.end(); i++)
cout << *i << " ";
cout << "After using clear() function, the size is equal to: ";
// erases off every element that is present in the multiset.
x.clear();
cout << x.size();
return 0;
}
Explanation:
- We initialized an array with the name "b" in the main() function, and we initialized various values in this array.
- We have 5 values in array b, and we declared a multiset of integer type which will contain the values from array b
- It will contain the initial 5 values of array b as we have declared it to b+5.
- now it will also contain the values: 1,2,3,4,5
- using the iterator, we printed the values of the multiset.
- Now we used the clear() function on the multiset, which will remove all the elements from the multiset, and then we print its size using the size() function, which will return 0.
Program Output:
Template Parameters:
The key, Allocator, and comparison class are the three template parameters.
- Key: The key controls the type of elements contained in the container. Each component of a multiset is its key.
- Compare: A class that receives two arguments of the same type as the container elements returns a boolean value. When x is to come before y in a strict weak ordering action, the expression comp(x,y), where x comp is an object of this type, and x and y are parts of the container, should return true. The class in question may implement a function pointer or a function call operator. When using the less-than operator, the default value of less is equivalent (all times).
- Allocator: The kind of allocator object determines the allocation paradigm for storage. As a default, the allocator class template for type Key is utilized, which specifies the most basic, value-neutral memory allocation paradigm.
Conclusion:
Multisets are included in the C++ STL (Standard Template Library).
Multisets are sorted value storage associative containers, similar to Sets (the value is the key of type T).
Multisets, unlike sets, can contain a variety of redundant keys.
Multisets, by default, compare the operator and the keys.
Items in a multiset's value can be added or subtracted from it but not modified (The items are always const).
A key of type T that is the content of a multiset is allowed, unlike Sets, to contain additional keys.