unordered_set vs unordered_multiset

As we can see most of the operations work similarly to that of unordered_set but some things are different such as:

equal_range(Val) function returns a pair of types where the first iterator points to the first position of Val and the second points to the last position of Val in the data structure. While erase(Val) function deletes all its instances from the data structure.
For example, if some value v has occurred t times in unordered_multiset and when erase is called, v is deleted completely which is not an expected behavior many times.
We can delete only one copy of some value by using the find function and the iterator version of erasing, as the find function returns the iterator to the first position of found value we can pass this iterator to erase instead of the actual value to delete only one copy. The following program demonstrates how this happens:

C++

//  C++ program to delete one copy from unordered set
#include <bits/stdc++.h>
using namespace std;
 
//  making typedef for short declaration
typedef unordered_multiset<int>::iterator umit;
 
//  Utility function to print unordered_multiset
void printUset(unordered_multiset<int> ums)
{
    // begin() returns iterator to first element of
    // set
    umit it = ums.begin();
    for (; it != ums.end(); it++)
        cout << *it << " ";
    cout << endl;
}
 
//  function to delete one copy of val from set
void erase_one_entry(unordered_multiset<int>& ums,
                    int val)
{
    //  find returns iterator to first position
    umit it = ums.find(val);
 
    //  if element is there then erasing that
    if (it != ums.end())
       ums.erase(it);
}
 
//  Driver program to check above function
int main()
{
    //  initializing multiset by initializer list
    unordered_multiset<int> ums ({1, 3, 1, 7, 2, 3,
                                 4, 1, 6});
 
    int val = 1;
    printUset(ums);
    erase_one_entry(ums, val);
    printUset(ums);
}

Output

6 4 2 7 3 3 1 1 1 
6 4 2 7 3 3 1 1

C++ unordered_multiset

The unordered_multiset in C++ STL is an unordered associative container that works similarly to an unordered_set. The only difference is that we can store multiple copies of the same key in this container.

It is also implemented using a hash table so the time complexity of the operations is O(1) on average which can go up to linear time O(n) in the worst case. Internally when an existing value is inserted, the data structure increases its count which is associated with each value. A count of each value is stored in unordered_multiset, it takes more space than unordered_set (if all values are distinct).

Due to hashing of elements, it has no particular order of storing the elements so all element can come in any order but duplicate element comes together.

Syntax:

std::unordered_multiset<data_type> name;

For Example:

C++

// C++ program to demonstrate various function
// of unordered_multiset
#include <bits/stdc++.h>
using namespace std;
 
// making typedef for short declaration
typedef unordered_multiset<int>::iterator umit;
 
// Utility function to print unordered_multiset
void printUset(unordered_multiset<int> ums)
{
    //  begin() returns iterator to first element of set
    umit it = ums.begin();
    for (; it != ums.end(); it++)
        cout << *it << " ";
    cout << endl;
}
 
//  Driver program to check all function
int main()
{
    //  empty initialization
    unordered_multiset<int> ums1;
 
    //  Initialization by intializer list
    unordered_multiset<int> ums2(
        { 1, 3, 1, 7, 2, 3, 4, 1, 6 });
 
    //  Initialization by assignment
    ums1 = { 2, 7, 2, 5, 0, 3, 7, 5 };
 
    //  empty() function return true if set is empty
    // otherwise false
    if (ums1.empty())
        cout << "unordered multiset 1 is empty\n";
    else
        cout << "unordered multiset 1 is not empty\n";
 
    //  size() function returns total number of elements
    // in data structure
    cout << "The size of unordered multiset 2 is : "
         << ums2.size() << endl;
 
    printUset(ums1);
 
    ums1.insert(7);
 
    printUset(ums1);
 
    int val = 3;
 
    // find function returns iterator to first position
    // of  val, if exist otherwise it returns iterator
    // to end
    if (ums1.find(val) != ums1.end())
        cout << "unordered multiset 1 contains " << val
             << endl;
    else
        cout << "unordered multiset 1 does not contains "
             << val << endl;
 
    //  count function returns total number of occurrence in
    //  set
    val = 5;
    int cnt = ums1.count(val);
    cout << val << " appears " << cnt
         << " times in unordered multiset 1 \n";
 
    val = 9;
 
    //  if count return >0 value then element exist
    //  otherwise not
    if (ums1.count(val))
        cout << "unordered multiset 1 contains " << val
             << endl;
    else
        cout << "unordered multiset 1 does not contains "
             << val << endl;
 
    val = 1;
 
    // equal_range returns a pair, where first is iterator
    // to first position of val and second it iterator to
    // last position to val
    pair<umit, umit> erange_it = ums2.equal_range(val);
    if (erange_it.first != erange_it.second)
        cout << val
             << " appeared atleast once in "
                "unoredered_multiset \n";
 
    printUset(ums2);
 
    // erase function deletes all instances of val
    ums2.erase(val);
 
    printUset(ums2);
 
    // clear function deletes all entries from set
    ums1.clear();
    ums2.clear();
 
    if (ums1.empty())
        cout << "unordered multiset 1 is empty\n";
    else
        cout << "unordered multiset 1 is not empty\n";
}

Output

unordered multiset 1 is not empty
The size of unordered multiset 2 is : 9
3 0 5 5 7 7 2 2 
3 0 5 5 7 7 7 2 2 
unordered multiset 1 contains 3
5 appears 2 times in unordered multiset 1 
unordered multiset 1 does not contains 9
1 appeared atleast once in unoredered_multiset 
6 4 2 7 3 3 1 1 1 
6 4 2 7 3 3 
unordered multiset 1 is empty

unordered_set vs unordered_multiset

C++

C++ unordered_multiset

C++

Categories

Contact US

unordered_set vs unordered_multiset

C++

C++ unordered_multiset

C++

Similar Reads

Categories

Contact US