c++ - 根据特定排序有效地从 map 中获取项目

Question

我有一个相当简单的问题:我有一个 std::map<int,T>另一个std::set<int> (也可以是std::vector或类似的)。

在 map 中我存储项目，在另一个容器中我存储( map 的)收藏夹。

在某些时候，我需要从 map 中检索(所有)项目，但从其他容器定义的收藏夹开始。

这是我的最小重现，我解决它非常丑陋，而且无效:

#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;
    }
}

真正困扰我的是最后一个循环，每次迭代都会调用 find关于set .

所需的输出是:

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

以下是 Coliru 中的上述来源，以使其更容易:https://coliru.stacked-crooked.com/a/731fa76d90bfab00

map 和 set 都可能会更改，但替换后需要实现与原始版本相同的接口(interface)。

我正在寻找一种比我原来的“暴力”方法更有效的方法来解决这个问题。

请注意: map 不得“重新排序”!我只需要使用自定义排序查询(检索)其项目!

注2:我知道map可以有一个比较运算符。但我通常需要原始订单，有时我需要自定义排序!

注 3:Boost 不可用，编译器支持 C++14。

Answer 1

std::map 和 std::set 都使用相同的严格弱排序来排序其内容。

您可以利用这一点。您知道，如果您迭代映射，您将按照与集合中的顺序相同的顺序获得键，因此所需要的只是一点聪明的逻辑，例如:

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;
     }
}

在某些边缘情况下使用 find() 可能仍然有意义，特别是当 myFavorites 明显小于 myMap 时，其中在这种情况下，对 find() 的几次调用可能比迭代(大部分)整个 map 更快。