Was sind transparente Komparatoren?

In C ++ 14 scheinen sich assoziative Container von C ++ 11 geändert zu haben - [assoziativ.reqmts] / 13 sagt:

Die Mitgliedsfunktionsschablonen find, count, lower_bound, upper_bound, und equal_rangedarf nicht in die Überladungsauflösung teilnehmen , es sei denn die Art Compare::is_transparentvorhanden ist .

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>(t) < std::forward<U>(u));
    typedef *unspecified* is_transparent;
};

So zum Beispiel, std::set<T, std::less<T>>würde nicht einen transparenten Komparator, aber std::set<T, std::less<>> würde eine haben.

Welches Problem löst dies und ändert sich dadurch die Funktionsweise von Standardcontainern? Zum Beispiel kann die Template - Parameter von std::setimmer noch Key, Compare = std::less<Key>, ..., nicht so der Standardsatz verliert seine find, countusw. Mitglieder?

Welches Problem löst das?

Siehe Dietmars Antwort und Remyabels Antwort .

und ändert dies die Funktionsweise von Standardcontainern?

Nein, nicht standardmäßig.

Mit den Überladungen der neuen Elementfunktionsvorlagen findusw. können Sie einen Typ verwenden, der mit dem Schlüssel des Containers vergleichbar ist, anstatt den Schlüsseltyp selbst zu verwenden. Siehe N3465 von Joaquín Mª López Muñoz für eine 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 war, aber wir konnten nicht sicher sein, dass Joaquins Vorschlag in allen Fällen sicher sein würde. Der N3465-Vorschlag hätte bei einigen Programmen ernsthafte Probleme verursacht (siehe Abschnitt Auswirkungen auf den vorhandenen Code ). Joaquín bereitete einen aktualisierten Entwurf eines Vorschlags mit einigen alternativen Implementierungen mit unterschiedlichen Kompromissen vor, was der LWG sehr hilfreich war, um die Vor- und Nachteile zu verstehen, aber alle riskierten, einige Programme auf irgendeine Weise zu brechen, sodass es keinen Konsens gab, die Funktion hinzuzufügen. Wir haben entschieden, dass es zwar nicht sicher ist, die Funktion unbedingt hinzuzufügen, aber sicher ist, wenn sie standardmäßig deaktiviert ist und nur "Opt-In" ist.

Der Hauptunterschied des N3657- Vorschlags (der in letzter Minute von mir und STL auf der Grundlage von N3465 und einem später unveröffentlichten Entwurf von Joaquín überarbeitet wurde ) bestand darin, den is_transparentTyp als Protokoll hinzuzufügen, mit dem die neue Funktionalität aktiviert werden kann.

Wenn Sie keinen "transparenten Funktor" verwenden (dh einen, der einen is_transparentTyp definiert ), verhalten sich die Container genauso wie immer, und das ist immer noch die Standardeinstellung.

Wenn Sie sich für die Verwendung std::less<>(die für C ++ 14 neu ist) oder einen anderen "transparenten Funktortyp" entscheiden, erhalten Sie die neue Funktionalität.

Die Verwendung std::less<>von Alias-Vorlagen ist einfach:

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

