Was sind transparente Komparatoren?

Lesezeit: 10 Minuten

Was sind transparente Komparatoren
Kerrek SB

In C++14 scheinen sich assoziative Container gegenüber C++11 geändert zu haben – [associative.reqmts]/13 sagt:

Die Memberfunktionsvorlagen find, count, lower_bound, upper_boundund equal_range darf nicht an der Überlastauflösung teilnehmen, es sei denn, der Typ Compare::is_transparent existiert.

Was ist der Zweck, einen Komparator “transparent” zu machen?

C++14 bietet auch Bibliotheksvorlagen wie diese:

template <class T = void> struct less {
    constexpr bool operator()(const T& x, const T& y) const;
    typedef T first_argument_type;
    typedef T second_argument_type;
    typedef bool result_type;
};

template <> struct less<void> {
    template <class T, class U> auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>
    typedef *unspecified* is_transparent;
};

Also zum Beispiel std::set<T, std::less<T>> möchten nicht haben einen transparenten Komparator, aber std::set<T, std::less<>> möchten habe eine.

Welches Problem wird dadurch gelöst und ändert sich dadurch die Funktionsweise von Standardcontainern? Zum Beispiel die Vorlagenparameter von std::set sind immer noch Key, Compare = std::less<Key>, ...so verliert der Standardsatz seine find, countusw. Mitglieder?

  • Zum Beispiel, siehe diese cpReferenzbeschreibung. Und jetzt komme ich mir blöd vor, weil ich das Wort „Memberfunktion“ notiere Vorlage“…

    – Kerrek SB

    1. Dezember 2013 um 21:24 Uhr

  • Möglicherweise verwandt: stackoverflow.com/questions/18939882/…

    Benutzer1508519

    1. Dezember 2013 um 21:33 Uhr

  • cpreference hat auch einen Klappentext en.cppreference.com/w/cpp/utility/functional/less_void

    – Kubbi

    1. Dezember 2013 um 22:09 Uhr


1647066013 352 Was sind transparente Komparatoren
Jonathan Wakely

Welches Problem wird dadurch gelöst,

Siehe Dietmars Antwort und Remyabels Antwort.

und ändert sich dadurch die Funktionsweise von Standardcontainern?

Nein, standardmäßig nicht.

Die neue Member-Funktionsvorlage überlädt von find usw. ermöglichen es Ihnen, einen Typ zu verwenden, der mit dem Schlüssel des Containers vergleichbar ist, anstatt den Schlüsseltyp selbst zu verwenden. Sehen N3465 von Joaquín Mª López Muñoz für die Begründung und einen detaillierten, sorgfältig geschriebenen Vorschlag, diese Funktion hinzuzufügen.

Auf dem Treffen in Bristol stimmte die LWG zu, dass die heterogene Suchfunktion nützlich und wünschenswert sei, aber wir konnten nicht sicher sein, dass Joaquíns Vorschlag in allen Fällen sicher wäre. Der N3465-Vorschlag hätte einigen Programmen ernsthafte Probleme bereitet (siehe die Auswirkungen auf bestehenden Code Sektion). Joaquín bereitete einen aktualisierten Vorschlagsentwurf mit einigen alternativen Implementierungen mit unterschiedlichen Kompromissen vor, was der LWG sehr hilfreich war, um die Vor- und Nachteile zu verstehen, aber sie alle riskierten, einige Programme auf irgendeine Weise zu beschädigen, sodass es keinen Konsens gab, das Feature hinzuzufügen. Wir entschieden, dass es zwar nicht sicher wäre, die Funktion bedingungslos hinzuzufügen, es aber sicher wäre, wenn sie standardmäßig deaktiviert wäre und nur “anmelden”.

Der entscheidende Unterschied der N3657 Vorschlag (der in letzter Minute von mir und STL überarbeitet wurde, basierend auf N3465 und ein später unveröffentlichter Entwurf von Joaquín) sollte hinzugefügt werden is_transparent geben Sie als Protokoll ein, das verwendet werden kann, um sich für die neue Funktionalität anzumelden.

