Qu'est-ce que la «recherche dépendante de l'argument» (aka ADL, ou «Koenig Lookup»)?

176

Quelles sont quelques bonnes explications sur ce qu'est la recherche dépendante des arguments? Beaucoup de gens l'appellent également Koenig Lookup.

De préférence, j'aimerais savoir:

  • Pourquoi est-ce une bonne chose?
  • Pourquoi est-ce une mauvaise chose?
  • Comment ça marche?
user965369
la source

Réponses:

223

Koenig Lookup , ou Argument Dependent Lookup , décrit comment les noms non qualifiés sont recherchés par le compilateur en C ++.

La norme C ++ 11 § 3.4.2 / 1 stipule:

Lorsque l'expression de suffixe dans un appel de fonction (5.2.2) est un identifiant non qualifié, d'autres espaces de noms non pris en compte lors de la recherche non qualifiée habituelle (3.4.1) peuvent être recherchés, et dans ces espaces de noms, des déclarations de fonction d'ami de portée d'espace de noms ( 11.3) non visibles autrement peuvent être trouvés. Ces modifications de la recherche dépendent des types d'arguments (et pour les arguments de modèle de modèle, de l'espace de noms de l'argument de modèle).

En termes plus simples, Nicolai Josuttis déclare 1 :

Vous n'avez pas besoin de qualifier l'espace de noms pour les fonctions si un ou plusieurs types d'argument sont définis dans l'espace de noms de la fonction.

Un exemple de code simple:

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

MyNamespace::MyClass obj; // global object


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

Dans l'exemple ci-dessus, il n'y a ni using-declaration ni using-directive mais le compilateur identifie toujours correctement le nom non qualifié doSomething()comme la fonction déclarée dans l'espace MyNamespacede noms en appliquant la recherche Koenig .

Comment ça marche?

L'algorithme dit au compilateur de regarder non seulement la portée locale, mais également les espaces de noms qui contiennent le type de l'argument. Ainsi, dans le code ci-dessus, le compilateur trouve que l'objet obj, qui est l'argument de la fonction doSomething(), appartient à l'espace de noms MyNamespace. Donc, il regarde cet espace de noms pour localiser la déclaration de doSomething().

Quel est l'avantage de la recherche Koenig?

Comme le montre l'exemple de code simple ci-dessus, la recherche Koenig offre commodité et facilité d'utilisation au programmeur. Sans la recherche Koenig, il y aurait une surcharge sur le programmeur, pour spécifier à plusieurs reprises les noms usingcomplets , ou à la place, utiliser de nombreuses déclarations.

Pourquoi la critique de la recherche Koenig?

Une dépendance excessive à la recherche Koenig peut conduire à des problèmes sémantiques et parfois prendre le programmeur au dépourvu.

Prenons l'exemple de std::swap, qui est un algorithme de bibliothèque standard permettant d'échanger deux valeurs. Avec la recherche Koenig, il faudrait être prudent lors de l'utilisation de cet algorithme car:

std::swap(obj1,obj2);

peut ne pas montrer le même comportement que:

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

Avec ADL, la version de la swapfonction appelée dépend de l'espace de noms des arguments qui lui sont passés.

S'il existe un espace de noms Aet si A::obj1, A::obj2& A::swap()existent, le deuxième exemple entraînera un appel à A::swap(), ce qui pourrait ne pas être ce que l'utilisateur voulait.

En outre, si pour une raison quelconque les deux A::swap(A::MyClass&, A::MyClass&)et std::swap(A::MyClass&, A::MyClass&)sont définis, alors le premier exemple appellera std::swap(A::MyClass&, A::MyClass&)mais le second ne compilera pas car swap(obj1, obj2)serait ambigu.

Trivia:

Pourquoi s'appelle-t-il «Koenig lookup»?

Parce qu'il a été conçu par Andrew Koenig, ancien chercheur et programmeur d'AT & T et de Bell Labs .

Lectures complémentaires:


1 La définition de la recherche Koenig est telle que définie dans le livre de Josuttis, The C ++ Standard Library: A Tutorial and Reference .