Der Name is_transparentstammt von STLs N3421, das C ++ 14 die "Diamantoperatoren" hinzufügte. Ein "transparenter Funktor" akzeptiert alle Argumenttypen (die nicht identisch sein müssen) und leitet diese Argumente einfach an einen anderen Operator weiter. Ein solcher Funktor ist genau das, was Sie für eine heterogene Suche in assoziativen Containern benötigen. Daher wurde der Typ is_transparentallen Diamantoperatoren hinzugefügt und als Tag-Typ verwendet, um anzugeben, dass die neue Funktionalität in assoziativen Containern aktiviert werden soll. Technisch gesehen benötigen die Container keinen "transparenten Funktor", sondern nur einen, der das Aufrufen mit heterogenen Typen unterstützt (z. B. ist der pointer_compTyp in https://stackoverflow.com/a/18940595/981959 gemäß der STL-Definition nicht transparent.pointer_comp::is_transparentermöglicht die Verwendung zur Lösung des Problems). Wenn Sie immer nur std::set<T, C>mit Schlüsseln vom Typ nachschlagen Toder intdann Cnur mit Argumenten vom Typ Tund int(in jeder Reihenfolge) aufrufbar sein müssen, muss es nicht wirklich transparent sein. Wir haben diesen Namen teilweise verwendet, weil wir keinen besseren Namen finden konnten (ich hätte es vorgezogen, is_polymorphicweil solche Funktoren statischen Polymorphismus verwenden, aber es gibt bereits ein std::is_polymorphicTypmerkmal, das sich auf dynamischen Polymorphismus bezieht).

In C ++ 11 sind nicht Mitglied Vorlagen find(), lower_bound()usw. Das heißt, nichts von dieser Änderung nicht verloren geht. Die Elementvorlagen 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_transparentVerwendung soll unerwünschte Conversions vermeiden. Wenn die Mitgliedsvorlagen nicht eingeschränkt wären, könnte vorhandener Code Objekte direkt passieren, die ohne die Mitgliedsvorlagen konvertiert worden wären. Der Beispielanwendungsfall von n3657 ist das Suchen eines Objekts in einem std::set<std::string>Zeichenfolgenliteral: Mit der C ++ 11-Definition wird ein std::stringObjekt erstellt, wenn Zeichenfolgenliterale an die entsprechende Elementfunktion übergeben werden. Mit der Änderung ist es möglich, das String-Literal direkt zu verwenden. Wenn das zugrunde liegende Vergleichsfunktionsobjekt ausschließlich in Bezug std::stringdarauf implementiert wird , ist dies schlecht, da jetzt std::stringfür jeden Vergleich ein erstellt wird. Wenn andererseits das zugrunde liegende Vergleichsfunktionsobjekt a annehmen kannstd::string und ein String-Literal, das die Konstruktion eines temporären Objekts vermeiden kann.

Der verschachtelte is_transparentTyp im Vergleichsfunktionsobjekt bietet eine Möglichkeit, anzugeben, ob die Vorlagenelementfunktion verwendet werden soll: Wenn das Vergleichsfunktionsobjekt heterogene Argumente verarbeiten kann, definiert es diesen Typ, um anzuzeigen, dass es effizient mit verschiedenen Argumenten umgehen kann. Beispielsweise delegieren die neuen Operatorfunktionsobjekte nur an operator<()und behaupten, transparent zu sein. Zumindest funktioniert das, für std::stringdas weniger überlastet wurde als für die char const*als Argument genommenen Operatoren . Da diese Funktionsobjekte auch neu sind, selbst wenn sie das Falsche tun (dh für einen Typ eine Konvertierung erfordern), wäre dies zumindest keine stille Änderung, die zu einer Leistungsverschlechterung führt.

_{Das Folgende sind alle Copy-Pasta von n3657 .}

Frage: Was ist der Zweck, einen Komparator "transparent" zu machen?

A. Die assoziativen Container-Suchfunktionen (find, lower_bound, obere_bound, gleicher Bereich) verwenden nur ein Argument von key_type, 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 Erstellen eines großen Objekts zum Suchen in einer Menge, wenn die Komparatorfunktion nur ein Feld des Objekts betrachtet. Die Benutzer haben den starken Wunsch, nach anderen Typen suchen zu können, die mit dem Schlüsseltyp vergleichbar sind.

F. Welches Problem löst dies?

A. Die LWG hatte Bedenken hinsichtlich des folgenden Codes:

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

In C ++ 11 wird ein einzelner temporärer std :: string erstellt und anschließend 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 weiterleitet, die einen temporären std :: string für erstellt jeder Vergleich. Die LWG betrachtete dieses Leistungsproblem als ernstes Problem. Die Funktion find () der Vorlage würde auch verhindern, dass NULL in einem Zeigercontainer gefunden wird, wodurch zuvor gültiger Code nicht mehr kompiliert wird. Dies wurde jedoch als weniger schwerwiegendes Problem angesehen als die stille Leistungsregression

F. Ändert dies die Funktionsweise von Standardcontainern?

A. Dieser Vorschlag ändert die assoziativen Container in und durch Überladen der Lookup-Member-Funktionen mit Member-Funktionsvorlagen. Es gibt keine Sprachänderungen.

Q. So verliert die Standardeinstellung ihre Mitglieder für Suchen, Zählen usw.

A. Fast der gesamte vorhandene C ++ 11-Code ist nicht betroffen, da die Elementfunktionen nur vorhanden sind, wenn neue C ++ 14-Bibliotheksfunktionen als Vergleichsfunktionen verwendet werden.

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,

Fügen Sie Absatz 13 in 23.2.4 [assoziative.Anforderungen] hinzu: Die Elementfunktionsvorlagen find, lower_bound, obere_bound und gleicher Bereich dürfen nicht an der Überlastungsauflösung teilnehmen, es sei denn, der Typ Compare :: is_transparent existiert nicht.

n3421 bietet ein Beispiel für "Transparent Operator Functors" .

Der vollständige Code ist hier .

Stephan T Lavavej spricht über Probleme, bei denen der Compiler ständig Provisorien erstellt, und wie sein Vorschlag für transparente Operator-Funktoren dies in c ++ 1y lösen wird

GoingNative 2013 - Helfen Sie dem Compiler nicht (ungefähr zur vollen Stunde)