初始化STL优先级队列

Question

我仍然对STL中的优先级队列感到困惑.这是我想实现的目标,比如说:我有一个名为Record的结构,它包含一个字符串字和一个int计数器.例如:我有很多这些记录(在示例程序中,只有5个),现在我想保留前N个记录(在样本中,3).

我现在知道我可以在Record中重载operator <,并将所有记录放在一个向量中,然后初始化priority_queue,如:

priority_queue< Record, vector<Record>, less<Record> > myQ (myVec.begin(),myVec.end());

但是,正如我所理解的那样,控制矢量myVec的大小并不容易,因为它没有按我的意愿排序.

我真的不明白为什么以下不能工作:

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 <overload工作,第二个(注释掉一个)将无法工作并且有一长串编译器,我更喜欢错误.

friend bool operator< (const Record& lhs, const Record& rhs)
{
    return lhs.count>rhs.count;
}

/*
bool operator<(const Record& rRecord)
{
    return this->count>rRecord.count;
}
    */

Answer 1

std::priority_queue不能神奇地知道如何对元素进行排序.你必须告诉它如何这样做.这样做的方法是给出priority_queue一个functor类型,当用两个对象调用时,返回第一个参数是否"小于"第二个,但是你想要定义它.这个仿函数是一个模板参数priority_queue.

默认参数是std::less<type>,要求type(您在队列中放置的内容)过载operator<.如果没有,那么您要么必须提供一个,要么必须提供适当的比较仿函数.

例如:

struct Comparator
{
  bool operator()(const Record& lhs, const Record& rhs)
  {
    return lhs.count>rhs.count;
  }
};

std::priority_queue<Record, std::vector<Record>, Comparator> myQ;

仅仅Record因为过载而无效的原因是因为您没有告诉priority_queue它是比较.此外,用于比较的类型需要是默认构造的,以便priority_queue可以随意创建和销毁对象.

虽然说实话,我不知道你为什么不把它们粘在一起,std::set如果你想对它们进行分类.或者只是运行std::sort的std::vector项目.