一组自定义类对象及其<操作员 [英] Set of custom class objects and their < operator

问题描述

我正在尝试实现A* algorithm(在Qt中具有可视化).我有这种方法:

I am trying to implement A* algorithm (with visualization in Qt). I've got this method:

result_path astar_algorithm::calculate(mapview* m_view)
{
    map_view = m_view;
    auto closed_set = std::vector<std::shared_ptr<node>>();
    auto start_node = std::make_shared<node>(_start);
    auto open_set = std::vector<std::shared_ptr<node>>{start_node};
    std::map<node, node> came_from;

    std::shared_ptr<node> current;
    while (!open_set.empty())
    {
        current = *std::min_element(open_set.begin(), open_set.end());
        if (*current == _end)
        {
            // TODO: Reconstruct a result path!!!
            break;
        }
        open_set.erase(std::find(open_set.begin(), open_set.end(), current));
        closed_set.push_back(current);
        auto neighbors = get_neighbors(*current);
        for (auto& neighbor : neighbors)
        {
            if (std::find_if(closed_set.begin(), closed_set.end(),
                             [&](std::shared_ptr<node> const& p) { return *p == neighbor; }) !=
                closed_set.end())
                continue;

            auto tentative_g_score = current->G + 1;

            if (std::find_if(open_set.begin(), open_set.end(), [&](std::shared_ptr<node> const& p) {
                    return *p == neighbor;
                }) == open_set.end())
            {
                neighbor.G = tentative_g_score;
                neighbor.H = heuristic_cost_estimate(neighbor.pos, _end);
                neighbor.parent = current;
                open_set.push_back(std::make_shared<node>(neighbor));
            }
            else if (tentative_g_score < neighbor.G)
            {
                neighbor.parent = current;
                neighbor.G = tentative_g_score;
            }
        }
    }
    auto result = result_path();
    while (*current != *start_node)
    {
        result.path.push_back(current->pos);
        current = current->parent;
    }
    result.path.push_back(start_node.pos);
    std::reverse(result.path.begin(), result.path.end());
    return result;
}

它可以工作，但是我有一些问题:

It works, but I have a few problems:

if (std::find_if(closed_set.begin(), closed_set.end(),
                             [&](std::shared_ptr<node> const& p) { return *p == neighbor; }) !=
                closed_set.end())
                continue;

此行检查std::vector中是否存在node，如果存在，它将继续循环(然后有第二行与此类似，它仅检查向量中是否实际上不存在节点) .我想更好的方法是将这些节点存储在向量中，然后搜索和进一步添加会更容易(因为我只需要检查insert是否成功).

This line checks if a node is present in an std::vector and if so, it continues the loop (then there is a second line similar to this, it just checks if node is not actually present in the vector). I guess the better way would be to store those nodes in a vector and then searching and further adding would be easier (cuz I just have to check if the insert succeeded).

问题是，要使这项工作有效，我必须实现<运算符.所以我做到了.我还制作了==和!=:

The problem is, afaik, to make this work I have to implement < operator. And so I did. I also made == and !=:

class node
{
public:
    node() {}
    node(const QPoint& p) : pos(p) {}
    bool operator == (const node& o ) const { return pos == o.pos; }
    bool operator == (const QPoint& o ) const { return pos == o; }
    bool operator != (const node& o) const {return pos != o.pos; }
    bool operator <(const node& o ) const { return G + H < o.G + o.H; }
    QPoint pos;
    std::shared_ptr<node> parent;
    int G = 0;
    int H = 0;
};

它非常适合早期搜索std::min_element(它搜索具有最低F值(F=G+H)的节点)，它使用<运算符.但是后来我尝试使用一个集合，所以设置了方法开头的那两个向量，当我只想insert或什至检查一个节点是否已经在集合中并且然后insert时，我遇到了问题.这些nodes的许多值将具有相同的G+H值，因为我使用的迷宫很简单(即完全没有地形的迷宫).我在调试器下进行了检查，并且具有唯一.pos值(QPoint)的节点没有被添加到集合中，就像它们不是唯一的一样(但是如果该节点的G+H值与节点中的任何节点都不相同)设置，则将其添加).对于矢量，它们当然可以正常工作，因为没有进行检查，我在调试器下仔细检查了所有内容.

