std::multiset

std::multiset is an associative container that allows you to store multiple elements with duplicate keys in a sorted order.

Unlike std::set, it allows duplicate elements, meaning you can have multiple occurrences of the same value.

Overview:

• Header file: <set>
• Class template: std::multiset<T, Compare, Allocator>
• Implemented as a self-balancing binary search tree (usually a Red-Black Tree).
• Elements are sorted based on the specified comparator or the default less-than comparator if none is provided.
• Elements are stored as const T objects.

Important Functions and Operations:

insert():

Inserts a new element into the std::multiset.

• Time Complexity: O(log N) on average (for each element being inserted)
• Space Complexity: O(1)

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    // Single element insertion
    ms.insert(1);

    // Multiple element insertion using initializer list
    ms.insert({2, 3, 2});

    return 0;
}

count():

Returns the number of occurrences of a specific element in the std::multiset.

• Time Complexity: O(log N) on average
• Space Complexity: O(1)

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    ms.insert({1, 2, 3, 2});

    std::cout << "Number of occurrences of 2: " << ms.count(2) << std::endl;

    return 0;
}

find():

Returns an iterator pointing to the first occurrence of a specific element or the end() iterator if the element is not found.

• Time Complexity: O(log N) on average
• Space Complexity: O(1)

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    ms.insert({1, 2, 3, 2});

    auto it = ms.find(2);
    if (it != ms.end()) {
        std::cout << "Found element 2." << std::endl;
    } else {
        std::cout << "Element 2 not found." << std::endl;
    }

    return 0;
}

equal_range():

Returns a pair of iterators representing the range of elements with a specific value.

• Time Complexity: O(log N) on average
• Space Complexity: O(1)

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    ms.insert({1, 2, 3, 2});

    auto range = ms.equal_range(2);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Found element 2." << std::endl;
    }

    return 0;
}

erase():

Removes elements from the std::multiset.

• Time Complexity: O(log N) on average (per erased element)
• Space Complexity: O(1)

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    ms.insert({1, 2, 3, 2});

    // Remove all occurrences of element 2
    ms.erase(2);

    return 0;
}

Iterating through the std::multiset:

• Time Complexity: O(N) to traverse all elements.
• Space Complexity: O(1)

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    ms.insert({1, 2, 3, 2});

    // Iterating through the multiset
    for (const auto& element : ms) {
        std::cout << "Element: " << element << std::endl;
    }

    return 0;
}

std::multiset maintains elements in sorted order, which allows for efficient searching and inserting. However, keep in mind that due to its self-balancing tree nature, it may have slightly higher overhead in comparison to std::unordered_multiset in terms of both time and space complexity. The choice between std::multiset and std::unordered_multiset depends on the specific use case and the required operations.