C ++优先级队列按特定方法按升序排列以获取指向对象的唯一指针

Question

我有一个名为 Foo 的 class，每个 Foo 对象都有一个名为 yVal 的方法。我想要的是 Foo 个对象的优先级队列，按 Foo.yVal()

的升序排列

我将 Foo 中的 operator> 和 operator< 重载为：

   bool operator> (const Foo &f){
        return yVal() > f.yVal();
   }

   bool operator< (const Foo &f){
        return yVal() < f.yVal();
   }

所以我有以下代码：

priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, greater<unique_ptr<Foo>> > Queue;

但这并不是按 Foo.yVal() 的升序对优先级队列进行排序。相反，它只是以某种未知的随机顺序对它们进行排序。我在 operator> 和 operator< 中放置了一个 cout 语句，但它们甚至都没有被调用。所以我尝试用 lambda 代替：

auto cmp = [](Foo left, Foo right) {return left.xVal() > right.xVal();};
priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, decltype(cmp) > Queue(cmp);

但这给了我"non-static data member declared auto"错误的错误。

理想情况下，我希望它能与 greater<> 和运算符重载一起使用。如果没有，有人可以告诉我我在 lambda 上做错了什么（对 lambda 不太熟悉，如果可能的话想避免使用它们）。

我也尝试过使用仿函数，但同样，仿函数上的 auto 给了我同样的 "non-static data member declared auto" 错误。

Answer 1

你得到了未知的随机顺序因为当你有greater<T> 执行以下操作

// pseudocode
cmp(T lhs, T rhs) {
  return lhs > rhs;
}

代码中的 T 是什么？ T是unique_ptr<Foo>，C++库里有operator>(unique_ptr<>,unique_ptr<>)吗？是的，它是 see here，这个运算符在比较时使用 unique_ptr::get 方法：

// Psuedocode when greater used:
cmp (unique_ptr<Foo>& lhs, unique_ptr<Foo>& rhs)
{
  lhs.get () > rhs.get()
}

unique_ptr::get return 是什么意思？它 return 指向 Foo 的指针，所以你正在比较指向 Foo 个实例的指针。结果不可预测。代码编译并执行，但它没有按照您的预期执行。

如何修复您的 lambda：

您的队列中存储了哪些对象？ Foo 还是 unique_ptr<Foo>？您正在存储 unique_ptr<Foo>，因此您的 lambda 参数应该声明为这种类型。

auto cmp = [](const unique_ptr<Foo>& left, const unique_ptr<Foo>& right) 
{                   ^^^^^^^^^^^^^^^^
    return left->yVal() > right->yVal();
};             ^^
priority_queue<unique_ptr<Foo>, vector<unique_ptr<Foo>>, decltype(cmp) > Queue(cmp);

因为无法复制 unique_ptr 的实例，所以您必须通过引用传递它们。还可以使用 -> 运算符访问 yVal 方法。

编辑：带有函数对象的版本。

 // comparator as function object with overloaded operator()
 struct Cmp {
   bool operator()(const std::unique_ptr<Foo>& left, const std::unique_ptr<Foo>& right) const {
     return left->xVal() > right->xVal();
   }
 };

class YourClass {
public:
   std::priority_queue<std::unique_ptr<Foo>, std::vector<std::unique_ptr<Foo>>, Cmp> Queue;

C ++优先级队列按特定方法按升序排列以获取指向对象的唯一指针

C++ priority queue in ascending order by specific method for unique pointers to objects

c++

priority-queue

unique-ptr