c++ - STL优先级队列的初始化

Question

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

我现在知道我可以在 Record 中重载运算符 <，并将所有记录放在一个 vector 中，然后像这样初始化 priority_queue:

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

但是，据我了解，控制 vector 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< 重载有效，而第二个版本(已注释掉)将不起作用并且有一长串编译器错误。

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一个仿函数类型，当用两个对象调用时，返回第一个参数是否“小于”第二个参数，但是你想定义它。这个仿函数是 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 上的项目。