mit min_element bei Teilauftrag

Question

Kann std::min_element (und auch std::sort und ähnliche Funktionen von <algorithm>) auf Typen mit nur einer Teilaufgabe verwendet werden?

Zum Beispiel:

auto it = std::min_element(vec.cbegin(), vec.cend(), [](const node* a, const node* b) { 
    return a->precedes(*b); 
}); 

node Hier stellt Knoten in einem DAG (gerichteter azyklischer Graph) und a.precedes(b) Tests a es ist ein Vorfahre von b. Wenn aber a und b in verschiedenen Zweigen sind, gibt es auch false zurück, und in diesem Fall a.precedes(b) == b.precedes(a) == false.

Answer 1

Per § 25,4/3 (Schwerpunkt und Fussnoten sind von mir):

Für andere Algorithmen als die in 25.4.3 beschrieben ^* richtig funktioniert, comp ^** muss eine strikt schwache Bestellung auf die Werte induzieren.

_{^* 25.4.3 ist der Abschnitt für binäre Suchalgorithmen.
^**comp ist der benutzerdefinierte Komparator.}

Da std::sort in 25.4.1 definiert und std::min_element ist in 25.4.7, dann brauchen Sie nur eine strenge schwache Ordnung auf den Werten, das heißt:

Der Begriff streng das bezieht sich Anforderung einer irreflexiven Beziehung (! comp (x, x) für alle x) und der Begriff schwach für Anforderungen, die nicht so stark sind wie für eine Gesamtordnung, aber stärker als diejenigen für eine partielle Ordnung. Wenn wir Äquiv (a, b) als! Comp (a, b) & &! Comp (b, a) definieren, dann sind die Anforderungen, dass comp und equiv beide transitive Relationen sein müssen:

(4.1) - comp (a, b) & & comp (b, c) impliziert comp (a, c)

(4.2) - equiv (a, b) & & equiv (b, c) impliziert equiv (a, c)

Soweit ich Ihre Beziehung zu verstehen, ist es nicht die equiv Anforderung überein, da Sie kann habe zwei Knoten, wo !comp(a, b) && !comp(b, a), aber a != b. Wenn Sie a und c auf einem Zweig und b auf einem anderen Zweig haben, funktioniert das obige normalerweise nicht, weil equiv(a, b) == equiv(b, c) == true aber equiv(a, c) == false.

Answer 2

Aus dem C++ 11-Standard § 23.2.1:

a < b umwandelbar bool. lexicographical_-compare(a.begin(), a.end(), b.begin(), b.end()) pre [Bedingung]: < ist für Werte von T definiert. < ist eine Gesamtbestellung Beziehung.

Also, nein, das wird nicht funktionieren.