C ++ 11 std :: set Lambda-Vergleichsfunktion

Ich möchte eine std::setmit einer benutzerdefinierten Vergleichsfunktion erstellen . Ich könnte es als Klasse mit definieren operator(), aber ich wollte die Möglichkeit genießen, ein Lambda dort zu definieren, wo es verwendet wird. Deshalb habe ich beschlossen, die Lambda-Funktion in der Initialisierungsliste des Konstruktors der Klasse zu definieren, die das std::setals Mitglied hat. Aber ich kann den Typ des Lambda nicht bekommen. Bevor ich fortfahre, hier ein Beispiel:

class Foo
{
private:
     std::set<int, /*???*/> numbers;
public:
     Foo () : numbers ([](int x, int y)
                       {
                           return x < y;
                       })
     {
     }
};

Nach der Suche habe ich zwei Lösungen gefunden: eine mit std::function. Lassen Sie einfach den eingestellten Vergleichsfunktionstyp sein std::function<bool (int, int)>und übergeben Sie das Lambda genau wie ich. Die zweite Lösung besteht darin, eine make_set-Funktion wie zu schreiben std::make_pair.

LÖSUNG 1:

class Foo
{
private:
     std::set<int, std::function<bool (int, int)> numbers;
public:
     Foo () : numbers ([](int x, int y)
                       {
                           return x < y;
                       })
     {
     }
};

LÖSUNG 2:

template <class Key, class Compare>
std::set<Key, Compare> make_set (Compare compare)
{
     return std::set<Key, Compare> (compare);
}

Die Frage ist, habe ich einen guten Grund, eine Lösung der anderen vorzuziehen? Ich bevorzuge die erste, weil sie Standardfunktionen verwendet (make_set ist keine Standardfunktion), aber ich frage mich: Macht die Verwendung std::functionden Code (möglicherweise) langsamer? Ich meine, verringert es die Wahrscheinlichkeit, dass der Compiler die Vergleichsfunktion einbindet, oder sollte es klug genug sein, sich genau so zu verhalten, als wäre es ein Lambda-Funktionstyp und nicht std::function(ich weiß, in diesem Fall kann es keine sein Lambda-Typ, aber weißt du, ich frage im Allgemeinen)?

(Ich benutze GCC, möchte aber wissen, was beliebte Compiler im Allgemeinen tun.)

ZUSAMMENFASSUNG, NACHDEM ICH VIELE GROSSE ANTWORTEN ERHALTEN HABE:

Wenn die Geschwindigkeit kritisch ist, ist die beste Lösung, eine Klasse mit operator()aka functor zu verwenden. Für den Compiler ist es am einfachsten, Indirektionen zu optimieren und zu vermeiden.

Verwenden Sie für eine einfache Wartung und eine bessere Allzwecklösung mit C ++ 11-Funktionen std::function. Es ist immer noch schnell (nur ein bisschen langsamer als der Funktor, aber es kann vernachlässigbar sein) und Sie können jede Funktion verwenden - std::function, Lambda, jedes aufrufbare Objekt.

Es gibt auch eine Option zur Verwendung eines Funktionszeigers, aber wenn es kein Geschwindigkeitsproblem gibt, ist es meiner Meinung std::functionnach besser (wenn Sie C ++ 11 verwenden).

Es gibt eine Option, um die Lambda-Funktion an einer anderen Stelle zu definieren, aber dann erhalten Sie nichts davon, wenn die Vergleichsfunktion ein Lambda-Ausdruck ist, da Sie sie genauso gut zu einer Klasse machen könnten operator()und der Ort der Definition ohnehin nicht die Mengenkonstruktion wäre.

Es gibt weitere Ideen, z. B. die Verwendung der Delegierung. Wenn Sie eine gründlichere Erklärung aller Lösungen wünschen, lesen Sie die Antworten :)

Ja, ein std::functionführt eine fast unvermeidbare Indirektion in Ihre ein set. Während der Compiler kann immer in der Theorie, herauszufinden , dass alle Nutzung Ihrer set‚s std::functiongeht es auf einem Lambda - Aufruf, der immer genau die gleiche Lambda ist, die sowohl hart und extrem zerbrechlich ist.

Fragil, denn bevor der Compiler sich selbst beweisen kann, dass alle Aufrufe std::functiontatsächlich Aufrufe an Ihr Lambda sind, muss er beweisen, dass kein Zugriff auf Ihr std::setjemals das std::functionauf etwas anderes als Ihr Lambda setzt. Das heißt, es muss alle möglichen Routen aufspüren, um Ihre std::setin allen Kompilierungseinheiten zu erreichen und zu beweisen, dass keine von ihnen dies tut.

Dies kann in einigen Fällen möglich sein, aber relativ harmlose Änderungen können es auch dann beschädigen, wenn Ihr Compiler es geschafft hat, dies zu beweisen.

Auf der anderen Seite kann ein Funktor mit einem Staatenlosen operator()das Verhalten leicht nachweisen, und Optimierungen, die damit verbunden sind, sind alltägliche Dinge.

