STL优先队列的初始化

Question

STL优先队列的初始化

c++stlvectorinitializationpriority-queue

5

我对STL中的优先队列仍然感到困惑。这是我想要实现的目标：我有一个名为Record的结构体，其中包含一个字符串word和一个整型counter。比如说：我有很多这样的记录（在示例程序中只有5个），现在我想要保留前N个记录（在示例中为3个）。

我现在知道可以在Record中重载运算符<，将所有记录放入一个向量中，然后像这样初始化优先队列：

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<重载可以工作，而第二个版本（被注释掉的那个）不能正常工作，并输出了一堆编译错误。

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

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

- WilliamLou

你意识到你没有为 Record 重载 operator< - 它被注释掉了。 - Björn Pollex

因为我不想按照我的帖子中的第一种方式去做。我会重载运算符()来代替。 - WilliamLou

"operator()" 是函数调用运算符，你对它进行重载是毫无意义的。如果你想对对象进行排序，请重载相应的比较运算符。" - Björn Pollex

这篇我在另一个问题中的回答基本上就是你需要的。链接：https://dev59.com/n1zUa4cB1Zd3GeqP2FOO#7803650 - Björn Pollex

如果你想重载operator()而不是operator<，那么你可能需要编写自己的比较函数对象。默认的函数对象less期望使用operator<，所以你需要提供它。 - Darcy Rayner

类似的帖子在这里。 - Rick Smith

2个回答

4

你的代码确实可以工作，只需要做两个小改动：

取消注释 Record::operator<() 的定义，因为优先队列的默认比较器需要用到它。
将声明改为 bool operator<(const Record &) const（注意额外的 const），因为优先队列需要使用指向常量对象的引用进行比较。

或者，你也可以将其声明为一个自由函数，放在类定义之外：

bool operator<(const Record &l, const Record &r) {return l.count > r.count;}

或者定义您自己的函数对象，并将其作为适当的模板参数提供：

struct CompareRecords
{
    bool operator()(const Record &l, const Record &r) {return l.count > r.count;}
};

typedef priority_queue<Record, vector<Record>, CompareRecords> RecordQueue;

- Mike Seymour

如果您尝试使用第二个，您将会得到一个未知类型名“Record”的错误。 - Yunfei Chen

这个函数的参数太多了。 - Yunfei Chen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicol Bolas · Accepted Answer

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 它是比较对象。此外，用于比较的类型需要默认可构造，这样 priority_queue 就可以随意创建和销毁对象。

但说实话，如果您想要排序，我不知道为什么不直接将它们放入 std::set 中。或者只需对项目的 std::vector 运行 std::sort 即可。