Was ist "Argument-Dependent Lookup" (auch bekannt als ADL oder "Koenig Lookup")?

176

Was sind einige gute Erklärungen für die argumentabhängige Suche? Viele Leute nennen es auch Koenig Lookup.

Am liebsten würde ich wissen:

  • Warum ist es eine gute Sache?
  • Warum ist es eine schlechte Sache?
  • Wie funktioniert es?
user965369
quelle

Antworten:

223

Koenig Lookup oder Argument Dependent Lookup beschreibt, wie unqualifizierte Namen vom Compiler in C ++ gesucht werden.

Der C ++ 11-Standard § 3.4.2 / 1 besagt:

Wenn der Postfix-Ausdruck in einem Funktionsaufruf (5.2.2) eine unqualifizierte ID ist, können andere Namespaces durchsucht werden, die bei der üblichen unqualifizierten Suche (3.4.1) nicht berücksichtigt wurden, und in diesen Namespaces Namespace-Scope-Friend-Funktionsdeklarationen ( 11.3) kann sonst nicht sichtbar gefunden werden. Diese Änderungen an der Suche hängen von den Argumenttypen ab (und bei Vorlagenvorlagenargumenten vom Namespace des Vorlagenarguments).

Einfacher ausgedrückt sagt Nicolai Josuttis 1 :

Sie müssen den Namespace nicht für Funktionen qualifizieren, wenn im Namespace der Funktion ein oder mehrere Argumenttypen definiert sind.

Ein einfaches Codebeispiel:

namespace MyNamespace
{
    class MyClass {};
    void doSomething(MyClass);
}

MyNamespace::MyClass obj; // global object


int main()
{
    doSomething(obj); // Works Fine - MyNamespace::doSomething() is called.
}

Im obigen Beispiel gibt es weder eine using-deklaration noch eine using-directive, aber der Compiler identifiziert den nicht qualifizierten Namen korrekt doSomething()als die im Namespace deklarierte Funktion, MyNamespaceindem er die Koenig-Suche anwendet .

Wie funktioniert es?

Der Algorithmus weist den Compiler an, nicht nur den lokalen Bereich zu betrachten, sondern auch die Namespaces, die den Typ des Arguments enthalten. Somit stellt der Compiler im obigen Code fest, dass das Objekt obj, das das Argument der Funktion ist doSomething(), zum Namespace gehört MyNamespace. Es sieht sich also diesen Namespace an, um die Deklaration von zu finden doSomething().

Was ist der Vorteil der Koenig-Suche?

Wie das obige einfache Codebeispiel zeigt, bietet die Koenig-Suche dem Programmierer Komfort und Benutzerfreundlichkeit. Ohne Koenig-Suche würde der Programmierer einen Overhead haben, um die vollständig qualifizierten Namen wiederholt anzugeben oder stattdessen zahlreiche usingDeklarationen zu verwenden.

Warum die Kritik an Koenig Lookup?

Übermäßiges Vertrauen in die Koenig-Suche kann zu semantischen Problemen führen und den Programmierer manchmal überraschen.

Betrachten Sie das Beispiel std::swapeines Standardbibliotheksalgorithmus zum Austauschen von zwei Werten. Bei der Koenig-Suche müsste man bei der Verwendung dieses Algorithmus vorsichtig sein, weil:

std::swap(obj1,obj2);

zeigt möglicherweise nicht das gleiche Verhalten wie:

using std::swap;
swap(obj1, obj2);

Bei ADL swaphängt die Version der aufgerufenen Funktion vom Namespace der an ADL übergebenen Argumente ab.

Wenn es einen Namespace gibt Aund wenn A::obj1, A::obj2& A::swap()existiert, führt das zweite Beispiel zu einem Aufruf von A::swap(), was möglicherweise nicht das ist, was der Benutzer wollte.

Wenn aus irgendeinem Grund beide A::swap(A::MyClass&, A::MyClass&)und std::swap(A::MyClass&, A::MyClass&)definiert sind, wird das erste Beispiel aufgerufen std::swap(A::MyClass&, A::MyClass&), das zweite jedoch nicht kompiliert, da swap(obj1, obj2)dies mehrdeutig wäre.

Wissenswertes:

Warum heißt es "Koenig Lookup"?

Weil es vom ehemaligen Forscher und Programmierer Andrew Koenig von AT & T und Bell Labs entwickelt wurde .

Weiterführende Literatur:


1 Die Definition von Koenig Lookup ist wie in Josuttis 'Buch The C ++ Standard Library: A Tutorial and Reference definiert .

