优先级队列自定义比较

我试图用一个优先级队列将与下面的成员变量反对自定义：优先级队列自定义比较

class Jobs{ 
    string id; 
    string location; 
    int start; 
    int end; 
};

我会从文件中读取作业ID的HashMap和的重量工作。我将最终有一个

unordered_map<string, int> jobWeight;

举行此信息。我希望将作业列表最终以基于hashmap jobWeight的优先级推送到priority_queue中。最重要的工作应该是第一位的。

参考其他教程，我注意到你应该创建一个单独的类/结构并实现operator（）。然后你可以将这个比较类传递给priority_queue参数。但是，看起来priority_queue使用默认参数创建了这个比较器类的新实例？我怎么能够从这个比较类中引用我的jobWeight hashmap？

class CompareJobs{ 

    map<string, int> jobWeight; 

public: 

    CompareJobs(map<string, int> &jobWeight){ 
     jobWeight = jobWeight; 
    } 

    bool operator() (const Jobs &a, const Jobs &b){ 

     return jobWeight.find(a)->second < jobWeight.find(b)->second; 

    } 

};

来源

2016-09-18 David Yuan

你最初说'jobWeight'是一个'unordered_map'。你想把它转换成一个'map'并把它作为参数传递给你的比较器或者什么？ – WhiZTiM

这个图是否用于比这个比较器的其他任何东西？而且：它有多大？ –

@DanielJour当我插入到我的优先级队列中时，地图只应用于比较。这张地图会和工作数量一样大（每个工作都会有一定的重量），因此可能会超大。目前，最终目标是在每个时间范围内选择一份工作（工作从开始到结束不需要持续整个工作时间......所以选择工作的贪婪方法应该足够了，我只是使用priority_queue填满整个时间范围。 –

std::priority_queue的默认构造函数，其实需要的可选参数：

explicit priority_queue(const Compare& x = Compare(), Container&& = Container());

你会注意到，第一个参数是比较类的一个实例。

首先构造您的比较器类，使其以任何方便的方式引用您的哈希映射，然后使用比较器类构造您的优先级队列。

来源

2016-09-18 23:42:50

啊从来没有注意到这一点。非常感谢！ –

我该如何从这个比较器类中引用我的jobWeight散列表？

将对地图的引用添加到您的Compare类中！当然你需要确保这个引用保持有效。而且你不能使用一个简单的引用（因为这些引用是不可复制的，你的Compare类必须是可复制的），而是可以使用std::reference_wrapper。

using IDMap = std::unordered_map<std::string, int>; 

struct JobsByWeight { 
    std::reference_wrapper<IDMap const> weights_ref; 
    bool operator()(Job const & lhs, Job const & rhs) const { 
    auto const & weights = weights_ref.get(); 
    auto lhsmapping = weights.find(lhs.id); 
    auto rhsmapping = weights.find(rhs.id); 
    if (lhsmapping == weights.end() || rhsmapping == weights.end()) { 
     std::cerr << "damn it!" << std::endl; 
     std::exit(1); 
    } 
    return lhsmapping->second < rhsmapping->second; 
    } 
};

然后，只需通过你的比较类的对象你priority queue's constructor（过载（1）中的链接）：

std::priority_queue<Job, std::vector<Job>, JobsByWeight> queue{std::cref(that_id_map)};

既然没有构造，使您可以将您的比较级在队列中，您确实需要参考JobsByWeight。否则就会有你的地图副本（如你所说，这可能很大）。

注意：未经测试的代码。

来源

2016-09-18 23:53:10

感谢您的支持！从来没有意识到priority_queues带参数。 –

优先级队列自定义比较

回答

相关问题