Alok Save
la source
11
@AlokSave: +1 pour la réponse, mais le trivia n'est pas correct. Koenig n'a pas inventé l'ADL, comme il le confesse ici :)
legends2k
20
L'exemple de la critique de l'algorithme de Koenig peut être considéré comme une "caractéristique" de la recherche de Koenig autant qu'un "con". Utiliser std :: swap () de cette manière est un idiome courant: Fournissez un 'using std :: swap ()' au cas où une version plus spécialisée A :: swap () n'est pas fournie. Si une version spécialisée de A :: swap () est disponible, nous voudrions normalement que celle-ci soit appelée. Cela fournit plus de généricité pour l'appel swap (), puisque nous pouvons faire confiance à l'appel pour compiler et travailler, mais nous pouvons également faire confiance à la version plus spécialisée à utiliser s'il y en a une.
Anthony Hall
6
@anthrond Il y a plus là-dedans. Avec std::swapvous devez le faire puisque la seule alternative serait d'ajouter std::swapune spécialisation explicite de fonction de modèle pour votre Aclasse. Pourtant, si votre Aclasse est un modèle lui-même, ce serait une spécialisation partielle plutôt qu'une spécialisation explicite. Et la spécialisation partielle de la fonction de modèle n'est pas autorisée. L'ajout d'une surcharge de std::swapserait une alternative mais est explicitement interdit (vous ne pouvez pas ajouter d'éléments à l' stdespace de noms). Donc ADL est le seul moyen pour std::swap.
Adam Badura
1
Je me serais attendu à voir une mention d'opérateurs surchargés sous "avantage de la recherche koenig". l'exemple avec std::swap()semble un peu à l'envers. Je m'attendrais à ce que le problème soit quand std::swap()est sélectionné plutôt que la surcharge spécifique au type A::swap(),. L'exemple avec std::swap(A::MyClass&, A::MyClass&)semble trompeur. comme stdn'aurait jamais de surcharge spécifique pour un type d'utilisateur, je ne pense pas que ce soit un bon exemple.
Arvid
1
@gsamaras ... Et? Nous pouvons tous voir que la fonction n'a jamais été définie. Votre message d'erreur prouve que cela a fonctionné, en fait, parce qu'il cherche MyNamespace::doSomething, pas seulement ::doSomething.
Fund Monica's Lawsuit
69

Dans Koenig Lookup, si une fonction est appelée sans spécifier son espace de noms, alors le nom d'une fonction est également recherché dans les espaces de noms dans lesquels le type du ou des arguments est défini. C'est pourquoi il est également connu sous le nom de recherche de nom dépendant de l' argument , en bref simplement ADL .

C'est à cause de Koenig Lookup, nous pouvons écrire ceci:

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

Sinon, il faudrait écrire:

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

ce qui est vraiment trop de frappe et le code a l'air vraiment moche!

En d'autres termes, en l'absence de Koenig Lookup, même un programme Hello World semble compliqué.

Nawaz
la source
12
Exemple convaincant.
Anthony Hall
10
@AdamBadura: Veuillez noter que std::coutc'est un argument de la fonction, ce qui suffit pour activer ADL. Avez-vous remarqué cela?
Nawaz
1
@meet: Votre question nécessite une réponse longue qui ne peut pas être fournie dans cet espace. Donc je ne peux que vous conseiller de lire sur des sujets tels que: 1) la signature de ostream<<(comme dans ce qu'elle prend comme arguments et ce qu'elle renvoie). 2) Noms complets (comme std::vectorou std::operator<<). 3) Une étude plus détaillée de la recherche dépendante de l'argument.
Nawaz
2
@WorldSEnder: Oui, vous avez raison. La fonction qui peut prendre std::endlcomme argument, est en fait une fonction membre. Quoi qu'il en soit, si j'utilise à la "\n"place de std::endl, ma réponse est correcte. Merci pour le commentaire.
Nawaz
2
@Destructor: Parce qu'un appel de fonction de la forme f(a,b)appelle une fonction libre . Donc, dans le cas de std::operator<<(std::cout, std::endl);, il n'y a pas de telle fonction libre qui prend std::endlcomme deuxième argument. C'est la fonction membre qui prend std::endlcomme argument, et pour laquelle vous devez écrire std::cout.operator<<(std::endl);. et comme il y a une fonction libre qui prend char const*comme second argument, "\n"fonctionne; '\n'fonctionnerait également.
Nawaz
30

