Home > front end >  How to find occurrences of a pair in a multimap
How to find occurrences of a pair in a multimap

Time:07-04

I have been trying to write a program that finds the occurrences of a pair in a multimap. So far I am thinking of using multimap::equal_range.

For example, if my multimap is {(BO, MA), (CL, SC), (DA, TX), (FL, MI), (FL, MI), (MI, FL), (OR, FL)} and I search for all occurrences of (FL, MI) in the multimap, then my program should ideally return two iterators, pointing to the 3rd and 5th elements. I can then subtract the two iterators to find the number of occurrences of the pair. However, multimap::equal_range only checks if a key is equivalent to a single value.

Is there a way to use multimap::equal_range to indicate the range of iterators pointing to the pairs with the same key and the same value of the target pair? Or is there an existing method that I can use? Any help is appreciated!

CodePudding user response:

I suggest using a std::unordered_map<std::string, std::unordered_map<std::string, unsigned>> instead. You then get 2 fast lookups and the count without iterating.

Example:

#include <iostream>
#include <iterator>
#include <map>
#include <unordered_map>

int main(void) {
    // your original looks something like this:
    std::multimap<std::string, std::string> m{
        {"BO", "MA"}, {"CL", "SC"}, {"DA", "TX"}, {"FL", "MI"}, {"BO", "MA"},
        {"FL", "OR"}, {"FL", "MI"}, {"MI", "FL"}, {"OR", "FL"}};

    // my suggested map:
    std::unordered_map<std::string, std::unordered_map<std::string, unsigned>> m2;

    // transform your original map to my suggested map:    
    for(auto&[k, v]: m)   m2[k][v];

    // lookup:
    std::cout << m2["FL"]["MI"] << '\n'; // prints 2
}
  • Related