deklarowanie Priority_queue w C ++ przy użyciu niestandardowego komparatora

88

Próbuję zadeklarować priority_queue of nodes, używając bool Compare(Node a, Node b)jako funkcji komparatora (która znajduje się poza klasą węzła).

Obecnie posiadam:

priority_queue<Node, vector<Node>, Compare> openSet;

Z jakiegoś powodu rozumiem Error: "Compare" is not a type name

Zmiana deklaracji na priority_queue <Node, vector<Node>, bool Compare>

daje mi Error: expected a '>'

Próbowałem też:

priority_queue<Node, vector<Node>, Compare()> openSet;
priority_queue<Node, vector<Node>, bool Compare()> openSet;
priority_queue<Node, vector<Node>, Compare<Node, Node>> openSet; 

Jak prawidłowo zgłosić moje priority_queue?

Steven Morad
źródło

Odpowiedzi:

113

Powinieneś zadeklarować klasę Comparei przeciążać operator()ją w następujący sposób:

class Foo
{

};

class Compare
{
public:
    bool operator() (Foo, Foo)
    {
        return true;
    }
};

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, Compare> pq;
    return 0;
}

Lub, jeśli z jakichś powodów nie możesz zrobić tego jako klasa, możesz użyć std::functiondo tego:

class Foo
{

};

bool Compare(Foo, Foo)
{
    return true;
}

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, std::function<bool(Foo, Foo)>> pq(Compare);
    return 0;
}
awesoon
źródło
1
Idealnie, właśnie to, czego szukałem. Nigdy nie myślałem o utworzeniu osobnej klasy. Czy pierwszy przykład można uznać za lepszy styl?
Steven Morad
2
@StevenMorad, wolę używać klasy z przeciążeniem operator(), wygląda na prostszą.
awesoon
1
@soon Dlaczego przeciążamy operatora ()? Czy jest to związane z wewnętrzną implementacją Priority_queues? overloading> lub <ma sens intuicyjnie, ale () operator nie tak bardzo
Piyush
2
@Piyush, pytanie dotyczy przekazania niestandardowego komparatora do pliku pritority_queue. Możliwe jest przeciążenie operator<i użycie wbudowanego std::lesskomparatora jednak bool Compare(Node a, Node b)zadeklarowanego poza klasą Node, zgodnie z pytaniem.
awesoon
3
Wciąż wracam do tej odpowiedzi, prawdopodobnie już 50 razy, nigdy nie pamiętam składni
Rockstar5645
52

Przyjęta odpowiedź sprawia, że ​​uważasz, że musisz użyć klasy lub klasy std::functionjako komparatora. To nie jest prawda! Jak pokazuje odpowiedź cute_ptr , możesz przekazać wskaźnik funkcji do konstruktora. Jednak składnia, aby to zrobić, jest znacznie prostsza niż tutaj pokazana:

class Node;
bool Compare(Node a, Node b);

std::priority_queue<Node, std::vector<Node>, decltype(&Compare)> openSet(Compare);

Oznacza to, że nie ma potrzeby jawnego kodowania typu funkcji, możesz pozwolić kompilatorowi zrobić to za Ciebie decltype.

Jest to bardzo przydatne, jeśli komparatorem jest lambda. Nie można określić typu lambda w żaden inny sposób niż za pomocą decltype. Na przykład:

auto compare = [](Node a, Node b) { return a.foo < b.foo; }
std::priority_queue<Node, std::vector<Node>, decltype(compare)> openSet(compare);
Cris Luengo
źródło
2
To fantastyczne, zastanawiam się, czy są tu jakieś potencjalne pułapki (problemy). Chciałbym, aby ta odpowiedź była bardziej widoczna i dyskusyjna.
Apollys obsługuje Monikę
1
@Apollys: Używam tej metody regularnie (zwykle Comparejest to lambda, dla której nie da się napisać deklaracji), nie znam żadnych pułapek.
Cris Luengo,
Gdybyś miał to zrobić dla funkcji lambda, gdzie umieściłbyś treść funkcji lambda? Czy należy go przechowywać w zmiennej fwcześniej i wtedy wymienić Comparez f?
Eric Auld
@EricAuld: Tak, Comparemoże być tam funkcją lambda, jak w auto Compare = [](){};. Ale musisz decltype(Compare)raczej użyć niż decltype(&Compare).
Cris Luengo
Cześć Chris, to świetnie, szukałem jakiegoś formatu do użycia z decltype dla priority_queue i bez deklarowania klasy, podałeś doskonałą odpowiedź! Dzięki!
Amanda Wang
17

Trzeci parametr szablonu musi być klasą, która została operator()(Node,Node)przeciążona. Będziesz więc musiał utworzyć klasę w ten sposób:

class ComparisonClass {
    bool operator() (Node, Node) {
        //comparison code here
    }
};

Następnie użyjesz tej klasy jako trzeciego parametru szablonu w następujący sposób:

priority_queue<Node, vector<Node>, ComparisonClass> q;
Mic
źródło
14
Metoda operatora musi być publiczna.
knezi
1
Trzeci szablon nie musi być klasą. Może to być typ funkcji.
Cris Luengo
1
Według cpluplus : Może to być wskaźnik funkcji lub obiekt funkcji
Benav,
9

Odpowiadając bezpośrednio na Twoje pytanie:

Próbuję zadeklarować priority_queueliczbę węzłów, używającbool Compare(Node a, Node b) as the comparator function

Obecnie posiadam:

priority_queue<Node, vector<Node>, Compare> openSet;

Z jakiegoś powodu otrzymuję błąd:

"Compare" is not a type name

Kompilator mówi dokładnie, co jest nie tak: Comparenie jest nazwą typu, ale instancją funkcji, która przyjmuje dwa Nodesi zwraca bool.
Potrzebujesz określić typ wskaźnika funkcji:
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

cute_ptr
źródło
Właśnie tego szukam, aby nadać funkcję w deklaracji Priority_queue, dzięki!
Amanda Wang
6

Można też użyć funkcji lambda.

auto Compare = [](Node &a, Node &b) { //compare };
std::priority_queue<Node, std::vector<Node>, decltype(Compare)> openset(Compare);
rodzi się wolny
źródło
6

Najpierw musisz zdefiniować porównanie. Można to zrobić na 3 sposoby:

  1. użyj klasy
  2. użyj struktury (która jest taka sama jak class)
  3. użyj funkcji lambda.

Jest łatwy w użyciu class / struct, ponieważ łatwo go zadeklarować, po prostu napisz tę linię kodu nad wykonywanym kodem

struct compare{
  public:
  bool operator()(Node& a,Node& b) // overloading both operators 
  {
      return a.w < b.w: // if you want increasing order;(i.e increasing for minPQ)
      return a.w > b.w // if you want reverse of default order;(i.e decreasing for minPQ)
   }
};

Kod telefoniczny:

priority_queue<Node,vector<Node>,compare> pq;
Shivam Mishra
źródło
Do rzeczy @shivam Mishra.
fight_club
3

Na wypadek, gdyby to komuś pomogło:

static bool myFunction(Node& p1, Node& p2) {}
priority_queue <Node, vector<Node>, function<bool(Node&, Node&)>> pq1(myFunction);
Mazhar MIK
źródło
0

wolą struct i to właśnie robią std :: Greater

struct Compare {
  bool operator()(Node const&, Node &) {}
}
Canhua Li
źródło