c++ - ¿Qué es la "Búsqueda dependiente del argumento"(también conocida como ADL o "Búsqueda Koenig")?

c++-faq

Question

¿Cuáles son algunas buenas explicaciones sobre qué argumento es la búsqueda dependiente? Mucha gente también lo llama Koenig Lookup también.

Preferiblemente me gustaría saber:

• ¿Por qué es algo bueno?
• ¿Por qué es algo malo?
• ¿Como funciona?

_{(Nota: Esto debe ser una entrada a las preguntas frecuentes de C ++ de Stack Overflow ).}

Answer 1

En Koenig Lookup, si se llama a una función sin especificar su espacio de nombre, entonces el nombre de una función también busca en el (los) espacio (s) de nombre en el que se define el tipo de argumento (s). Es por eso que también se conoce como búsqueda de nombre dependiente del argumento , en resumen, simplemente ADL .

Es por Koenig Lookup, podemos escribir esto:

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

De lo contrario, en ausencia de Koenig Lookup, tenemos que escribir:

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

¡lo cual es realmente demasiado tipeado y el código se ve realmente feo!

En otras palabras, en ausencia de Koenig Lookup, incluso un programa Hello World parece complicado.

Answer 2

No todo es bueno, en mi opinión. La gente, incluidos los vendedores de compiladores, lo han estado insultando debido a su comportamiento a veces desafortunado.

ADL es responsable de una importante revisión del ciclo for-range en C ++ 11. Para entender por qué ADL a veces puede tener efectos involuntarios, considere que se consideran no solo los espacios de nombres donde se definen los argumentos, sino también los argumentos de argumentos de plantilla de los argumentos, de tipos de parámetros de tipos de funciones / tipos de punta de tipos de punteros de esos argumentos , y así sucesivamente.

Un ejemplo usando boost

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

Esto dio lugar a una ambigüedad si el usuario usa la biblioteca boost.range, porque se encuentra std::begin (por ADL utilizando std::vector ) y boost::begin se encuentra (por ADL usando boost::shared_ptr ).

Answer 3

Tal vez sea mejor comenzar con el porqué, y solo entonces veamos cómo.

Cuando se introdujeron los espacios de nombres, la idea era tener todo definido en los espacios de nombres, de modo que las bibliotecas separadas no interfieran entre sí. Sin embargo, eso introdujo un problema con los operadores. Busque por ejemplo en el siguiente código:

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

Por supuesto, podría haber escrito N::operator++(x) , pero eso hubiera vencido al punto de sobrecarga del operador. Por lo tanto, se tenía que encontrar una solución que permitiera al compilador encontrar el operator++(X&) pesar de que no estaba dentro del alcance. Por otro lado, todavía no debería encontrar otro operator++ definido en otro espacio de nombres no relacionado que podría hacer que la llamada sea ambigua (en este ejemplo simple, no obtendría ambigüedad, pero en ejemplos más complejos, podría). La solución fue Argument Dependent Lookup (ADL), llamado así porque la búsqueda depende del argumento (más exactamente, en el tipo del argumento). Dado que el esquema fue inventado por Andrew R. Koenig, también se lo denomina búsqueda Koenig.

El truco es que para las llamadas a funciones, además de la búsqueda normal de nombres (que encuentra nombres en el alcance en el punto de uso), se realiza una segunda búsqueda en los ámbitos de los tipos de argumentos dados a la función. Entonces, en el ejemplo anterior, si escribe x++ en main, busca operator++ no solo en alcance global, sino también en el ámbito donde se definió el tipo de x , N::X , es decir, en el namespace N de namespace N Y allí encuentra un operator++ juego operator++ , y por lo tanto, x++ simplemente funciona. Sin embargo, no se encontrará otro operator++ definido en otro espacio de nombres, digamos N2 . Como ADL no está restringido a espacios de nombres, también puede usar f(x) lugar de N::f(x) en main() .

Answer 4

Koenig Lookup también se conoce comúnmente como Argument Dependent Lookup en C ++ y la mayoría de los compiladores estándar de C ++ lo admiten.

El estándar C ++ 11 § 3.4.2 / 1 establece:

Cuando la expresión postfix en una llamada a función (5.2.2) es una identificación no calificada, se pueden buscar otros espacios de nombres no considerados durante la búsqueda no calificada habitual (3.4.1), y en esos espacios de nombres, declaraciones de función de espacio de espacio de nombres ( 11.3) no visible de otro modo se puede encontrar. Estas modificaciones en la búsqueda dependen de los tipos de argumentos (y para los argumentos de la plantilla de plantilla, el espacio de nombres del argumento de la plantilla).

En términos más simples, Nicolai Josuttis dice ¹ :

No es necesario que califique el espacio de nombres para funciones si uno o más tipos de argumentos están definidos en el espacio de nombres de la función.

Un simple ejemplo de código:

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

MyNamespace::MyClass obj; // global object


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

En el ejemplo anterior, no hay ni una using-declaration ni una using-directive pero el compilador identifica correctamente el nombre no calificado doSomething() como la función declarada en el espacio de nombres MyNamespace aplicando el algoritmo de Koenig .

¿Como funciona?
El algoritmo le dice al compilador que no solo mire el alcance local, sino también los espacios de nombres que contienen el tipo de argumento. Por lo tanto, en el código anterior, el compilador encuentra que el objeto obj , que es el argumento de la función doSomething() , pertenece al espacio de nombres MyNamespace . Entonces, mira ese espacio de nombres para ubicar la declaración de doSomething() .

¿Cuál es la ventaja de Koenig Lookup ?
Como muestra el ejemplo del código simple anterior, el Algoritmo Koenig brinda comodidad y facilidad de uso al programador. Sin Koenig Algorithm, habría una sobrecarga en el programador, para especificar repetidamente los nombres completos, o en su lugar, utilizar numerosas declaraciones de uso.

¿Por qué la crítica de Koenig Algorithm ?
La dependencia excesiva del Algoritmo Koenig puede provocar problemas semánticos y, a veces, sorprender al programador.

Considere el ejemplo de std::swap , que es un algoritmo de biblioteca estándar para intercambiar dos valores. Con el algoritmo de Koenig uno debería tener cuidado al usar este algoritmo porque:

std::swap(obj1,obj2);    

no puede mostrar el mismo comportamiento que:

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

Con ADL, qué versión de la función de swap se llama dependerá del espacio de nombres de los argumentos que se le pasen.
Si existe un espacio de nombres A y si A::obj1 , A::obj2 y A::swap() , el segundo ejemplo dará como resultado una llamada a A::swap() que podría no ser lo que el usuario quería.

Además, si por alguna razón ambos:
A::swap(A::MyClass&, A::MyClass&) y std::swap(A::MyClass&, A::MyClass&) están definidos, luego el primer ejemplo llamará a std::swap(A::MyClass&, A::MyClass&) pero el segundo no compilará porque swap(obj1, obj2) sería ambiguo.

Trivialidades:
¿Por qué se llama Koenig Lookup ?
Porque fue ideado por el ex investigador y programador de AT & T y Bell Labs, Andrew Koenig .

Buenas lecturas:

gotw.ca/gotw/030.htm
Estándar C ++ 03/11 [basic.lookup.argdep]: 3.4.2 Búsqueda de nombre dependiente del argumento.

_{¹ La definición de Koenig Algorithm es como se define en el libro de Josuttis, The C ++ Standard Library: A Tutorial and Reference .}