Compare Funktion für priority_queue

farw

Hallo,

ich brauche für eine priority_queue eine Vergleichsfunktion, die mir alle Werte gleich -1 nach hinten sortiert. Werte ungleich -1 sollen nach der normalen Ordnung aufsteigend sortiert sein.
Z.B. käme bei der Menge {6, 2, -1, 1} folgende Ordnung zustande: 1, 2, 6, -1.
Ich habe folgendes geschrieben, nur irgendwie scheint da ein Denkfehler drin zu sein, denn sie wählt immer das größte Element != -1.

class comp
{
    public:
    bool operator()(node* lhs, node* rhs)
    {
        if (lhs->distance == -1)
            return false;
        else if (lhs->distance < rhs->distance)
            return true;
        else
            return false;
    }
};

Danke für die Hilfe.

BigNeal

ich nehme mal an, dass die returns (false/true) dem Sinn-Ensprechend richtig gesetzt sind.

Ich denke der Fehler liegt daran, dass aus rhs == -1 sein kann. Der fall ist nicht abgedeckt und wird somit "normal" verglichen mit den anderen Zahlen.
versuch mal mit

if(rhs->distance == -1)
  return true;

ist ungetestet

Jepp, dein comparator is falsch.

struct comp
{
    bool operator()(node const* lhs, node const* rhs) const
    {
        bool specialL = lhs->distance == -1;
        bool specialR = rhs->distance == -1;
        if (specialL != specialR) {
            return specialR;
        } else {
            return lhs->distance < rhs->distance;
        }
    }
};

müsste klappen

Unter der Annahme, dass distance vom Typ int ist und außer -1 keine anderen negativen Zahlen zugelassen werden, könnte man es auch so machen:

struct comp
{
    bool operator()(node const* lhs, node const* rhs) const
    {
        unsigned int l = lhs->distance; // -1 wird automatisch zu UINT_MAX
        unsigned int r = rhs->distance; // -1 wird automatisch zu UINT_MAX
        return l<r;
    }
};

kk