C++ multiset

---

Introduction

In C++, a multiset is an associative container that allows duplicate elements and stores them in sorted order. It is part of the C++ Standard Library and is defined in the <set> header. Like a std::set, a std::multiset is a collection of elements, but unlike a set, it permits duplicate values. The elements in a multiset are automatically ordered, and you can search for an element or perform other operations in logarithmic time (O(log n)) due to the underlying self-balancing binary search tree (usually a Red-Black Tree).

---

Syntax

To declare a multiset, the syntax is:

std::multiset<Type> multiset_name;

Where:

• Type: The type of the elements in the multiset (e.g., int, std::string).

You can also specify a custom comparison function to order the elements in a custom way:

std::multiset<Type, Compare> multiset_name;

Where:

• Compare: A function or function object that defines the sorting order of the elements (by default, it sorts in ascending order).

---

Declaring and Initializing a Multiset

Example 1: Basic Multiset Declaration

#include <iostream>
#include <set>

int main() {
    // Declare a multiset that stores integers
    std::multiset<int> multiset;

    // Inserting elements into the multiset
    multiset.insert(10);
    multiset.insert(20);
    multiset.insert(20);
    multiset.insert(30);
    multiset.insert(10);

    // Displaying the elements in the multiset
    for (int elem : multiset) {
        std::cout << elem << " ";
    }

    return 0;
}

Output:

10 10 20 20 30

Explanation:

• The multiset stores the elements in ascending order.
• The elements 10 and 20 appear twice, showcasing the multiset's ability to store duplicates.
• Elements are automatically ordered by default (ascending order).

---

Operations on Multisets

1. Insert Elements

You can insert elements into a multiset using the insert() method. Unlike a set, a multiset allows duplicate elements:

multiset.insert(40);  // Insert 40 into the multiset
multiset.insert(10);  // Insert 10 again (duplicate allowed)

2. Erase Elements

You can remove elements by key or by iterator.

• Remove by key:

  multiset.erase(10);  // Removes all instances of 10 from the multiset
  

• Remove by iterator:

  auto it = multiset.find(20);
  multiset.erase(it);  // Removes the first occurrence of 20 from the multiset
  

3. Find Elements

You can search for an element in the multiset using the find() function. This function returns an iterator pointing to the first occurrence of the element or multiset.end() if the element is not found.

auto it = multiset.find(20);
if (it != multiset.end()) {
    std::cout << "Found: " << *it << std::endl;  // Output: Found: 20
} else {
    std::cout << "Element not found!" << std::endl;
}

4. Count Elements

You can count the occurrences of a specific element in a multiset using the count() method. Since a multiset allows duplicate elements, the count() method will return the number of occurrences of the given key.

std::cout << "Count of 10: " << multiset.count(10) << std::endl;  // Output: 2
std::cout << "Count of 20: " << multiset.count(20) << std::endl;  // Output: 2

5. Size and Emptiness

You can check the size of the multiset and whether it is empty using the size() and empty() methods:

std::cout << "Size of multiset: " << multiset.size() << std::endl;
std::cout << "Is multiset empty? " << (multiset.empty() ? "Yes" : "No") << std::endl;

6. Clear the Multiset

You can remove all elements from the multiset using the clear() method:

multiset.clear();  // Removes all elements from the multiset

---

Iterating Over a Multiset

You can iterate over the elements of a multiset using an iterator or a range-based for loop:

Example 1: Using Iterator

for (auto it = multiset.begin(); it != multiset.end(); ++it) {
    std::cout << *it << " ";
}

Example 2: Using Range-Based For Loop

for (int elem : multiset) {
    std::cout << elem << " ";
}

---

Custom Sorting in Multisets

By default, elements in a multiset are stored in ascending order. However, you can define a custom sorting order by providing a comparator.

Example: Custom Sorting (Descending Order)

#include <iostream>
#include <set>

bool descendingOrder(int a, int b) {
    return a > b;  // Custom comparator for descending order
}

int main() {
    // Create a multiset with a custom comparator
    std::multiset<int, bool(*)(int, int)> multiset(descendingOrder);

    multiset.insert(10);
    multiset.insert(30);
    multiset.insert(20);
    multiset.insert(20);
    multiset.insert(40);

    // Display elements in descending order
    for (const auto& elem : multiset) {
        std::cout << elem << " ";
    }

    return 0;
}

Output:

40 30 20 20 10

---

Advantages of Using std::multiset

1. Duplicate Elements: Unlike a std::set, a multiset allows duplicate elements, making it ideal when you need to store multiple instances of the same value.
2. Efficient Searching: Just like a std::set, operations like search, insertion, and deletion are performed in logarithmic time (O(log n)) due to the self-balancing binary search tree.
3. Automatic Ordering: Elements are automatically sorted based on the keys. This makes it easier to manage ordered collections.
4. Versatile: You can perform operations such as searching for an element, counting occurrences, and removing duplicates efficiently.

---

When to Use std::multiset

Use a std::multiset when:

• You need to store multiple instances of the same element.
• You want the elements to be automatically ordered.
• You need efficient operations like searching, insertion, and deletion, while allowing duplicate values.

---

---