C++ STL优先级队列自定义比较器与结构体重载运算符疑问

Hey there! Let's figure out why your priority_queue breaks when you remove the overloaded operator from your struct. This is a common pitfall with STL's priority queues, so let's break it down step by step.

First, a Quick Recap of priority_queue's Template Parameters #

The priority_queue in C++ has three template parameters:

template <class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue;

• T is your custom object type.
• Container is the underlying storage (default is vector<T>).
• Compare is the functor that defines the priority order (default is less<T>).

What the Default less<T> Does #

When you don't specify a custom Compare type, priority_queue uses less<T>, which relies on the operator< being defined for your T type. That's why your program works when you have the overloaded operator< in your struct—it's what the default comparator uses to order elements.

Why Your Custom Comparator Might Still Require the Overloaded Operator #

If you've defined a mycomparison class but removing the struct's operator< breaks the program, one of two things is happening:

1. You Didn't Properly Specify the Custom Comparator in the priority_queue Declaration #

If your priority_queue is declared like this (without the third template parameter):

priority_queue<MyObject> pq;

It's still using the default less<MyObject> comparator, which needs MyObject::operator< to exist. Even if you have a mycomparison class defined, the queue won't use it unless you explicitly tell it to:

// Correct declaration with custom comparator
priority_queue<MyObject, vector<MyObject>, mycomparison> pq;

2. Your Custom Comparator Uses operator< Internally #

Check the operator() method in your mycomparison class. If it looks like this:

struct mycomparison {
    bool operator()(const MyObject& a, const MyObject& b) const {
        // This calls MyObject::operator<, so it needs to exist!
        return a < b;
    }
};

Then even though you're using a custom comparator, it's still relying on the overloaded operator< from your struct. To fix this, rewrite the comparator to directly compare the cost member without using operator<:

struct mycomparison {
    bool operator()(const MyObject& a, const MyObject& b) const {
        // Prioritize objects with lower cost
        // Return true if a should come after b (lower priority)
        return a.cost > b.cost;
    }
};

This way, the comparator doesn't depend on any overloaded operators in your struct.

Working Example Without Struct Operator Overload #

Here's a complete, working snippet that uses only the custom comparator (no operator< in the struct):

#include <iostream>
#include <queue>
#include <vector>

struct MyObject {
    int cost;
    std::string name;
    // No operator< overloaded here!
};

struct mycomparison {
    bool operator()(const MyObject& a, const MyObject& b) const {
        // Lower cost = higher priority
        return a.cost > b.cost;
    }
};

int main() {
    std::priority_queue<MyObject, std::vector<MyObject>, mycomparison> pq;

    pq.push({5, "Object A"});
    pq.push({2, "Object B"});
    pq.push({7, "Object C"});

    while (!pq.empty()) {
        auto obj = pq.top();
        pq.pop();
        std::cout << "Name: " << obj.name << ", Cost: " << obj.cost << "\n";
    }
    // Output will be Object B (cost 2), Object A (cost5), Object C (cost7)
    return 0;
}

Key Takeaways #

• If you use the default priority_queue (no custom comparator), you must define operator< for your custom object.
• If you use a custom comparator, make sure to:
  1. Explicitly specify it as the third template parameter in the priority_queue declaration.
  2. Write the comparator's operator() to directly compare the relevant members (like cost) without relying on the struct's overloaded operators.

内容的提问来源于stack exchange，提问作者user478905