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

原文 标签 c++ sorting dictionary

我有一个相当简单的问题:我有一个 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;
    }
}
真正困扰我的是最后一个循环,每次迭代都会调用 findset .
所需的输出是:
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)相同的接口(interface)。
我正在寻找一种比我原来的“蛮力”更有效的方法来解决这个问题。
请注意: map 不得“重新排序”!我只需要使用自定义排序来查询(检索)它的项目!
注2:我知道 map 可以有一个比较运算符。但我通常需要原始订单,有时我需要自定义排序!
注意 3:Boost 不可用,编译器支持 C++14。

最佳答案

两个std::mapstd::set使用相同的严格弱排序对其内容进行排序。
您可以利用这一点。您知道,如果您遍历 map ,您将按照与它们在集合中的顺序相同的顺序获取键,因此只需要一点聪明的逻辑,例如:

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 更快。

关于c++ - 根据特定排序有效地从 map 中获取项目,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/67863989/

相关文章:

c++ - C++如何定义其他开发人员需要调用的常量函数顺序

c++ - 在C++中查找最大,最小和模式

c++ - boost::ptr_list 中的前向声明类

c++ - 调试 lambda 内存损坏 ||自动监视 GDB 中的对象指针

c# - 可以使用 IComparer 在填充列表时对其进行散列吗?

c - C中不区分大小写的排序

json - 将 map[string]string 编码到 json 是否会返回错误?

arrays - Fortran 选择排序子例程、错误、数组无法读取

python - 在字典中查找特定值的平均值

python - 将Pandas Dataframe转换为嵌套字典