4 ways to remove elements from Multiset in C++ STL

Multiset is a container in C++ STL (Standard Template Library) that stores elements in a specific order as per their value. It is similar to a set but allows duplicates. Multiset is implemented as a balanced binary search tree. Removing elements from a multiset is an important operation in many algorithms and applications. In this article, we will explore different ways to remove elements from a multiset in C++ STL including:

• Using the multiset::erase() function
• Using the multiset::erase() function with an iterator
• Using the multiset::erase() function with a range of iterators
• Using the multiset::clear() function

Let's dive into each method in detail.

1. multiset::erase() function

The multiset::erase() method removes the element(s) from the multiset with the given value.

The syntax of this method is as follows:

size_type erase (const key_type& key_val);

The first overload of the erase() function takes the key value of the element to be removed as its argument. This overload removes all the elements from the multiset that have the specified key value. The key value is used to compare the elements in the multiset, and all the elements that match the key value are removed.

Here's an example:

#include <iostream>
#include <set>
using namespace std;

int main() {
  multiset<int> ms {1, 2, 3, 4, 5, 5, 5};
  
  ms.erase(5);

  for (auto& num : ms) {
    cout << num << " ";
  }

  return 0;
}

The output of this code will be:
1 2 3 4

As you can see, the three occurrences of the number 5 were removed from the multiset, and the remaining elements were printed.

NOTE: If you wish to remove / erase a particular element only once, then first find that element and then erase it. Here's an example:

#include <iostream>
#include <set>
using namespace std;

int main(){
    multiset<int> ms {1, 2, 2, 3, 3, 3};
    
    //remove only one occurance of 2 from the multiset
    ms.erase(ms.find(2));
    for (auto& x: ms){
        cout<<x<<" ";
    }
}

Output:
1 2 3 3 3

2. multiset::erase() function with an iterator

The multiset::erase() method can also be used with an iterator to **remove a specific element from the multiset. **
The syntax of this method is as follows:

iterator erase (const_iterator position);

The method returns an iterator to the element that followed the last element removed. Here's an example:

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms = {1, 2, 3, 4, 5};

    // remove element at position 2
    auto it = ms.begin();
    advance(it, 2);
    ms.erase(it);

    for (auto& x : ms) {
        cout << x << " ";
    }

    return 0;
}

The output of this code will be:
1 2 4 5

In the above code, we create a multiset s that contains some elements. We then get an iterator to the element at position 2 using the advance() function, and call the erase() function with this iterator as the argument, which removes the element at position 2 from the multiset. Finally, we iterate over the remaining elements in the multiset and print them.

3. multiset::erase() function with a range of iterators

The multiset::erase() method can also be used with a range of iterators to remove a range of elements from the multiset. The syntax of this method is as follows:

iterator erase (const_iterator first, const_iterator last);

The method removes the elements in the range first -> last where first is included and last is excluded and returns an iterator to the element that followed the last element removed. Here's an example:

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> ms = {1, 2, 2, 3, 3, 3, 4, 4, 5};
    auto it = ms.find(2); // find first occurrence of 2
    auto end = ms.find(4); // find last occurrence of 4
    ms.erase(it, end); // remove range from [it, end)
    for (auto& i : ms) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

The output of this code will be:
1 4 5

In this example, we first create a multiset called ms with some duplicate elements. We then use the find() function to get iterators to the first and last occurrence of the value 2 and 4, respectively. We pass these iterators to the erase() function to remove all elements between them.

The output of the program shows the remaining elements in the multiset after the range has been removed.

Time Complexity:
The time complexity of using the multiset::erase() method with an iterator is
O(log N), where N is the number of elements in the multiset.
However, it is important to note that if multiple elements need to be removed from the multiset, the time complexity can increase significantly. For example, if we want to remove all elements with a specific value, we would need to iterate through the entire multiset and remove each instance one-by-one, resulting in a time complexity of O(N log N). In such cases, it may be more efficient to use other methods such as the multiset::erase() method with a value or range.

4. multiset::clear() function

The multiset::clear() method is a built-in function in the C++ STL that is used to remove all the elements from a multiset container. It doesn't delete the multiset container itself, but just removes all its elements, making the multiset empty.
Example:

#include <iostream>
#include <set>
using namespace std;

int main() {
   multiset<int> ms = {1, 2, 2, 3, 3, 3};

   // removing all elements from the multiset
   ms.clear();

   return 0;
}

the multiset becomes empty.

Time Complexity: The complexity of the multiset::clear() function is linear or O(n), where n is the number of elements in the multiset. This is because the function simply traverses through the multiset and deletes each element one by one.

In general, it is important to keep in mind the time complexity of various operations when working with data structures like multiset, especially when dealing with large amounts of data. In cases where frequent modifications to the multiset are expected, it might be worth considering using other data structures like unordered_set or vector, which have faster erase times.