为什么为我的对象 class 编译标准优先级队列失败？

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;
        }
    }
}

我想知道如何消除这个错误，我对队列或对不是很熟悉，但我认为我对它们的理解足以满足我需要做的事情。它试图与该运算符进行比较的是什么？我不需要一个比对参数中的 Coord 更小的 int。

欢迎提出任何建议，但不要太复杂，因为我仍然是 C++ 的初学者，可能无法理解它们

Answer 1

您需要为您的Coordclass定义一个比较操作。将 bool operator<(const Coord &rhs) const; 添加到您的 class 中，这将决定两个坐标（*this 或 rhs）中的哪一个先出现。

Answer 2

这对你来说似乎完全合乎逻辑，但编译器不知道 order 你对 "priority" 的概念定义对于你称为 [=20= 的东西意味着什么].您的 object 存储在您的 queue 中，如下所示：

std::pair<int, Coord>

并了解 std::priority_queue 如何比较元素是有必要的。

适配器 std::priority_queue defaults to using std::less for the item comparator to determine order. As you have now-discovered, that comparator does little more than manufacture a simple a < b construct to compare objects for order, and if the object class (or its bases) provide this, great; if not, you need to do so. as it turns out, std::pair does provide an operator <，它基本上在 first 和 second 之间建立了严格的弱排序。对于两对 objects 它基本上是这样做的：

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

为什么那个很重要？请注意 second 在最后一个表达式中的用法。这很重要，因为上面的 second 是你的类型 Coord，因此， operator < 被应用到 Coord 并且因为没有这样的运算符，compiler = not-happy。

作为 side-note，您已经注意到 对 std::pair<int, std::pair<int,int>> 开箱即用 因为如前所述，std::pair 有运算符 <overload, and in that case two different instantiations ofoperator <` 出现。

要解决这个问题，您必须为您的类型提供这样一个 operator。基本上只有两种方法可以做到这一点：成员函数或 free-function 中的任何一个都为 Coord 定义了 operator < 重载。通常实现为成员函数，但也可能实现为 free-function，这实质上提供了 std::less 正在寻找的运算符。这是提供订单的最常见机制（恕我直言，最容易理解）：

// 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)
}

一般比较器指南

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

std::map
std::set
std::sort
std::priority_queue
许多其他...

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

为您的 Type 类型的实例提供一个 operator <（简单，示例如前）。这允许继续默认 std::less 完成它的工作，即触发您提供的 operator <。
为 container/algorithm 提供一个比较器来为您执行比较（也很简单）。本质上，您正在编写您在声明或调用它们时为容器、适配器或算法指定的 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;

当您需要对不同容器的相同 object class 实施不同排序时，这会很方便。例如，您可以有一个容器订购 small-to-large，另一个容器订购 large-to-small。不同的比较器允许您这样做。例如，您可以使用比较器创建 std::set of Coord objects

std::set<Coord, CoordLess> myset;

或通过执行此操作对 Coord object 的向量 vec 进行排序：

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

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

提供std::less专业

这不容易理解，很少有人这样做，但同样容易实施。由于 std::less 是默认比较器，只要类型是自定义类型（不是本地语言类型或库类型），您就可以为 Coord 提供 std::less 特化。这意味着如果事先提供了下面的定义，通常使用 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>，并且由于我们自己专门化了它，所以它使用 我们的。这是在许多地方更改默认行为的便捷、包罗万象的方法，但能力越大责任越大，所以要小心，永远不会 这样做这与原生或 library-provided 类型。

希望这能给您一些解决错误的不同方法的想法。

为什么为我的对象 class 编译标准优先级队列失败？

Why does compiling a standard priority queue for my object class fail?

c++

priority-queue

operator-keyword

std-pair