Alok Speichern
quelle
11
@AlokSave: +1 für die Antwort, aber die Trivia sind nicht korrekt. Koenig hat ADL nicht erfunden, wie er hier gesteht :)
legends2k
20
Das Beispiel in der Kritik am Koenig-Algorithmus kann sowohl als "Merkmal" der Koenig-Suche als als "Betrug" angesehen werden. Die Verwendung von std :: swap () auf diese Weise ist eine gängige Redewendung: Geben Sie "using std :: swap ()" an, falls keine speziellere Version A :: swap () bereitgestellt wird. Wenn eine spezielle Version von A :: swap () verfügbar ist, möchten wir normalerweise, dass diese aufgerufen wird. Dies bietet mehr Generizität für den Aufruf von swap (), da wir dem Aufruf zum Kompilieren und Arbeiten vertrauen können, aber wir können auch der spezialisierteren Version vertrauen, die verwendet werden soll, wenn es eine gibt.
Anthony Hall
6
@anthrond Da ist mehr drin. Das müssen std::swapSie tatsächlich tun, da die einzige Alternative darin besteht, eine std::swapexplizite Spezialisierung der Vorlagenfunktion für Ihre AKlasse hinzuzufügen . Wenn Ihre AKlasse jedoch selbst eine Vorlage ist, handelt es sich eher um eine Teilspezialisierung als um eine explizite Spezialisierung. Eine teilweise Spezialisierung der Vorlagenfunktion ist nicht zulässig. Das Hinzufügen einer Überladung von std::swapwäre eine Alternative, ist jedoch ausdrücklich verboten (Sie dürfen dem stdNamespace keine Dinge hinzufügen ). ADL ist also der einzige Weg für std::swap.
Adam Badura
1
Ich hätte erwartet, dass überladene Operatoren unter "Vorteil der Koenig-Suche" erwähnt werden. Das Beispiel mit std::swap()scheint etwas rückwärts. Ich würde erwarten, dass das Problem eher bei std::swap()Auswahl als bei typspezifischer Überlastung liegt A::swap(). Das Beispiel mit std::swap(A::MyClass&, A::MyClass&)scheint irreführend. Da stdes für einen Benutzertyp niemals eine bestimmte Überlastung geben würde, halte ich dies nicht für ein gutes Beispiel.
Arvid
1
@ gsamaras ... und? Wir können alle sehen, dass die Funktion nie definiert wurde. Ihre Fehlermeldung beweist, dass es tatsächlich funktioniert hat, weil es MyNamespace::doSomethingnicht nur sucht ::doSomething.
Fund Monica Klage
69

Wenn in Koenig Lookup eine Funktion aufgerufen wird, ohne ihren Namespace anzugeben, wird der Name einer Funktion auch in Namespace (s) gesucht, in denen der Typ der Argumente definiert ist. Aus diesem Grund wird es auch als argumentabhängige Namenssuche bezeichnet , kurz ADL .

Es ist wegen Koenig Lookup, wir können dies schreiben:

std::cout << "Hello World!" << "\n";

Sonst müssten wir schreiben:

std::operator<<(std::operator<<(std::cout, "Hello World!"), "\n");

Das ist wirklich zu viel Tippen und der Code sieht wirklich hässlich aus!

Mit anderen Worten, ohne Koenig Lookup sieht sogar ein Hello World- Programm kompliziert aus.

Nawaz
quelle
12
Überzeugendes Beispiel.
Anthony Hall
10
@AdamBadura: Bitte beachten Sie, dass dies std::coutein Argument für die Funktion ist, das ausreicht, um ADL zu aktivieren. Hast du das bemerkt?
Nawaz
1
@meet: Ihre Frage benötigt eine lange Antwort, die in diesem Bereich nicht bereitgestellt werden kann. Daher kann ich Ihnen nur raten, zu folgenden Themen zu lesen: 1) Unterschrift von ostream<<(wie in dem, was als Argumente verwendet wird und was zurückgegeben wird). 2) Vollqualifizierte Namen (wie std::vectoroder std::operator<<). 3) Eine detailliertere Untersuchung der argumentabhängigen Suche.
Nawaz
2
@WorldSEnder: Ja, du hast recht. Die Funktion, die std::endlals Argument verwendet werden kann, ist tatsächlich eine Mitgliedsfunktion. Wie auch immer, wenn ich "\n"anstelle von verwende std::endl, ist meine Antwort richtig. Danke für den Kommentar.
Nawaz
2
@Destructor: Weil ein Funktionsaufruf in der Form von f(a,b)eine freie Funktion aufruft . Im Falle von std::operator<<(std::cout, std::endl);gibt es also keine solche freie Funktion, die std::endlals zweites Argument dient. Es ist die Member-Funktion, die std::endlals Argument dient und für die Sie schreiben müssen std::cout.operator<<(std::endl);. und da es eine freie Funktion gibt, die char const*als zweites Argument dient, "\n"funktioniert; '\n'würde auch funktionieren.
Nawaz
30

