O que é "Pesquisa Dependente de Argumento" (aka ADL, ou "Koenig Lookup")?

176

Quais são algumas boas explicações sobre o que é a pesquisa dependente de argumento? Muitas pessoas também chamam de Koenig Lookup.

De preferência, gostaria de saber:

  • Por que isso é uma coisa boa?
  • Por que isso é uma coisa ruim?
  • Como funciona?
user965369
fonte

Respostas:

223

A Pesquisa Koenig , ou Pesquisa Dependente de Argumento , descreve como os nomes não qualificados são pesquisados ​​pelo compilador no C ++.

O padrão C ++ 11, § 3.4.2 / 1, declara:

Quando a expressão postfix em uma chamada de função (5.2.2) é um ID não qualificado, outros espaços para nome não considerados durante a pesquisa não qualificada usual (3.4.1) podem ser pesquisados ​​e, nesses espaços para nome, declarações de função de amigo no escopo do espaço para nome ( 11.3) não visível de outra forma pode ser encontrado. Essas modificações na pesquisa dependem dos tipos dos argumentos (e dos argumentos do modelo, o espaço para nome do argumento do modelo).

Em termos mais simples, Nicolai Josuttis afirma 1 :

Você não precisa qualificar o espaço para nome para funções se um ou mais tipos de argumento estiverem definidos no espaço para nome da função.

Um exemplo de código simples:

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

MyNamespace::MyClass obj; // global object


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

No exemplo acima, não há uma usingdeclaração-nem um diretório, usingmas ainda assim o compilador identifica corretamente o nome não qualificado doSomething()como a função declarada no espaço para nome MyNamespaceaplicando a pesquisa Koenig .

Como funciona?

O algoritmo diz ao compilador para não apenas examinar o escopo local, mas também os espaços para nome que contêm o tipo do argumento. Assim, no código acima, o compilador descobre que o objeto obj, que é o argumento da função doSomething(), pertence ao espaço para nome MyNamespace. Portanto, ele olha para esse espaço para nome para localizar a declaração de doSomething().

Qual é a vantagem da pesquisa Koenig?

Como o exemplo de código simples acima demonstra, a pesquisa Koenig oferece conveniência e facilidade de uso ao programador. Sem a pesquisa de Koenig, haveria uma sobrecarga no programador, para especificar repetidamente os nomes totalmente qualificados ou, em vez disso, usar várias usingdeclarações -.

Por que as críticas à pesquisa de Koenig?

O excesso de confiança na pesquisa de Koenig pode levar a problemas semânticos e, às vezes, pegar o programador desprevenido.

Considere o exemplo de std::swap, que é um algoritmo de biblioteca padrão para trocar dois valores. Com a pesquisa de Koenig, seria preciso ter cuidado ao usar esse algoritmo, porque:

std::swap(obj1,obj2);

pode não mostrar o mesmo comportamento que:

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

Com o ADL, qual versão da swapfunção é chamada dependeria do espaço para nome dos argumentos passados ​​para ele.

Se existe um espaço de nomes Ae se A::obj1, A::obj2e A::swap()existem, em seguida, o segundo exemplo irá resultar em uma chamada para A::swap(), que pode não ser o que o usuário queria.

Além disso, se por algum motivo tanto A::swap(A::MyClass&, A::MyClass&)e std::swap(A::MyClass&, A::MyClass&)são definidos, em seguida, o primeiro exemplo chamará std::swap(A::MyClass&, A::MyClass&)mas o segundo não irá compilar, porque swap(obj1, obj2)seria ambíguo.

Curiosidades:

Por que é chamado de "pesquisa Koenig"?

Porque foi desenvolvido pelo ex-pesquisador e programador da AT&T e Bell Labs, Andrew Koenig .

Leitura adicional:


1 A definição da pesquisa de Koenig é a definida no livro de Josuttis, The C ++ Standard Library: A Tutorial and Reference .

Alok Save
fonte
11
@AlokSave: +1 para a resposta, mas as curiosidades não estão corretas. Koenig não inventou ADL, como ele confessa aqui :)
legends2k
20
O exemplo das críticas ao algoritmo de Koenig pode ser considerado um "recurso" da pesquisa de Koenig, tanto quanto um "golpe". Usar std :: swap () dessa maneira é um idioma comum: forneça um 'using std :: swap ()' caso uma versão mais especializada A :: swap () não seja fornecida. Se uma versão especializada do A :: swap () estiver disponível, nós normalmente queremos que essa seja chamada. Isso fornece mais genicidade para a chamada swap (), pois podemos confiar na chamada para compilar e trabalhar, mas também podemos confiar na versão mais especializada a ser usada, se houver uma.
Anthony Hall
6
@anthrond Há mais sobre isso. Com std::swapvocê, na verdade, é necessário fazer isso, pois a única alternativa seria adicionar a std::swapfunção de modelo de especialização explícita para sua Aclasse. No entanto, se sua Aclasse for um modelo em si, seria especialização parcial, e não explícita. E a especialização parcial da função de modelo não é permitida. Adicionar sobrecarga de std::swapseria uma alternativa, mas é explicitamente proibido (você não pode adicionar coisas ao stdespaço para nome). Portanto, o ADL é o único caminho std::swap.
21915 Adam Aduraura
1
Eu esperava ver uma menção de operadores sobrecarregados sob "vantagem da pesquisa koenig". o exemplo com std::swap()parece um pouco para trás. Eu esperaria que o problema seja quando std::swap()for selecionado, e não a sobrecarga específica para o tipo A::swap(). O exemplo com std::swap(A::MyClass&, A::MyClass&)parece enganador. como stdnunca haveria uma sobrecarga específica para um tipo de usuário, não acho que seja um ótimo exemplo.
Arvid #
1
@gsamaras ... E? Todos nós podemos ver que a função nunca foi definida. Sua mensagem de erro prova que funcionou, na verdade, porque está procurando MyNamespace::doSomething, não apenas ::doSomething.
Fund Monica's Lawsuit
69

