Merkwürdiges Verhalten von std::priority_queue

[tag]

Der operator< ist m. E. falsch. Probier's damit:

bool operator<( const QueueMsg& other ) const
{
 if ( m_ulPriority > other.m_ulPriority )
  return true;
 if ( m_ulPriority < other.m_ulPriority )
  return false;

 return m_ulOrder > other.m_ulOrder;
}

[ChrisM]

Hi,

na gut, gehen wir mal alle Fälle durch.

Fall 1: prio1 > prio2 order1 > order2
Fall 2: prio1 > prio2 order1 < order2
Fall 3: prio1 < prio2 order1 > order2
Fall 4: prio1 < prio2 order1 < order2
Fall 5: prio1 = prio2 order1 > order2
Fall 6: prio1 = prio2 order1 < order2

Meine Vergleichsfunktion:
1. true
2. true
3. true
4. false
5. true
6. false

tags Vergleichsfunktion:
1. true
2. true
3. false
4. false
5. true
6. false

Das Problem scheint also nur bei Fall 3 zu liegen, komisch.

ChrisM

[camper]

fall 2 und fall 3 müssen entgegengesetzte ergebnisse liefern. diese if konstruktionen sind auch irgendwie ziemlich abenteuerlich und schwer verständlich.

bool operator<( const QueueMsg& other ) const
{
    return m_ulPriority > other.m_ulPriority || m_ulPriority == other.m_ulPriority && m_ulOrder > other.m_ulOrder;
}

damit stimmt auch die adhoc definition von == mit dem !(a<b) && !(b<a) überein, was ja meistens erwünscht ist.

[Shade Of Mine]

camper schrieb:

diese if konstruktionen sind auch irgendwie ziemlich abenteuerlich und schwer verständlich.

sagt jemand, der die ganze logik in eine zeile quetscht...

[tag]

Shade Of Mine schrieb:

camper schrieb:

diese if konstruktionen sind auch irgendwie ziemlich abenteuerlich und schwer verständlich.

sagt jemand, der die ganze logik in eine zeile quetscht...

Aber so abenteuerlich sind sie gar nicht.
Übrigens fehlen in der Aufzählung noch drei Fälle, und zwar jeweils order1=order2.

Fall 1: prio1 > prio2, order1 > order2: true
Fall 2: prio1 > prio2, order1 < order2: true
Fall 3: prio1 > prio2, order1 = order2: true

Fall 4: prio1 < prio2, order1 > order2: false
Fall 5: prio1 < prio2, order1 < order2: false
Fall 6: prio1 < prio2, order1 = order2: false

Fall 7: prio1 = prio2, order1 > order2: true
Fall 8: prio1 = prio2, order1 < order2: false
Fall 9: prio1 = prio2, order1 = order2: false

So wird deutlich, dass in den Fällen 1-6 das Ergebnis ausschließlich vom Verhältnis prio1/prio2 abhängt. Falls diese beiden gleich sind, wird das Ergebnis nur von order1/order2 bestimmt usw.

Wenn man Datensätze nach mehreren Kriterien nacheinander sortieren will, kann man sich alle Daten hintereinander wie eine Zahl vorstellen, bei der jede Variable einer Ziffer entspricht.
So denke ich mir das immer und so schreibe ich es auch hin.

Beispiel:
Wenn ich z.B. 11 und 37 vergleiche und bereits weiß, dass der 10er der ersten Zahl größer als der der zweiten ist, muss die gesamte Zahl auch größer sein, ergo

if ( m_ulPriority > other.m_ulPriority )
  return true;

Im umgekerten Fall, wenn der 10er der ersten Zahl kleiner ist, muss die erste Zahl auf jeden Fall kleiner als die zweite sein, daher

if ( m_ulPriority < other.m_ulPriority )
  return false;

Wenn man hier angekommen ist, dann sind die 10er identisch. Daher entscheidet sich alles bei den 1ern. Da das aber die letzte "Ziffer" ist, kann man hier abkürzen. Aus

if ( m_ulOrder > other.m_ulOrder )
  return true;
 if ( m_ulOrder < other.m_ulOrder )
  return false;
 return false; // beide sind identisch

wird

return m_ulOrder > other.m_ulOrder;

Alles zusammen:

bool operator<( const QueueMsg& other ) const
{
  if(m_ulPriority > other.m_ulPriority)
    return true;
  if(m_ulPriority < other.m_ulPriority)
    return false;

  return m_ulOrder > other.m_ulOrder;
}