Il vaut peut-être mieux commencer par le pourquoi, et ensuite seulement passer au comment.

Lorsque les espaces de noms ont été introduits, l'idée était que tout soit défini dans des espaces de noms, afin que des bibliothèques séparées n'interfèrent pas les unes avec les autres. Cependant, cela a introduit un problème avec les opérateurs. Regardez par exemple le code suivant:

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
  ???
}

Bien sûr, vous auriez pu écrire N::operator++(x), mais cela aurait vaincu le point de surcharge des opérateurs. Par conséquent, il fallait trouver une solution qui permettait au compilateur de trouver operator++(X&)malgré le fait qu'elle n'était pas dans la portée. D'un autre côté, il ne devrait toujours pas en trouver un autre operator++défini dans un autre espace de noms non lié qui pourrait rendre l'appel ambigu (dans cet exemple simple, vous n'obtiendrez pas d'ambiguïté, mais dans des exemples plus complexes, vous pourriez). La solution était la recherche dépendante de l'argument (ADL), appelée ainsi puisque la recherche dépend de l'argument (plus exactement, du type de l'argument). Depuis que le schéma a été inventé par Andrew R. Koenig, il est également souvent appelé recherche Koenig.

L'astuce est que pour les appels de fonction, en plus de la recherche de nom normale (qui trouve les noms dans la portée au point d'utilisation), il y a une seconde recherche dans les portées des types de tous les arguments donnés à la fonction. Ainsi , dans l'exemple ci - dessus, si vous écrivez x++dans le principal, il cherche operator++non seulement une portée mondiale, mais en plus dans le champ où le type de x, N::X, a été défini, par exemple dans namespace N. Et là, il trouve une correspondance operator++, et donc x++fonctionne tout simplement. Un autre operator++défini dans un autre espace de noms, par exemple N2, ne sera pas trouvé, cependant. Puisque ADL n'est pas limité aux espaces de noms, vous pouvez également utiliser à la f(x)place de N::f(x)in main().

celtschk
la source
Merci! Je n'ai jamais vraiment compris pourquoi c'était là!
user965369
20

À mon avis, tout n'est pas bon. Les gens, y compris les vendeurs de compilateurs, l'ont insulté à cause de son comportement parfois malheureux.

ADL est responsable d'une refonte majeure de la boucle for-range en C ++ 11. Pour comprendre pourquoi ADL peut parfois avoir des effets inattendus, considérez que non seulement les espaces de noms dans lesquels les arguments sont définis sont pris en compte, mais aussi les arguments des arguments modèles des arguments, des types de paramètres des types de fonction / des types pointee des types de pointeurs de ces arguments , et ainsi de suite.

Un exemple utilisant boost

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

Cela entraînait une ambiguïté si l'utilisateur utilise la bibliothèque boost.range, car les deux std::beginsont trouvés (par ADL en utilisant std::vector) et boost::beginsont trouvés (par ADL en utilisant boost::shared_ptr).

Johannes Schaub - litb
la source
Je me suis toujours demandé quel avantage il y avait à considérer les arguments de modèle en premier lieu.
Dennis Zickefoose
Est-il juste de dire que l'ADL n'est recommandé que pour les opérateurs et qu'il est préférable d'écrire explicitement les espaces de noms pour d'autres fonctions?
balki
Tient-il également compte des espaces de noms des classes de base d'arguments? (ce serait fou si c'était le cas, bien sûr).
Alex B
3
comment réparer? utilisez std :: begin?
paulm
2
@paulm Oui, std::beginefface l'ambiguïté de l'espace de noms.
Nikos