具有自定义对象的 C++ 优先级队列

Question

我试图了解比较器如何为优先级队列工作，我做了几个测试：

测试 1：创建比较器 class，并使用 priority_queue<T, vector<T>, cmp>

它总是工作正常

测试 2：

struct test {
    int a = 0;
};

bool operator<(const test& lhs, const test& rhs) {
    return lhs.a < rhs.a;
}

int main() 
{
    priority_queue<test> pq;
}

这按预期工作。

测试 3：将测试 2 放入 class

class T{
    struct test {
        int a = 0;
    };

    bool operator<(const test& lhs, const test& rhs) {
        return lhs.a < rhs.a;
    }
};

编译错误：

'bool T::operator<(const T::test&, const T::test&)' must take exactly one argument

似乎编译器认为我正在为 class T 重载运算符 <。如果我真的需要嵌套 classes，还有其他方法可以实现吗？

测试 4：重载运算符<

struct test {
    int a = 0;
    bool operator<(const test& rhs) {
        return a < rhs.a;
    }
};

int main() 
{
    vector<test> v;
    sort(v.begin(), v.end());   // No error
    set<test> s;                // No error
    priority_queue<test> pq;    // Compiling error
}

只有priority_queue会报错：

'passing 'const test*' as 'this' argument discards qualifiers'

我不知道为什么这适用于排序和设置但不适用于优先级队列。

Answer 1

operator< 必须有两个参数，而当你使它成为 class T 的成员时，它隐含地得到 this 作为第三个参数，因此测试 3 中的错误：

class T {
  bool operator<(const test& lhs, const test& rhs) { // error
    return lhs.a < rhs.a;
  }
};

要解决此问题，请在嵌套的 test class:

中定义 operator<

class T {
public:
  struct test {
    int a = 0;
    friend bool operator<(const test& lhs, const test& rhs) {
      return lhs.a < rhs.a;
    }
  };
};

或在命名空间范围内。

在测试 4 中 operator< 应该是 const:

struct test {
  int a = 0;
  bool operator<(const test& rhs) const {
    return a < rhs.a;
  }
};

Answer 2

priority_queue 的比较器与任何其他比较器一样工作。应该可以参与表达式

if (compare(element1, element2))

默认实现缩减为

if (element1 < element 2) ....

你在 3 中所做的导致

if ( tObject.operator<(anotherTObject, yetAnotherTObject))

所以你的

bool T::operator<(const test& lhs, const test& rhs) {
    return lhs.a < rhs.a;
}

确实应该与对象本身进行比较，例如

bool T::operator<(const test& rhs) const {
    auto lhs = *this;
    return lhs.a < rhs.a;
}

最后一个 const 的作用类似于 vitauts 合理答案中第一个参数的 const。

具有自定义对象的 C++ 优先级队列

C++ Priority Queue with customized object

c++

priority-queue

comparator