Wenn Sie keinen “transparenten Funktor” verwenden (dh einen, der a is_transparent type) dann verhalten sich die Container genauso wie sie es immer getan haben, und das ist immer noch die Voreinstellung.

Wenn Sie sich für die Verwendung entscheiden std::less<> (was neu für C++14 ist) oder einen anderen “transparenten Funktor”-Typ, dann erhalten Sie die neue Funktionalität.

Verwenden std::less<> ist mit Alias-Vorlagen einfach:

template<typename T, typename Cmp = std::less<>, typename Alloc = std::allocator<T>>
  using set = std::set<T, Cmp, Alloc>;

Der Name is_transparent stammt aus STLs N3421 die die “Diamantoperatoren” zu C++14 hinzufügten. Ein “transparenter Funktor” ist einer, der beliebige Argumenttypen akzeptiert (die nicht gleich sein müssen) und diese Argumente einfach an einen anderen Operator weiterleitet. Ein solcher Funktor ist genau das, was Sie für die heterogene Suche in assoziativen Containern wollen, also der Typ is_transparent wurde allen Rautenoperatoren hinzugefügt und als Tag-Typ verwendet, um anzugeben, dass die neue Funktionalität in assoziativen Containern aktiviert werden sollte. Technisch gesehen benötigen die Container keinen “transparenten Funktor”, sondern nur einen, der den Aufruf mit heterogenen Typen unterstützt (z pointer_comp Typ in https://stackoverflow.com/a/18940595/981959 ist nach STL-Definition nicht transparent, aber definierend pointer_comp::is_transparent ermöglicht die Verwendung zur Lösung des Problems). Wenn Sie immer nur in Ihrer nachschlagen std::set<T, C> mit Schlüsseln des Typs T oder int dann C muss nur mit Argumenten vom Typ aufrufbar sein T und int (in beliebiger Reihenfolge) muss es nicht wirklich transparent sein. Wir haben diesen Namen teilweise verwendet, weil uns kein besserer Name einfiel (ich hätte es vorgezogen is_polymorphic weil solche Funktoren statischen Polymorphismus verwenden, aber es gibt bereits einen std::is_polymorphic Typmerkmal, das sich auf dynamischen Polymorphismus bezieht).

  • Hey, warst du derjenige, zu dem STL in dem verlinkten Talk von Woolstar gesagt hat: “Natürlich kannst du im Kopf Schablonen-Argument-Deduktion machen”?

    – Kerrek SB

    4. Dezember 2013 um 21:12 Uhr

  • Nein, ich war nicht dort, aber es gibt Leute mit weitaus konformeren Compilern im Kopf als ich 🙂

    – Jonathan Wakely

    4. Dezember 2013 um 23:02 Uhr

  • Ich denke, “Diamantoperator” bezieht sich auf <> in dem verknüpften Vorschlag, aber dieser Vorschlag wurde nicht eingeführt <> – Es ist eine vorhandene Syntax für eine leere Vorlagenparameterliste. “Diamant-Operator-Funktoren” wären etwas weniger verwirrend.

    – Qwertie

    22. Januar 2019 um 22:13 Uhr

Was sind transparente Komparatoren
Dietmar Kühl

In C++11 gibt es keine Membervorlagen find(), lower_bound()usw. Das heißt, durch diese Änderung geht nichts verloren. Die Mitgliedsvorlagen wurden mit n3657 eingeführt, um die Verwendung heterogener Schlüssel mit den assoziativen Containern zu ermöglichen. Ich sehe kein konkretes Beispiel, wo dies nützlich ist, außer dem Beispiel, das gut und schlecht ist!

Die is_transparent Die Verwendung dient dazu, unerwünschte Konvertierungen zu vermeiden. Wenn die Mitgliedsvorlagen uneingeschränkt wären, kann vorhandener Code Objekte direkt passieren, die ohne die Mitgliedsvorlagen konvertiert worden wären. Der beispielhafte Anwendungsfall aus n3657 ist das Auffinden eines Objekts in a std::set<std::string> Verwenden eines Zeichenfolgenliterals: mit der C++11-Definition a std::string -Objekt wird erstellt, wenn ein Zeichenfolgenliteral an die entsprechende Elementfunktion übergeben wird. Mit der Änderung ist es möglich, das String-Literal direkt zu verwenden. Wenn das zugrunde liegende Vergleichsfunktionsobjekt ausschließlich im Hinblick auf implementiert ist std::string das ist schlecht, weil jetzt a std::string für jeden Vergleich erstellt würden. Wenn andererseits das zugrunde liegende Vergleichsfunktionsobjekt eine annehmen kann std::string und ein Zeichenfolgenliteral, das die Konstruktion eines temporären Objekts vermeiden kann.

Das verschachtelte is_transparent Der Typ im Vergleichsfunktionsobjekt bietet eine Möglichkeit anzugeben, ob die vorlagenbasierte Elementfunktion verwendet werden soll: Wenn das Vergleichsfunktionsobjekt mit heterogenen Argumenten umgehen kann, definiert es diesen Typ, um anzugeben, dass es mit unterschiedlichen Argumenten effizient umgehen kann. Beispielsweise delegieren die neuen Operatorfunktionsobjekte einfach an operator<() und behaupten, transparent zu sein. Das funktioniert zumindest für std::string die weniger überladen hat als die Operatoren, die nehmen char const* als argument. Da diese Funktionsobjekte ebenfalls neu sind, selbst wenn sie das Falsche tun (dh eine Konvertierung für einen bestimmten Typ erfordern), wäre dies zumindest keine stille Änderung, die zu einer Leistungsverschlechterung führt.

  • Danke – siehe meinen Kommentar zur anderen Frage: Erhalten Sie standardmäßig das transparente Verhalten?

    – Kerrek SB

    1. Dezember 2013 um 23:10 Uhr

  • @KerrekSB: Das transparente Verhalten ist aktiviert, wenn is_transparent ist im Vergleichsfunktionsobjekt gemäß 23.2.4 definiert [associative.reqmts] Absatz 13. Die Standard-Vergleichsfunktion Objekte ist std::less<Key> nach 23.4.2 [associative.map.syn] und 23.4.3 [associative.set.syn]. Gemäß 20.10.5 [comparison] Absatz 4 die allgemeine Vorlage für std::less<...> tut nicht einen verschachtelten Typ definieren is_transparent aber die std::less<void> Spezialisierung tut. Das heißt, nein, Sie erhalten standardmäßig keinen transparenten Operator.

    – Dietmar Kühl

    1. Dezember 2013 um 23:45 Uhr

  • Hast du eine Idee für die Namensgebung? ich meine warum is_transparent?

    – Plasmacel

    19. Juni 2018 um 20:01 Uhr

  • Sie wollen ein „konkretes Beispiel, wo das sinnvoll ist“? Hier ist mein Anwendungsfall

    – Spraff

    5. Januar 2019 um 15:23 Uhr

Das Folgende ist alles Copy-Pasta von n3657.

Q. Was ist der Zweck, einen Komparator “transparent” zu machen?

A. Die Suchfunktionen für assoziative Container (find, lower_bound, upper_bound, equal_range) nehmen nur ein Argument von key_type entgegen, sodass Benutzer (entweder implizit oder explizit) ein Objekt des key_type erstellen müssen, um die Suche durchzuführen. Dies kann teuer sein, z. B. das Konstruieren eines großen Objekts zum Suchen in einem Satz, wenn die Komparatorfunktion nur ein Feld des Objekts betrachtet. Unter den Benutzern besteht ein starker Wunsch, mit anderen Typen suchen zu können, die mit dem key_type vergleichbar sind.

Q. Welches Problem wird dadurch gelöst

A. Die LWG hatte Bedenken bezüglich Code wie dem folgenden:

std::set<std::string> s = /* ... */;
s.find("key");

In C++11 wird dadurch ein einzelner std::string temporär erstellt und dann mit Elementen verglichen, um den Schlüssel zu finden.

Mit der von N3465 vorgeschlagenen Änderung wäre die Funktion std::set::find() eine uneingeschränkte Vorlage, die das const char* an die Komparatorfunktion std::less weitergeben würde, die einen temporären std::string für erstellen würde jeden Vergleich. Die LWG betrachtete dieses Leistungsproblem als ein ernstes Problem. Die Template-Funktion find() würde auch verhindern, dass NULL in einem Container mit Zeigern gefunden wird, was dazu führt, dass zuvor gültiger Code nicht mehr kompiliert wird, aber dies wurde als weniger schwerwiegendes Problem angesehen als die stille Leistungsregression

Q. ändert dies die Funktionsweise von Standardcontainern?

A. Dieser Vorschlag modifiziert die assoziativen Container in und durch Überladen der Lookup-Mitgliedsfunktionen mit Mitgliedsfunktionsvorlagen. Es gibt keine Sprachänderungen.

Q. ebenso verliert der Standardsatz seine find-, count- usw. Mitglieder

A. Fast der gesamte vorhandene C++11-Code ist nicht betroffen, da die Memberfunktionen nicht vorhanden sind, es sei denn, neue C++14-Bibliotheksfeatures werden als Vergleichsfunktionen verwendet.

Um Yakk zu zitieren,

In C++14 ist std::set::find eine Vorlagenfunktion, wenn Compare::is_transparent vorhanden ist. Der Typ, den Sie übergeben, muss nicht Key sein, sondern entspricht nur Ihrem Komparator.

und n3657,

Absatz 13 in 23.2.4 hinzufügen [associative.reqmts]: Die Member-Funktionsvorlagen find, lower_bound, upper_bound und equal_range dürfen nicht an der Überladungsauflösung teilnehmen, es sei denn, der Typ Compare::is_transparent ist ist nicht vorhanden existiert.

n3421 bietet ein Beispiel für “Transparent Operator Functors”.

Die vollständiger Code ist hier.

  • Tut std::set<std::string> tatsächlich profitieren von “bestanden char const * durch”, oder müssen Sie eine machen std::set<std::string, std::less<>>?

    – Kerrek SB

    1. Dezember 2013 um 23:09 Uhr

  • @Kerrek Ich denke, “das Übergeben der char const *” war das Problem, das sie vermeiden wollten, wenn ich mich nicht irre. Sehen Sie sich den Wortlaut an: With the change proposed by N3465 the std::set::find() function would be an unconstrained template which would pass the const char* through to the comparator function, std::less<std::string>, which would construct a std::string temporary for every comparison. The LWG considered this performance problem to be a serious issue.

    Benutzer1508519

    1. Dezember 2013 um 23:20 Uhr

  • Ihr Zitat und meins von Paragraph 13 sagen das Gegenteil: “es sei denn, der Typ existiert / existiert nicht” …?!

    – Kerrek SB

    1. Dezember 2013 um 23:22 Uhr

  • @KerrekSB, das ist meine Schuld, N3657 sollte “existiert” sagen, aber ich schrieb “existiert nicht” … es war ein spätes Papier, das in letzter Minute geschrieben wurde. Der Normentwurf ist richtig.

    – Jonathan Wakely

    4. Dezember 2013 um 18:20 Uhr


  • Ja, es könnte klarer sein, zu zitieren, was ich gemeint um nicht zu sagen was ich damals eigentlich gesagt habe 🙂

    – Jonathan Wakely

    4. Dezember 2013 um 18:23 Uhr

Stephan T. Lavavej spricht über Probleme, bei denen der Compiler ständig Temporäre erstellt, und wie sein Vorschlag transparenter Operatorfunktoren dies in c++1y lösen wird

GoingNative 2013 – Hilf dem Compiler nicht (ungefähr zur Stunde)

992890cookie-checkWas sind transparente Komparatoren?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy