std::multimap

• std::multimap is an associative container that allows you to store multiple pairs of keys and values.
• Unlike std::map, it allows duplicate keys, which means you can have multiple values associated with the same key.

• Header file: <map>
• Class template: std::multimap<Key, T, Compare, Allocator>
• Requires the keys to be ordered, either through the default less-than comparator or a custom comparator.
• Implemented as a self-balancing binary search tree (usually a Red-Black Tree).
• Key-value pairs are stored as std::pair<const Key, T> elements.

Important Functions and Operations:

insert():

Inserts a new key-value pair or multiple pairs into the std::multimap. If the key already exists, the new value(s) will be added to the existing ones.

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

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mm;

    // Single pair insertion
    mm.insert(std::make_pair(1, "One"));

    // Multiple pair insertion using initializer list
    mm.insert({{2, "Two"}, {3, "Three"}, {2, "Second Two"}});

    return 0;
}

count():

Returns the number of elements with a specific key in the std::multimap.

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

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mm;

    mm.insert({{1, "One"}, {2, "Two"}, {2, "Second Two"}, {3, "Three"}});

    std::cout << "Number of elements with key 2: " << mm.count(2) << std::endl;

    return 0;
}

find():

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

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

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mm;

    mm.insert({{1, "One"}, {2, "Two"}, {2, "Second Two"}, {3, "Three"}});

    auto it = mm.find(2);
    if (it != mm.end()) {
        std::cout << "Found key 2, value: " << it->second << std::endl;
    } else {
        std::cout << "Key 2 not found." << std::endl;
    }

    return 0;
}

equal_range():

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

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

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mm;

    mm.insert({{1, "One"}, {2, "Two"}, {2, "Second Two"}, {3, "Three"}});

    auto range = mm.equal_range(2);
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << "Key 2, value: " << it->second << std::endl;
    }

    return 0;
}

erase():

Removes elements from the std::multimap.

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

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mm;

    mm.insert({{1, "One"}, {2, "Two"}, {2, "Second Two"}, {3, "Three"}});

    // Remove all elements with key 2
    mm.erase(2);

    return 0;
}

Iterating through the std::multimap:

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

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> mm;

    mm.insert({{1, "One"}, {2, "Two"}, {2, "Second Two"}, {3, "Three"}});

    // Iterating through the multimap
    for (const auto& pair : mm) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

Remember that std::multimap maintains the keys 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_multimap in terms of both time and space complexity. The choice between std::multimap and std::unordered_multimap depends on the specific use case and the required operations.