初始化为STL优先级队列 [英] initialization for STL priority queue
问题描述
我仍然困惑在STL的优先级队列。这里是我想实现的目标，说：我有一个结构叫Record，它包含一个字符串和一个int计数器。例如：我有很多这些记录（在示例程序中，只有5），现在我想保持前N个记录（在示例中，3）。
I'm still confused about priority queue in STL. Here is the objective I wanna achieve, say: I have a structure called Record, which contains a string word and a int counter. For example: I have many records of these (in the sample program, only 5), now I want to keep top N records(in sample, 3).
我知道现在我可以重载operator<在记录中，并将所有记录放在向量中，然后初始化priority_queue，如：
I know now that I could overload operator < in Record, and put all records in a vector, and then initialize the priority_queue like:
priority_queue< Record, vector<Record>, less<Record> > myQ (myVec.begin(),myVec.end());
然而，据我所知，控制矢量myVec的大小并不容易，因为它没有排序我想。
However, as I understood, it's not easy to control the size of vector myVec because it's not sorted as I wanted.
我真的不明白为什么以下无法工作：
I really don't understand why the following can not work:
struct Record
{
string word;
int count;
Record(string _word, int _count): word(_word), count(_count) { };
/*
bool operator<(const Record& rr)
{
return this->count>rr.count;
}
*/
bool operator() (const Record& lhs, const Record& rhs)
{
return lhs.count>rhs.count;
}
};
void test_minHeap()
{
priority_queue<Record> myQ;
Record arr_rd[] = {Record("William", 8),
Record("Helen", 4),
Record("Peter", 81),
Record("Jack", 33),
Record("Jeff", 64)};
for(int i = 0; i < 5; i++)
{
if(myQ.size() < 3)
{
myQ.push(arr_rd[i]);
}
else
{
if(myQ.top().count > arr_rd[i].count)
continue;
else
{
myQ.pop();
myQ.push(arr_rd[i]);
}
}
}
while(!myQ.empty())
{
cout << myQ.top().word << "--" << myQ.top().count << endl;
myQ.pop();
}
}
编辑：
感谢您的输入，现在我得到它工作。然而，我喜欢如果有人可以解释为什么第一版本的operator<重载工作，第二个（注释掉一个）将不工作，并有一长串编译器错误。
Thanks for your input, now I got it working.However, I prefer if someone could explain why the first version of operator< overload works, the second one (commented out one) won't work and has a long list of compiler errors.
friend bool operator< (const Record& lhs, const Record& rhs)
{
return lhs.count>rhs.count;
}
/*
bool operator<(const Record& rRecord)
{
return this->count>rRecord.count;
}
*/
推荐答案
std :: priority_queue 不可能神奇地知道如何排序元素。你必须告诉它如何这样做。这样做的方法是给 priority_queue 一个函子类型，当用两个对象调用时，返回第一个参数是否小于第二个参数，但是你想定义。此函数是 priority_queue 的模板参数。
std::priority_queue cannot magically know how to sort the elements. You must tell it how to do so. The way to do that is to give priority_queue a functor type which, when called with two objects, returns whether the first argument is "less than" the second, however you want to define that. This functor is a template parameter to the priority_queue.
默认参数为 std： ：less< type> ，这要求类型（你放入队列中）有一个重载的 ; 。如果没有，那么你必须提供一个比较函子。
The default parameter is std::less<type>, which requires that type (what you're putting in the queue) has an overloaded operator<. If it doesn't, then you either have to provide one or you have to provide a proper comparison functor.
例如：
struct Comparator
{
bool operator()(const Record& lhs, const Record& rhs)
{
return lhs.count>rhs.count;
}
};
std::priority_queue<Record, std::vector<Record>, Comparator> myQ;
code>是因为你没有告诉 priority_queue 这是比较。此外，用于比较的类型需要是默认构造的，因此 priority_queue 可以随意创建和销毁对象。
The reason that doesn't work with just an overload on Record is because you didn't tell the priority_queue that it was the comparison. Also, the type used for comparison needs to be default constructable, so that the priority_queue can create and destroy the objects at will.
虽然说实话，我不知道你为什么不把它们放在 std :: set 如果你想排序他们。或者只需在项目的 std :: vector 上运行 std :: sort 。
Though to be honest, I don't know why you don't just stick them in a std::set if you want to sort them. Or just run std::sort on the std::vector of items.
这篇关于初始化为STL优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