It works perfectly for the earlier search for std::min_element (it searches for a node with the lowest F value (F=G+H)), it uses < operator. But then I tried to use a set, so those two vectors at the beginning of the method were set and when I wanted to just insert or even check if a node is already in a set and then insert I had a problem. Many of those nodes will have the same G+H value, as the maze which I used was kind of simple (i.e. a maze completely without terrains). I checked it under the debugger and the nodes with unique .pos values (QPoint) were not added to the set just like they weren't unique (but if the node had a different G+H value than any node in the set, it would be added). For the vector the same nodes of course work, cuz there are no checks made, I checked everything carefully under the debugger.

我不知道我是否弄错了，但是我认为它会使用==或!=运算符，但是如以下答案所示:

I don't know if I am getting this wrong, but I thought it would use a == or != operators but as seen in this answer: link, it actually uses < operator, which in my case would not distinguish between two nodes (cuz the unique part of each node is its position in the grid (node represents a box in a grid, which can represent a maze or smth similar))

因此，是否有我做错的事情或实际上是对的，插入(检查元素是否唯一)或检查元素是否存在于集合中，所以使用了<运算符，我无法执行有什么事吗? (因为我想让我的<运算符与G+H进行比较，然后我想在搜索/插入时使用==运算符进行比较)

So, is there something I am doing wrong or am I actually getting this right, and the inserting (which checks if the element is unique) or checking if the element exists in a set uses < operator and I cannot do anything about it? (cuz I would like to have my < operator with comparing G+H and then I would like the searching/inserting to use the == operator to compare)

这是我编写的示例(我忘记了从命令行获得的Microsoft C ++编译器)

This is the example that I wrote (I forgot I have Microsoft C++ Compiler from the command line - cl.exe)

#include <algorithm>
#include <iostream>
#include <memory>
#include <set>

class Point
{
public:
    int _x, _y;
    Point() : _x(0), _y(0) {}
    Point(int x, int y) : _x(x), _y(y) {}
    bool operator==(const Point& p) const { return _x == p._x && _y == p._y; }
    bool operator!=(const Point& p) const { return _x != p._x && _y != p._y; }
};

class node
{
public:
    node() {}
    node(const Point& p) : pos(p) {}
    bool operator==(const node& o) const { return pos == o.pos; }
    bool operator==(const Point& o) const { return pos == o; }
    bool operator!=(const node& o) const { return pos != o.pos; }
    bool operator<(const node& o) const { return G + H < o.G + o.H; }
    Point pos;
    std::shared_ptr<node> parent;
    int G = 0;
    int H = 0;
};

int main()
{
    node n1(Point(0, 0));
    n1.G = 1;
    n1.H = 1;
    node n2(Point(1, 1));
    n2.G = 2;
    n2.H = 2;
    node n3(Point(2, 2));
    n3.G = 1;
    n3.H = 1;
    std::set<node> nodes;
    nodes.insert(n1);
    nodes.insert(n2);
    nodes.insert(n3);
    auto min = (*std::min_element(nodes.begin(), nodes.end())).pos;
    std::cout << min._x << " " << min._y << '\n';
    std::cout << nodes.size() << '\n';
}

>main.exe
0 0
2

std::min_element可以工作，但是对我来说，那些是3个唯一节点(不同的.pos值)，因此集合中应该有3个节点.这就是我要实现的目标

std::min_element works, but those are 3 unique nodes for me (differet .pos values) so there should be 3 nodes in the set. And that's what I want to achieve

推荐答案

我认为它将使用==或!=运算符

I thought it would use a == or != operators

否，std::set不使用运算符==和!=， std::set 仅使用一个函数，即比较函数(第二个模板参数，默认为std::less<T>).

No, std::set does not use operators == and !=, std::set uses just one function, the comparison function (the second template argument, which defaults to std::less<T>).

唯一性基于等价关系，该等价关系是通过两次应用相同的比较函数而得出的:!a<b && !b<a.

Uniqueness is based on the equivalence relation which is derived from applying the same comparison function twice: !a<b && !b<a.

似乎您并不是真的需要唯一性，在这种情况下，您可以使用 std::multiset .它将维持顺序，但不会强制唯一性.

It seems you don't really need uniqueness, in which case you can use std::multiset instead. It will maintain the order, but will not enforce uniqueness.

std::set<node> nodes;
. . .
auto min = (*std::min_element(nodes.begin(), nodes.end())).pos;

std::min_element始终为O(N).在set上使用它会破坏具有set的目的. 只需获取第一个元素，该元素将是最小的(根据比较函数).

std::min_element is always O(N). Using it on a set defeats the purpose of having a set. Just get the first element, which will be the smallest (according to the comparison function).

auto min = begin(nodes)->pos;

这篇关于一组自定义类对象及其<操作员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！