c++ - 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

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());

Answer 3

问题是在/pair < int, tablero& >内部复制的情况下参考不起作用。为了解决这个问题，我们需要. 和其他实现需要相应地改变。make_heappop_heappair<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_heapCompare

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