c++ - Bool 运算符重载不起作用

Question

代码示例:

#include <queue>
#include <vector>

using namespace std;

class Cell
{
public:
    int totalCost = 0;
};

class Helper
{
public:
    struct Comparator
    {
        bool operator()(Cell const *lfs, Cell const *rhs)
        {
            return lfs->totalCost < rhs->totalCost;
        }
    };
};

priority_queue<Cell*, vector<Cell*>, Helper::Comparator> path;

void function(Cell* cell)
    {
        cell->totalCost += rand() % 1000;
        path.push(cell);
    }

    int main()
    {
        Helper help;

        Cell first;
        Cell second;
        Cell third;
        Cell fourth;
        Cell fifth;

        Cell* firstPtr = &first;
        Cell* secondPtr = &second;
        Cell* thirdPtr = &third;
        Cell* fourthPtr = &fourth;
        Cell* fifthPtr = &fifth;



        function(firstPtr);
        function(secondPtr);
        function(thirdPtr);
        function(fourthPtr);
        function(fifthPtr);

        return 0;
    }

调试器片段:

我正在创建一个优先级队列，我尝试过重载 () 运算符，但由于某种原因它根本不起作用(如在调试器中所见)。

我觉得指针有问题，但我无法弄清楚到底是什么。

Answer 1

我没有发现您的代码有问题。除了您忘记初始化随机数生成器。

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

using namespace std;

class Cell
{
public:
    int totalCost = 0;
};

class Helper
{
public:
    struct Comparator
    {
        bool operator()(Cell const *lfs, Cell const *rhs)
        {
            return lfs->totalCost < rhs->totalCost;
        }
    };
};

priority_queue<Cell*, vector<Cell*>, Helper::Comparator> path;

void function(Cell* cell)
{
    cell->totalCost += rand() % 1000;
    path.push(cell);
}

int main()
{
    srand(time(0));
    Helper help;

    Cell first;
    Cell second;
    Cell third;
    Cell fourth;
    Cell fifth;

    Cell* firstPtr = &first;
    Cell* secondPtr = &second;
    Cell* thirdPtr = &third;
    Cell* fourthPtr = &fourth;
    Cell* fifthPtr = &fifth;

    function(firstPtr);
    function(secondPtr);
    function(thirdPtr);
    function(fourthPtr);
    function(fifthPtr);

for(;path.size();path.pop()) std::cout << path.top()->totalCost <<"\n";

    return 0;
}

输出:

luk32@debianvm:~/projects/tests$ ./a.out 
896
725
370
200
130
luk32@debianvm:~/projects/tests$ ./a.out 
699
672
285
250
208
luk32@debianvm:~/projects/tests$ ./a.out 
772
582
388
223
153
luk32@debianvm:~/projects/tests$ ./a.out 
869
807
670
642
182

这是预期的。也许您会感到困惑，因为它不会对项目进行排序。但它不必。只有第一个(顶部)必须比所有其他的都大(根据比较器)。其余元素不遵循 n > n+1。因为优先级队列是在堆上实现的。这样可以更快地运行。因为插入元素需要 O(log n) 时间。保持所有元素排序需要 O(n) 插入操作。