std :: make_heap с парами

Question

Можно ли сделать make_heap() с парой в векторе?

Я использую:

 std::vector< std::pair < int , tablero& > > lista_abierta_;

Я использую функцию объекта, чтобы упорядочить пару по первомучлен, но он падает.

Код:

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include "8_puzzle.h"
#include "tablero.h"

using namespace std;

class comp {
public:
    bool operator()(pair < int, tablero&> a, pair < int, tablero&> b) const {
        return a.first > b.first;
    }
};

pair < int, tablero& > puzzle::A_estrella::tope()
{
    pair < int, tablero& > l=lista_abierta_.front();

    pop_heap(lista_abierta_.begin(),lista_abierta_.end());
    lista_abierta_.pop_back();

    return l;
}

[Взят от здесь ]

Answer 1

Пока std::pair<T, U> обеспечивает operator< (что означает: T и U предоставляют operator<), я не вижу никаких проблем в использовании make_heap.

Answer 2

Проблема справочная, например pair < int, tablero& > не будет работать в случае копирования внутри make_heap / pop_heap.Чтобы это исправить, нам нужно pair<int, std::reference_wrapper<tablero> >.comp и другие реализации должны быть изменены соответствующим образом.

class comp {
public:
    bool operator()(pair < int, std::reference_wrapper<tablero> > a, pair < int, std::reference_wrapper<tablero> > b) const {
        return a.first > b.first;
    }
};

А heap_pop и make_heap потребуется объект Compare.

comp mycomp;
pop_heap(lista_abierta_.begin(),lista_abierta_.end(),mycomp);

Answer 3

Вы можете позвонить std::make_heap<T>, если T предоставляет bool operator<(const T &, const T &) или вы явно передаете компаратор.

Вы должны изменить строку 23 с

pop_heap(lista_abierta_.begin(),lista_abierta_.end());

до

pop_heap(lista_abierta_.begin(),lista_abierta_.end(), comp());