Also ja, in der Praxis würde ich vermuten, std::functiondass es langsamer sein könnte. Auf der anderen Seite ist die std::functionLösung einfacher zu warten als die andere make_set, und der Austausch der Programmiererzeit gegen die Programmleistung ist ziemlich fungibel.

make_sethat den schwerwiegenden Nachteil, dass ein solcher setTyp aus dem Aufruf an abgeleitet werden muss make_set. Oft setspeichert ein dauerhafter Speicherstatus und nicht etwas, das Sie auf dem Stapel erstellen, den Gültigkeitsbereich.

Wenn Sie ein statisches oder globales Lambda ohne Status erstellt haben auto MyComp = [](A const&, A const&)->bool { ... }, können Sie mithilfe der std::set<A, decltype(MyComp)>Syntax ein Lambda erstellen set, das beibehalten werden kann. Der Compiler kann es jedoch leicht optimieren (da alle Instanzen decltype(MyComp)zustandslose Funktoren sind) und inline. Ich weise darauf hin, weil Sie das setin a stecken struct. (Oder unterstützt Ihr Compiler

struct Foo {
  auto mySet = make_set<int>([](int l, int r){ return l<r; });
};

was ich überraschend finden würde!)

Wenn Sie sich Sorgen um die Leistung machen, std::unordered_setdenken Sie schließlich, dass dies viel schneller ist (auf Kosten der Unfähigkeit, den Inhalt in der richtigen Reihenfolge zu durchlaufen und einen guten Hash schreiben / finden zu müssen) und dass eine Sortierung std::vectorbesser ist, wenn Sie einen haben 2-phasig "Alles einfügen" und dann "Inhalte wiederholt abfragen". Füllen Sie es vectordann einfach in den ersten und verwenden Sie dann sort unique eraseden kostenlosen equal_rangeAlgorithmus.

Es ist unwahrscheinlich, dass der Compiler einen std :: -Funktionsaufruf einbinden kann, wohingegen jeder Compiler, der Lambdas unterstützt, mit ziemlicher Sicherheit die Funktorversion einbinden würde, auch wenn dieser Funktor ein Lambda ist, das nicht von a verborgen wird std::function.

Sie können verwenden decltype, um den Vergleichstyp des Lambda zu erhalten:

#include <set>
#include <iostream>
#include <iterator>
#include <algorithm>

int main()
{
   auto comp = [](int x, int y){ return x < y; };
   auto set  = std::set<int,decltype(comp)>( comp );

   set.insert(1);
   set.insert(10);
   set.insert(1); // Dupe!
   set.insert(2);

   std::copy( set.begin(), set.end(), std::ostream_iterator<int>(std::cout, "\n") );
}

Welche Drucke:

1
2
10

Sehen Sie, wie es live läuft Coliru.

Ein zustandsloses Lambda (dh eines ohne Captures) kann in einen Funktionszeiger zerfallen. Ihr Typ könnte also sein:

std::set<int, bool (*)(int, int)> numbers;

Sonst würde ich mich für die make_setLösung entscheiden. Wenn Sie keine einzeilige Erstellungsfunktion verwenden, weil diese nicht dem Standard entspricht, wird nicht viel Code geschrieben!

Nach meiner Erfahrung mit dem Profiler besteht der beste Kompromiss zwischen Leistung und Schönheit darin, eine benutzerdefinierte Delegatenimplementierung zu verwenden, z.

/codereview/14730/impossibly-fast-delegate-in-c11

Da std::functionist das meist etwas zu schwer. Ich kann Ihre spezifischen Umstände nicht kommentieren, da ich sie jedoch nicht kenne.

Wenn Sie fest entschlossen sind, das setals Klassenmitglied zu haben und seinen Komparator zur Konstruktorzeit zu initialisieren, ist mindestens eine Indirektionsebene unvermeidbar. Bedenken Sie, dass Sie nach Kenntnis des Compilers einen weiteren Konstruktor hinzufügen können:

 Foo () : numbers ([](int x, int y)
                   {
                       return x < y;
                   })
 {
 }

 Foo (char) : numbers ([](int x, int y)
                   {
                       return x > y;
                   })
 {
 }

Sobald Sie ein Objekt vom Typ haben Foo, enthält der Typ des Objekts setkeine Informationen darüber, welcher Konstruktor seinen Komparator initialisiert hat. Um das richtige Lambda aufzurufen, ist daher eine Indirektion zum zur Laufzeit ausgewählten Lambda erforderlich operator().

Da Sie Captureless-Lambdas verwenden, können Sie den Funktionszeigertyp bool (*)(int, int)als Vergleichstyp verwenden, da Captureless-Lambdas über die entsprechende Konvertierungsfunktion verfügen. Dies würde natürlich eine Indirektion durch den Funktionszeiger beinhalten.

Der Unterschied hängt stark von den Optimierungen Ihres Compilers ab. Wenn es Lambda in einem optimiert std::function, sind diese äquivalent, wenn nicht, führen Sie eine Indirektion in die erstere ein, die Sie in der letzteren nicht haben werden.