C++ unordered_multiset

---

Introduction

The std::unordered_multiset is a container in the C++ Standard Library that stores multiple instances of the same element in an unordered fashion, using a hash table. Unlike std::unordered_set, which only stores unique elements, an unordered multiset allows multiple copies of the same element. It provides efficient insertion, deletion, and search operations, all with an average time complexity of O(1).

An unordered multiset does not maintain any specific order of its elements and is often used when you need to store and manage elements with duplicates but without worrying about their ordering. It can be particularly useful when you need to track the frequency of elements or simply allow multiple copies of the same item.

---

Syntax

To declare an unordered multiset, use the following syntax:

std::unordered_multiset<ElementType> unordered_multiset_name;

Where:

• ElementType is the type of element you want to store (e.g., int, std::string).

You can also specify a custom hash function and comparison function:

std::unordered_multiset<ElementType, Hash, Compare> unordered_multiset_name;

Where:

• Hash is a custom hashing function.
• Compare is a comparison function, though the default comparator is generally sufficient.

---

Declaring and Initializing an Unordered Multiset

Example 1: Basic Unordered Multiset Declaration

#include <iostream>
#include <unordered_set>

int main() {
    // Declare an unordered multiset of integers
    std::unordered_multiset<int> umset;

    // Insert elements into the unordered multiset
    umset.insert(10);
    umset.insert(20);
    umset.insert(20);
    umset.insert(30);
    umset.insert(40);
    umset.insert(40);
    umset.insert(40);

    // Displaying the elements of the unordered multiset
    for (const auto& element : umset) {
        std::cout << element << std::endl;
    }

    return 0;
}

Output:

10
20
20
30
40
40
40

Note: Unlike std::unordered_set, the unordered_multiset allows duplicate elements and does not guarantee any order for the elements.

---

Operations on Unordered Multisets

1. Insert Elements

You can insert elements into an unordered multiset using the insert() method. Duplicate elements are allowed.

umset.insert(50);  // Inserts 50 into the unordered multiset
umset.insert(20);  // Inserts another 20 into the unordered multiset

2. Find Elements

You can search for an element in the unordered multiset using the find() method. This returns an iterator pointing to the element if found, or unordered_multiset::end() if the element is not present.

auto it = umset.find(30);  // Search for the element 30
if (it != umset.end()) {
    std::cout << "Found: " << *it << std::endl;
} else {
    std::cout << "Element not found!" << std::endl;
}

3. Erase Elements

You can remove elements from the unordered multiset using the erase() method. When erasing by value, it removes all occurrences of the element.

• Remove by value:

  umset.erase(20);  // Removes all occurrences of 20 from the unordered multiset
  

• Remove by iterator:

  auto it = umset.find(40);
  umset.erase(it);  // Removes the first occurrence of 40
  

4. Count Elements

You can count the number of occurrences of a particular element in the unordered multiset using the count() method. Since it allows duplicates, count() will return the number of times the element appears.

std::cout << "Count of 20: " << umset.count(20) << std::endl;  // Output: 2
std::cout << "Count of 40: " << umset.count(40) << std::endl;  // Output: 3

5. Size and Emptiness

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

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

6. Clear the Unordered Multiset

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

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

---

Iterating Over an Unordered Multiset

You can iterate over the elements of an unordered multiset using an iterator or a range-based for loop. Since an unordered multiset allows duplicates, each occurrence of an element will be visited in the iteration.

Example 1: Using Iterator

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

Example 2: Using Range-Based For Loop

for (const auto& element : umset) {
    std::cout << element << std::endl;
}

---

Custom Hash Function

If you're using a custom type as an element in the unordered multiset, you must define a custom hash function. Here's an example with a custom class.

Example: Custom Hash Function for a Class

#include <iostream>
#include <unordered_set>
#include <string>

class Person {
public:
    std::string name;
    int age;

    Person(std::string name, int age) : name(name), age(age) {}

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return std::hash<std::string>()(p.name) ^ std::hash<int>()(p.age);  // Combine hashes of name and age
    }
};

int main() {
    std::unordered_multiset<Person, PersonHash> umset;

    umset.insert(Person("Alice", 30));
    umset.insert(Person("Bob", 25));
    umset.insert(Person("Alice", 30));  // Inserting duplicate entry of "Alice, 30"

    for (const auto& person : umset) {
        std::cout << person.name << " (" << person.age << ")" << std::endl;
    }

    return 0;
}

Output:

Alice (30)
Bob (25)
Alice (30)

---

Advantages of Using std::unordered_multiset

1. Fast Lookup: Like unordered_set, unordered_multiset offers O(1) average time complexity for insertion, deletion, and lookup operations.
2. Allows Duplicates: Unlike unordered_set, an unordered multiset allows multiple occurrences of the same element, making it suitable for use cases where duplicates are allowed.
3. Efficient Handling of Frequent Operations: The hash table implementation ensures that insertion and removal operations are efficient even for large datasets.
4. Unordered Storage: The elements are stored in an unordered fashion, allowing for faster insertion and deletion, but you will not be able to retrieve elements in any particular order.

---

When to Use std::unordered_multiset

• Handling Frequency Counts: If you need to keep track of the frequency of elements (like counting word occurrences in a document), unordered_multiset is a good choice as it allows duplicates and is efficient in terms of insertion and lookup.
• Large Datasets with Duplicates: When dealing with large datasets where elements may appear multiple times, and you don't need the elements to be ordered.
• Efficient Set Operations: When you need to frequently insert, delete, or check for the presence of elements without worrying about the order of elements.

---

---