c++ - 为什么为我的对象类编译标准优先级队列失败？

Question

我正在尝试创建一个以一对为参数的std::priority_queue。该对具有参数int和Coord。 Coord是一个结构，仅包含两个用于数组坐标的整数(x和y)。

我要对整个程序进行的操作是在数组网格上实现Dijkstra算法(而不是使用图形)，这已经让我头疼，因为我不确定自己是否以正确的方式进行操作。至少我正在尝试和学习。但是无论如何，我现在遇到的问题是，当我编译时，我得到了错误

"C2678 binary'<' no operator found which takes a left-hand operand of type 'const Coord' (or there is no acceptable conversion)"

这是我的一些代码的样子:

struct Coord
{
    int x, y;
};

这是基本的 Coord结构。然后是创建队列的函数:

void dijkstraFirstPhase(Coord start, Coord end, int(&aGrid)[HEIGHT][WIDTH], unordered_map<pair<int, int>, bool, pair_hash>& theMap)
{
    //priority_queue< pair<int, pair<int, int>> > pq;
    priority_queue<pair<int, Coord>> pq; //this is the line where the error comes from

    //initializing the starting point
    int distanceFromStart = 0;
    aGrid[start.x][start.y] = distanceFromStart;
    pq.push({ distanceFromStart, start });

    while (!pq.empty())
    {
        Coord u = pq.top().second;
        theMap[make_pair(u.x, u.y)] = true;
        pq.pop();

        writeDistances(u.x, u.y, aGrid, theMap, pq);
        displayGrid(aGrid);

        if (theMap[make_pair(end.x, end.y)] = true)
        {
            cout << "The end has been found" << endl;
            cout << "Distance written into its cell: " << aGrid[end.x][end.y] << endl;
            break;
        }
    }
}

我想知道如何摆脱这个错误，我对队列或队列对不是很熟悉，但是我认为我对队列或队列的理解足以满足我的需要。与该运营商进行比较的目的是什么？我不需要将int小于对参数中的 Coord。

欢迎任何建议，但不要复杂，因为我还是C++的初学者，可能不理解它们

Answer 1

对您来说，这似乎完全合乎逻辑，但是编译器不知道您对“priority”的概念性定义对于Coord而言意味着什么顺序。存储在队列中的对象如下所示:

std::pair<int, Coord>

并且必须了解 std::priority_queue如何比较元素。

适配器 std::priority_queue 缺省将 std::less 用于项目比较器以确定顺序。正如您现在所发现的那样，该比较器所做的只是创建一个简单的 a < b构造以比较对象的顺序而已，并且如果对象类(或其基类)提供了此功能，那就太好了；如果不是，则需要这样做。事实证明， std::pair does provide an operator < 基本上在 first和 second之间建立了严格的弱排序。对于两个对对象，它基本上是这样做的:

return lhs.first < rhs.first || (!(rhs.first < lhs.first) && lhs.second < rhs.second);

为什么这么重要？注意最后一个表达式中的 second用法。这很重要，因为上面的 second属于您的类型 Coord，因此， operator <被应用于 Coord，并且由于没有这样的运算符，所以编译器=不满意。

附带说明一下，您已经注意到 std::pair<int, std::pair<int,int>>可以立即使用，因为如前所述， std::pair具有运算符< overload, and in that case two different instantiations of运算符<`。

为了解决这个问题，您必须为您的类型提供一个 operator。基本上只有两种方法可以执行此操作:成员函数或自由函数均定义 operator <的 Coord重载。通常实现为成员函数，但也可能实现为自由函数，这从根本上提供了运算符 std::less寻找。这是提供命令的最常见机制(并且imho最容易理解):

// member function
struct Coord
{
    int x, y;

    bool operator <(const Coord& rhs)
    {
        return x < rhs.x || (!(rhs.x < x) && y < rhs.y)
    }
};

要么

// free function
bool operator <(const Coord& lhs, const Coord& rhs)
{
    return lhs.x < rhs.x || (!(rhs.x < lhs.x) && lhs.y < rhs.y)
}

一般比较器准则

除了通过重载 std::less<>使 operator <对给定类型满意之外，许多容器，适配器和算法还允许您提供自己的自定义比较器类型。例如:

std::map

std::set

std::sort

std::priority_queue

许多其他人...

为此，有几种可能的方法可以做到这一点。示例包括:

为您的operator <类型的实例提供一个Type(简单，前面显示的示例)。这允许继续使用默认的std::less来执行您提供的operator <的工作。

为容器/算法提供一个比较器，为您执行比较(也很容易)。本质上，您是在声明或调用它们时为容器，适配器或算法指定的std::less的替代代码。

提供std::less<Coord>的模板特化(适度简单，但很少做，对初学者来说不太直观)。它将std::less替换为通常在任何地方使用的特化名称。

后两个示例如下所示。我们假设我们只是使用您的 Coord而不是您的 std::pair<int, Coord>，前面已经解释了

提供自定义比较器

您不必使用 std::less进行订购。您也可以提供自己的函子来完成相同的工作。 std::priority_queue的第三个模板参数是用于提供此功能的参数:

struct CoordLess
{
    bool operator()(Coord const& lhs, Coord const& rhs) const
    {
        return lhs.x < rhs.x || (!(rhs.x < lhs.x) && lhs.y < rhs.y)
    }
};

std::priority_queue<Coord, std::vector<Coord>, CoordLess> myqueue;

当您需要在同一对象类上为不同的容器实现不同的排序时，这很方便。例如，您可能有一个从小到大订购的容器，另一个从大到小的订购容器。不同的比较器允许您执行此操作。例如，您可以使用比较器创建 std::set对象的 Coord

std::set<Coord, CoordLess> myset;

或通过执行以下操作对 vec对象的 vector Coord进行排序:

std::sort(vec.begin(), vec.end(), CoordLess());

请注意，在两种情况下，我们都在声明或调用时指定了自定义比较器。

提供std::less特化

这不是那么容易理解，很少做，但是一样容易实现。由于 std::less是默认的比较器，因此，只要类型是自定义类型(不是本地语言类型或库类型)，就可以为 std::less提供 Coord专门化。这意味着，如果事先提供了以下定义，则通常使用 std::less<Coord>进行排序的所有内容都将隐式获得此信息。

namespace std
{
    template<>
    struct less<Coord>
    {
        bool operator ()(Coord const& lhs, Coord const& rhs) const
        {
            return lhs.x < rhs.x || (!(rhs.x < lhs.x) && lhs.y < rhs.y)
        }
    };
}

使用提供的参数(通常在同一 header 中自定义类型之后)，您可以简单地使用默认模板参数，而在我们必须指定它们之前。例如，现在我们可以这样声明一个 std::set:

std::set<Coord> myset;

或执行这样的排序:

std::sort(vec.begin(), vec.end());

两者都默认使用 std::less<Coord>，并且由于我们自己专门设计，因此使用了我们的。这是在许多地方更改默认行为的便捷，包围式方法，但是强大的功能带来了巨大的责任，因此请当心，切勿对本机或库提供的类型执行此操作。

希望能给您一些解决错误的不同思路。