Es mag ja sein, dass man das ganze auch "handlich" in eine Zeile quetschen kann, aber ich finde solche jeweils vier Zeilen lange if-Blöcke übersichtlicher (u.A. auch deswegen, weil man sie unkompliziert untereinander vertauschen kann, wenn die Sortierung noch nicht ganz passt und weil man auch bei 10 Variablen noch den Überblick behält ;)).

Am Rande bemerkt: Auch sowas ist ein korrekter Vergleich:

bool operator<( const QueueMsg& other ) const
{
  if(m_ulPriority > other.m_ulPriority)
    return true;
  if(m_ulPriority < other.m_ulPriority)
    return false;

  // gleiche Priorität - Alle Einträge mit
  // Prio>5 aufsteigend, Prio<2 absteigend,
  // Rest gar nicht sortieren
  if(m_ulPrio > 5)
    return m_ulOrder < other.m_ulOrder;
  else if(m_ulPrio < 2)
    return m_ulOrder > other.m_ulOrder;
  else
    return false; // alle sind "gleich" bzw. Eigenschaft "Order" nicht sinnvoll/vorhanden
}

[camper]

Shade Of Mine schrieb:

camper schrieb:

diese if konstruktionen sind auch irgendwie ziemlich abenteuerlich und schwer verständlich.

sagt jemand, der die ganze logik in eine zeile quetscht...

es gibt sicher grenzen (erscheint ja auch nur wegen den langen bezeichner gequetscht). aber nach 5 ungeschachtelten ifs, die mit return enden, ist nicht mehr sofort offensichtlich, welche fälle noch offen sind, insbesondere wenn die art des tests sich ständig ändert.
es muss ja auch gar nicht eine zeile sein, bei einem einzigen return statement zählt man eben alle fälle auf, die wahr sind, alles was durchfällt ist dann automatisch falsch:

bool operator<( const QueueMsg& other ) const
{
  return m_ulPriority > other.m_ulPriority                   // einfacher fall, höhere ulPriorität
      || m_ulPriority == other.m_ulPriority                  // oder gleiche priorität UND noch etwas anderes
         && ( m_ulPrio < 2                                   // bei Prio<2 absteigend sortieren
              && m_ulOrder > other.m_ulOrder               
           || m_ulPrio >= 2 && m_ulPrio <= 5                 // andere prioritäten fallen durch (false)
              && false                                       // der compiler optimiert diesen zweig nat. weg
           || m_ulPrio > 5                                   // bei Prio>5 aufsteigend sortieren
              && m_ulOrder < other.m_ulOrder );
}

bei solchen komplexen statements ist es sowieso eher eine frage der richtigen dokumentation.

[Der Pate 3]

Boah Du Bist So Dumm Und So Langweilig Wie TheGayGameCoder!

[tag]

camper schrieb:

aber nach 5 ungeschachtelten ifs, die mit return enden, ist nicht mehr sofort offensichtlich, welche fälle noch offen sind, insbesondere wenn die art des tests sich ständig ändert.

Alles eine Sache der ordentlichen Formatierung und Gruppierung.

camper schrieb:

es muss ja auch gar nicht eine zeile sein, bei einem einzigen return statement zählt man eben alle fälle auf, die wahr sind, alles was durchfällt ist dann automatisch falsch: [quellcode]

Argh! STEINE, STEINE, STEINE!

[ChrisM]

Hi,

danke an euch alle, die Sortierfunktion war wirklich schuld.

Trotzdem hat priority_queue einen komischen Sortieralgorithmus, würde es ganz normal nach jeder Insertion mit Quicksort sortieren, wäre ein anderes, aber trotzdem falsches Ergebnis rausgekommen (IMHO).

ChrisM

[sperenzchen]

Der Pate 3 schrieb:

Boah Du Bist So Dumm Und So Langweilig Wie TheGayGameCoder!

[volkard]

ChrisM schrieb:

mal nach langer Zeit bin ich wieder an ein C++-Paradoxon gestoßen, vielleicht könnt ihr mir helfen.

http://de.wikipedia.org/wiki/Heap_(Datenstruktur)

und die priority_queue sagt dir nur, daß das vordertse element das kleinste ist und macht keine aussagen über das innendrin. paßt prima beieinander, gell?

[Dravere]

@volkard,
Dir ist schon bewusst, dass der Thread aus dem Jahre 2005 stammt und zwar im Januar, als über 4 Jahre alt

Bei Unregistrierten immer das Datum der vorherigen Poster lesen

Grüssli

[volkard]

uups.
(und ich hab mich gefragt, was bei ChrisM so eine amnesie ausgelöst haben kann.)