Effectively getting items from map based on specific sort

user_1446710 0
Viewed 45

I have a fairly easy problem: I have an std::map<int,T> and another std::set<int> (can be std::vector or similar too).

In the map I store items, and in the other container I'm storing favorites (of the map).

At some point, I'd need to retrieve (all) items from the map, but starting with the favorites defined by the other container.

Here is my minimal repro, I solved it very ugly, and ineffective:

#include <iostream>
#include <string>
#include <set>
#include <map>

using namespace std;

map<int, string> myMap;
set<int> myFavorites;


int main()
{
    
    myMap.emplace(1, "but I don't like this");
    myMap.emplace(12, "So it will go below");
    myMap.emplace(31, "This one will come first, and");
    myMap.emplace(44, "under my favorites");
    myMap.emplace(52, "then this will follow");
    
    myFavorites.insert(52);
    myFavorites.insert(31);
    
    cout << "My map:" << endl;
    for(auto p : myMap) {
        cout << "#" << p.first << "=" << p.second << endl;
    }
    
    cout << endl << "My favorites:" << endl;
    for(auto p : myFavorites) {
        cout << "#" << p << endl;
    }
    
    cout << endl << "All items starting with my favorites:" << endl;
    for(auto p : myFavorites) {
        auto item = myMap.find(p);
        if (item != myMap.end()) cout << "#" << item->first << "=" << item->second << endl;
    }
    for(auto p : myMap) {
        if (myFavorites.find(p.first) != myFavorites.end()) continue;
        cout << "#" << p.first << "=" << p.second << endl;
    }
}

What really bothers me is the last loop, where each iterations would call find on the set.

Required output is:

All items starting with my favorites:
#31=This one will come first, and
#52=then this will follow
#1=but I don't like this
#12=So it will go below
#44=under my favorites

Here is the above source in Coliru for making it easier: https://coliru.stacked-crooked.com/a/731fa76d90bfab00

Both map and set might be changed, but replacements needs to implement the same interfaces as originals.

I'm looking for a way to solve this more efficient than my original "brute-force" one.

Please note: map must not be "reordered"! I just need to query (retrieve) its items with custom sorting!

Note2: I know map can have a comparison operator. But I'd need to have the original order usually, and sometimes I'd need to have the custom sort!

Note3: Boost is not available and compiler is C++14 capable.

dictionary sorting c++
1 Answers

Both std::map and std::set use the same strict weak ordering for ordering its contents.

You can take advantage of this. You know that if you iterate over the map you will get the keys in the same order as they are in the set, therefore all it takes is a little bit of clever logic, something like:

auto map_iter=myMap.begin();

for(auto p : myFavorites) {
    while (map_iter != myMap.end())
    {
         if (map_iter->first == p)
            cout << "#" << map_iter->first << "=" << map_iter->second << endl;
         if (map_iter->first > p)
              break;
         ++map_iter;
     }
}

It may still make sense to use find() in some edge cases, specifically when myFavorites is significantly smaller than myMap, in which case a few calls to find() might be faster than iterating over (most of) the entire map.

user_39433120
Related