Vielleicht ist es am besten, mit dem Warum zu beginnen und erst dann zum Wie zu gehen.

Bei der Einführung von Namespaces bestand die Idee darin, alles in Namespaces zu definieren, damit sich separate Bibliotheken nicht gegenseitig stören. Dies führte jedoch zu einem Problem mit den Bedienern. Schauen Sie sich zum Beispiel den folgenden Code an:

namespace N
{
  class X {};
  void f(X);
  X& operator++(X&);
}

int main()
{
  // define an object of type X
  N::X x;

  // apply f to it
  N::f(x);

  // apply operator++ to it
  ???
}

Natürlich hätten Sie schreiben können N::operator++(x), aber das hätte den ganzen Punkt der Überlastung des Bedieners zunichte gemacht. Daher musste eine Lösung gefunden werden, die es dem Compiler ermöglichte, operator++(X&)trotz der Tatsache, dass es nicht im Umfang war, zu finden. Auf der anderen Seite sollte es immer noch keinen anderen finden operator++, der in einem anderen, nicht verwandten Namespace definiert ist, was den Aufruf möglicherweise mehrdeutig macht (in diesem einfachen Beispiel würden Sie keine Mehrdeutigkeit erhalten, in komplexeren Beispielen jedoch möglicherweise). Die Lösung war Argument Dependent Lookup (ADL), so genannt, da die Suche vom Argument abhängt (genauer gesagt vom Typ des Arguments). Da das Schema von Andrew R. Koenig erfunden wurde, wird es auch oft als Koenig-Suche bezeichnet.

Der Trick besteht darin, dass für Funktionsaufrufe zusätzlich zur normalen Namenssuche (bei der Namen im Gültigkeitsbereich am Verwendungsort gefunden werden) eine zweite Suche in den Bereichen der Typen von Argumenten durchgeführt wird, die der Funktion gegeben wurden. Wenn Sie also im obigen Beispiel x++in main schreiben , wird operator++nicht nur im globalen Bereich gesucht, sondern auch in dem Bereich, in dem der Typ von x, N::Xdefiniert wurde, dh in namespace N. Und dort findet es eine Übereinstimmung operator++und x++funktioniert daher einfach. Ein anderer operator++, der beispielsweise in einem anderen Namespace definiert ist N2, wird jedoch nicht gefunden. Da ADL nicht auf Namespaces beschränkt ist, können Sie auch f(x)anstelle von N::f(x)in verwenden main().

Celtschk
quelle
Vielen Dank! Nie wirklich verstanden, warum es da war!
user965369
20

Meiner Meinung nach ist nicht alles gut. Leute, einschließlich Compiler-Anbieter, haben es wegen seines manchmal unglücklichen Verhaltens beleidigt.

ADL ist für eine umfassende Überarbeitung der for-range-Schleife in C ++ 11 verantwortlich. Um zu verstehen, warum ADL manchmal unbeabsichtigte Auswirkungen haben kann, sollten Sie berücksichtigen, dass nicht nur die Namespaces berücksichtigt werden, in denen die Argumente definiert sind, sondern auch die Argumente der Vorlagenargumente der Argumente, der Parametertypen der Funktionstypen / der Zeigertypen der Zeigertypen dieser Argumente und so weiter und so fort.

Ein Beispiel mit Boost

std::vector<boost::shared_ptr<int>> v;
auto x = begin(v);

Dies führte zu einer Mehrdeutigkeit, wenn der Benutzer die Bibliothek boost.range verwendet, da beide std::begingefunden werden (durch ADL-Verwendung std::vector) und boost::begingefunden werden (durch ADL-Verwendung boost::shared_ptr).

Johannes Schaub - litb
quelle
Ich habe mich immer gefragt, welchen Nutzen es hat, Vorlagenargumente überhaupt zu berücksichtigen.
Dennis Zickefoose
Ist es fair zu sagen, dass ADL nur für Operatoren empfohlen wird und es besser ist, die Namespaces explizit für andere Funktionen zu schreiben?
Balki
Berücksichtigt es auch die Namespaces von Basisklassen von Argumenten? (das wäre natürlich verrückt, wenn es so wäre).
Alex B
3
wie repariert man? benutze std :: begin?
Paulm
2
@paulm Ja, std::beginlöscht die Mehrdeutigkeit des Namespaces.
Nikos