Странное поведение элемента std :: min, когда класс обернут в shared_ptr - PullRequest
Новая
       20

Странное поведение элемента std :: min, когда класс обернут в shared_ptr

0 голосов
/ 08 февраля 2019

У меня был долгий сеанс отладки (6 часов и более).Я отлаживал свою реализацию алгоритма A *.

После проверки каждой возможности, после добавления регистрации, пошаговой отладки и т. Д., Я наконец нашел ответ.По сути, все сводится к одной строке, где я ищу минимальное значение в векторе.

Проверьте это: 

auto open_set = std::vector<std::shared_ptr<node>>{start_node};

std::shared_ptr<node> current;
while (!open_set.empty())
{
    current = *std::min_element(open_set.begin(), open_set.end());

Строка current = *std::min_element(open_set.begin(), open_set.end()); должна была найтисамый низкий node в векторе.Это моя node реализация: 

class node
{
public:
    node() : G(0), H(0) {}
    node(const QPoint& p) : pos(p), G(0), H(0) {}
    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;
    int H;
};

Итак, у меня есть operator<, необходимый для поиска min_element.Проблема в том, что после многократного просмотра моих журналов я обнаружил, что у меня есть node, то есть G = 8, H = 10 и узел G = 10, H = 10. Угадайте, что было выбрано как min_element -> Второй!Я понятия не имел, почему, и я был в ярости, поэтому я написал простую лямбду для сравнения узлов: 

current = *std::min_element(open_set.begin(), open_set.end(),
                            [&] (const std::shared_ptr<node>& lhs, const std::shared_ptr<node>& rhs)
                            {
                                return lhs->G + lhs->H < rhs->G + rhs->H;
                            });

И бум, это:

enter image description here

изменено на это:

enter image description here

Очевидно, что вы можете видеть, что первое неверно.И я проверял это много раз, теперь он всегда работает хорошо, поэтому проблема была действительно здесь.

Итак, мой вопрос здесь, почему это не сработало, когда я использовал std::min_element.Связано ли это с тем, что у меня std::vector std::shared_ptr<node> с, а не просто node с?Должен ли я писать operator< в node классе по-другому?

1 Ответ

0 голосов
/ 08 февраля 2019

Документация C ++ очень ясно объясняет, почему возникает эта проблема:

Если вы посмотрите на страницу на shared_ptr:

https://en.cppreference.com/w/cpp/memory/shared_ptr/operator_cmp

Примечаниечто операторы сравнения для shared_ptr просто сравнивают значения указателя;фактические объекты, на которые указывают, не сравниваются.Наличие оператора <определено для shared_ptr позволяет использовать shared_ptrs в качестве ключей в ассоциативных контейнерах, таких как std :: map и std :: set. </p>

Но есть способ получить std :: min для достиженияповедение, которое вы хотите.Вы можете реализовать объект функции сравнения или использовать лямбду, как у вас уже есть. 

class node
{
public:
    node() : G(0), H(0) {}
    node(int x, int y) : G(x), H(y) {}

    bool operator<(const node& o) const { return  (G + H) < (o.G + o.H); }

    int G;
    int H;
};

struct NodeComparer
{
    bool operator()(std::shared_ptr<node> const& lhs, std::shared_ptr<node>  const& rhs) const
    {
        return *lhs < *rhs;
    }
};

int main()
{
    std::shared_ptr<node> a = std::make_shared<node>(3, 6);
    std::shared_ptr<node> b = std::make_shared<node>(1, 1);
    std::shared_ptr<node> c = std::make_shared<node>(2, 2);

    auto open_set = std::vector<std::shared_ptr<node>>
    { 
        a,b,c
    };

    std::shared_ptr<node> current;

    current = *std::min_element(open_set.begin(), open_set.end(), NodeComparer());


    getchar();

}

Как только вы заключаете узел в shared_ptr, вы больше не имеете дело с типом узла, вы имеете дело с shared_ptrтип.И поэтому вы должны ожидать, что все операции, которые вы выполняете с данными, будут отражать это.Например, оператор sizeof (), примененный к узлу shared_ptr, вернет вам размер shared_ptr, а не размер узла.Таким же образом, когда вы выполняете сравнение для двух shared_ptr, для этого типа определяется оператор сравнения shared_ptr.

...