Na Pesquisa Koenig, se uma função é chamada sem especificar seu espaço para nome, o nome de uma função também é pesquisado no (s) espaço (s) de nomes no qual o tipo de argumento (s) está definido. É por isso que também é conhecido como pesquisa de nome dependente de argumento , em resumo simplesmente ADL .

É por causa da pesquisa Koenig, podemos escrever o seguinte:

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

Caso contrário, teríamos que escrever:

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

o que realmente é muita digitação e o código parece realmente feio!

Em outras palavras, na ausência do Koenig Lookup, até mesmo um programa Hello World parece complicado.

Nawaz
fonte
12
Exemplo persuasivo.
Anthony Hall
10
@ AdamBadura: Observe que esse std::couté um argumento para a função, o suficiente para ativar a ADL. Você percebeu isso?
Nawaz
1
@meet: Sua pergunta precisa de uma resposta longa que não possa ser fornecida neste espaço. Portanto, só posso aconselhá-lo a ler sobre tópicos como: 1) assinatura de ostream<<(como no que leva como argumento e no que ele retorna). 2) Nomes totalmente qualificados (como std::vectorou std::operator<<). 3) Um estudo mais detalhado da Pesquisa Dependente de Argumento.
Nawaz 27/05
2
@WorldSEnder: Sim, você está certo. A função que pode ser std::endlusada como argumento é na verdade uma função de membro. Enfim, se eu usar em "\n"vez de std::endl, então minha resposta está correta. Obrigado pelo comentário.
Nawaz
2
@ Destructor: Porque uma chamada de função da forma de f(a,b)invoca uma função livre . Portanto, no caso de std::operator<<(std::cout, std::endl);, não existe essa função livre que leva std::endlcomo segundo argumento. É a função de membro que assume std::endlcomo argumento e para a qual você deve escrever std::cout.operator<<(std::endl);. e uma vez que existe uma função livre que assume char const*como segundo argumento, "\n"funciona; '\n'funcionaria também.
Nawaz
30

Talvez seja melhor começar com o porquê e só depois ir para o como.

Quando os espaços para nome foram introduzidos, a idéia era ter tudo definido nos espaços para nome, para que bibliotecas separadas não interferissem entre si. No entanto, isso introduziu um problema com os operadores. Veja, por exemplo, o seguinte 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
  ???
}

Claro que você poderia ter escrito N::operator++(x), mas isso teria derrotado todo o ponto de sobrecarga do operador. Portanto, uma solução teve que ser encontrada, o que permitiu ao compilador encontrar, operator++(X&)apesar de não estar no escopo. Por outro lado, ainda não deve encontrar outrooperator++ definido em outro espaço de nome não relacionado que possa tornar a chamada ambígua (neste exemplo simples, você não obteria ambiguidade, mas em exemplos mais complexos, talvez). A solução foi a Pesquisa Dependente de Argumento (ADL), chamada dessa maneira, pois a pesquisa depende do argumento (mais exatamente, do tipo do argumento). Desde que o esquema foi inventado por Andrew R. Koenig, também é chamado de pesquisa Koenig.

O truque é que, para chamadas de função, além da pesquisa normal de nomes (que encontra nomes no escopo no ponto de uso), é feita uma segunda pesquisa nos escopos dos tipos de argumentos fornecidos à função. Assim, no exemplo acima, se você escrever x++no principal, ele procura operator++não só no âmbito global, mas além disso, no âmbito onde o tipo de x, N::X, foi definida, ou seja, namespace N. E lá encontra uma correspondência operator++e, portanto, x++simplesmente funciona. Outro operator++definido em outro espaço para nome, por exemplo N2, não será encontrado. Como a ADL não está restrita a espaços para nome, você também pode usar em f(x)vez de N::f(x)em main().

celtschk
fonte
Obrigado! Nunca realmente entendi por que estava lá!
user965369
20

Nem tudo é bom, na minha opinião. Pessoas, incluindo fornecedores de compiladores, o insultam por causa de seu comportamento às vezes infeliz.

A ADL é responsável por uma grande revisão do loop for-range no C ++ 11. Para entender por que a ADL às vezes pode ter efeitos não intencionais, considere que não apenas os espaços para nome em que os argumentos são definidos são considerados, mas também os argumentos dos argumentos de modelo dos argumentos, dos tipos de parâmetros dos tipos de função / tipos de ponta dos tipos de ponteiro desses argumentos e assim por diante.

Um exemplo usando boost

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

Isso resultou em uma ambiguidade se o usuário usar a biblioteca boost.range, porque ambos std::beginsão encontrados (pelo ADL usando std::vector) e boost::beginencontrados (pelo ADL usando boost::shared_ptr).

Johannes Schaub - litb
fonte
Sempre me perguntei que benefício há em considerar argumentos de modelo em primeiro lugar.
Dennis Zickefoose
É justo dizer que o ADL é recomendado apenas para operadores e é melhor escrever explicitamente os namespaces para outras funções?
balki
Também considera os namespaces das classes base de argumentos? (isso seria louco, se o fizer, é claro).
Alex B
3
como consertar? use std :: begin?
paulm
2
@paulm Sim, std::beginlimpa a ambiguidade do espaço para nome.
Nikos