Apa itu "Argumen-Dependent Lookup" (alias ADL, atau "Koenig Lookup")?

176

Apa saja penjelasan yang baik tentang apa pencarian bergantung pada argumen? Banyak orang juga menyebutnya Koenig Lookup juga.

Lebih disukai saya ingin tahu:

  • Mengapa ini hal yang baik?
  • Kenapa itu hal yang buruk?
  • Bagaimana cara kerjanya?
pengguna965369
sumber

Jawaban:

223

Koenig Lookup , atau Argument Dependent Lookup , menjelaskan bagaimana nama yang tidak memenuhi syarat dicari oleh kompiler di C ++.

Standar C ++ 11 § 3.4.2 / 1 menyatakan:

Ketika ekspresi postfix dalam panggilan fungsi (5.2.2) adalah id yang tidak memenuhi syarat, ruang nama lain yang tidak dipertimbangkan selama pencarian biasa tanpa pengecualian (3.4.1) dapat dicari, dan di ruang nama tersebut, deklarasi fungsi namespace-lingkup teman ( 11.3) tidak terlihat dapat ditemukan. Modifikasi untuk pencarian ini bergantung pada jenis argumen (dan untuk argumen templat templat, namespace argumen templat).

Dalam istilah yang lebih sederhana, Nicolai Josuttis menyatakan 1 :

Anda tidak harus memenuhi syarat namespace untuk fungsi jika satu atau lebih tipe argumen didefinisikan dalam namespace fungsi.

Contoh kode sederhana:

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

MyNamespace::MyClass obj; // global object


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

Dalam contoh di atas tidak ada using-deklarasi atau -direktif usingtetapi masih kompiler dengan benar mengidentifikasi nama yang tidak memenuhi syarat doSomething()sebagai fungsi yang dinyatakan dalam namespaceMyNamespace dengan menerapkan pencarian Koenig .

Bagaimana cara kerjanya?

Algoritma memberitahu kompiler untuk tidak hanya melihat lingkup lokal, tetapi juga ruang nama yang berisi tipe argumen. Jadi, dalam kode di atas, kompiler menemukan bahwa objek obj, yang merupakan argumen fungsi doSomething(), adalah milik namespace MyNamespace. Jadi, terlihat di namespace itu untuk menemukan deklarasidoSomething() .

Apa keuntungan dari pencarian Koenig?

Seperti yang ditunjukkan contoh kode sederhana di atas, pencarian Koenig memberikan kemudahan dan kemudahan penggunaan bagi programmer. Tanpa pencarian Koenig akan ada overhead pada programmer, untuk berulang kali menentukan nama-nama yang memenuhi syarat, atau sebaliknya, menggunakan banyakusing -deklarasian.

Mengapa kritik terhadap pencarian Koenig?

Ketergantungan yang berlebihan pada pencarian Koenig dapat menyebabkan masalah semantik, dan terkadang membuat programmer lengah.

Pertimbangkan contoh std::swap, yang merupakan algoritma perpustakaan standar untuk bertukar dua nilai. Dengan pencarian Koenig kita harus berhati-hati saat menggunakan algoritma ini karena:

std::swap(obj1,obj2);

mungkin tidak menunjukkan perilaku yang sama dengan:

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

Dengan ADL, versi mana dari swap fungsi mana yang dipanggil akan bergantung pada namespace argumen yang diteruskan ke sana.

Jika ada namespace Adan jika A::obj1, A::obj2& A::swap()ada maka contoh kedua akan menghasilkan panggilan keA::swap() , yang mungkin bukan yang diinginkan pengguna.

Selanjutnya, jika karena alasan kedua A::swap(A::MyClass&, A::MyClass&)dan std::swap(A::MyClass&, A::MyClass&)didefinisikan, maka contoh pertama akan memanggil std::swap(A::MyClass&, A::MyClass&)tapi yang kedua tidak akan dikompilasi karena swap(obj1, obj2)akan ambigu.

Hal sepele:

Kenapa disebut "Koenig lookup"?

Karena itu dirancang oleh mantan AT&T dan peneliti dan programmer Bell Labs, Andrew Koenig .

Bacaan lebih lanjut:


1 Definisi pencarian Koenig adalah seperti yang didefinisikan dalam buku Josuttis, The C ++ Standard Library: A Tutorial and Reference .

Alok Simpan
sumber
11
@AlokSave: +1 untuk jawabannya, tetapi hal-hal sepele tidak benar. Koenig tidak menciptakan ADL, karena ia mengaku di sini :)
legends2k
20
Contoh dalam kritik terhadap Algoritma Koenig dapat dianggap sebagai "fitur" dari pencarian Koenig sebanyak "penipu". Menggunakan std :: swap () sedemikian rupa adalah idiom yang umum: Berikan 'using std :: swap ()' jika versi yang lebih terspesialisasi A :: swap () tidak disediakan. Jika versi khusus dari A :: swap () tersedia, kami biasanya ingin yang itu dipanggil. Ini memberikan lebih banyak generalisasi untuk panggilan swap (), karena kami dapat memercayai panggilan untuk mengkompilasi dan bekerja, tetapi kami juga dapat mempercayai versi yang lebih khusus untuk digunakan jika ada.
Anthony Hall
6
@ Anthond Ada lagi ke dalam ini. Dengan std::swapAnda benar-benar harus melakukan itu karena satu-satunya alternatif adalah menambahkan std::swapfungsi template spesialisasi eksplisit untuk Akelas Anda . Namun jika Akelas Anda adalah templat itu sendiri, itu akan menjadi spesialisasi parsial daripada spesialisasi eksplisit. Dan sebagian spesialisasi fungsi templat tidak diperbolehkan. Menambahkan kelebihan std::swapakan menjadi alternatif tetapi dilarang secara eksplisit (Anda tidak boleh menambahkan sesuatu ke stdnamespace). Jadi ADL adalah satu-satunya cara untuk std::swap.
Adam Badura
1
Saya akan berharap untuk melihat menyebutkan operator kelebihan beban di bawah "keuntungan pencarian koenig". contoh dengan std::swap()sepertinya agak mundur. Saya mengharapkan masalah yang terjadi ketika std::swap()dipilih daripada kelebihan spesifik untuk tipe A::swap(),. Contoh dengan std::swap(A::MyClass&, A::MyClass&)sepertinya menyesatkan. karena stdtidak akan pernah memiliki kelebihan spesifik untuk tipe pengguna, saya tidak berpikir itu adalah contoh yang bagus.
Arvid
1
@gsamaras ... Dan? Kita semua dapat melihat bahwa fungsi tidak pernah didefinisikan. Pesan kesalahan Anda membuktikan bahwa itu berfungsi, sebenarnya, karena sedang dicari MyNamespace::doSomething, bukan hanya ::doSomething.
Dana Gugatan Monica
69

Di Koenig Lookup, jika suatu fungsi dipanggil tanpa menentukan namespace-nya, maka nama fungsi juga dicari di namespace (s) di mana tipe argumen didefinisikan. Itu sebabnya juga dikenal sebagai nama pencarian Argument-Dependent , singkatnya hanya ADL .

Itu karena Koenig Lookup, kita dapat menulis ini:

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

Kalau tidak, kita harus menulis:

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

yang benar-benar terlalu banyak mengetik dan kode terlihat sangat jelek!

Dengan kata lain, dengan tidak adanya Koenig Lookup, bahkan program Hello World terlihat rumit.

Nawaz
sumber
12
Contoh persuasif.
Anthony Hall
10
@AdamBadura: Harap dicatat bahwa std::coutini adalah satu argumen untuk fungsi tersebut, yang cukup untuk mengaktifkan ADL. Apakah kamu memperhatikan itu?
Nawaz
1
@ bertemu: Pertanyaan Anda membutuhkan jawaban panjang yang tidak dapat disediakan di ruang ini. Jadi saya hanya bisa menyarankan Anda untuk membaca topik seperti: 1) tanda tangan ostream<<(seperti apa yang diperlukan sebagai argumen dan apa yang dikembalikan). 2) Nama yang sepenuhnya memenuhi syarat (seperti std::vectoratau std::operator<<). 3) Studi yang lebih rinci tentang Argument Dependent Lookup.
Nawaz
2
@ WorldSEnder: Ya, Anda benar. Fungsi yang dapat dianggap std::endlsebagai argumen, sebenarnya adalah fungsi anggota. Lagi pula, jika saya menggunakan "\n"alih-alih std::endl, maka jawaban saya sudah benar. Terima kasih atas komentarnya.
Nawaz
2
@Destructor: Karena panggilan fungsi dalam bentuk f(a,b)memanggil fungsi gratis . Jadi dalam hal std::operator<<(std::cout, std::endl);, tidak ada fungsi bebas seperti itu yang mengambil std::endlargumen kedua. Ini adalah fungsi anggota yang mengambil std::endlsebagai argumen, dan untuk itulah Anda harus menulis std::cout.operator<<(std::endl);. dan karena ada fungsi bebas yang char const*menjadi argumen kedua, "\n"berfungsi;'\n'akan bekerja juga.
Nawaz
30

Mungkin yang terbaik adalah memulai dengan alasannya, dan baru kemudian menuju ke caranya.

Ketika ruang nama diperkenalkan, idenya adalah untuk memiliki segalanya didefinisikan dalam ruang nama, sehingga perpustakaan yang terpisah tidak saling mengganggu. Namun itu menimbulkan masalah dengan operator. Lihat misalnya pada kode berikut:

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

Tentu saja Anda bisa menulis N::operator++(x), tetapi itu akan mengalahkan seluruh titik kelebihan operator. Oleh karena itu solusi harus ditemukan yang memungkinkan kompiler untuk menemukan operator++(X&)terlepas dari kenyataan bahwa itu tidak dalam ruang lingkup. Di sisi lain, masih tidak harus menemukan yang lainoperator++ didefinisikan dalam ruang nama lain yang tidak terkait yang dapat membuat panggilan ambigu (dalam contoh sederhana ini, Anda tidak akan mendapatkan ambiguitas, tetapi dalam contoh yang lebih kompleks, Anda mungkin). Solusinya adalah Argument Dependent Lookup (ADL), disebut demikian karena pencarian tergantung pada argumen (lebih tepatnya, pada tipe argumen). Karena skema ini ditemukan oleh Andrew R. Koenig, itu juga sering disebut pencarian Koenig.

Kuncinya adalah bahwa untuk panggilan fungsi, selain pencarian nama normal (yang menemukan nama dalam lingkup pada titik penggunaan), dilakukan pencarian kedua dalam lingkup jenis argumen yang diberikan ke fungsi. Jadi dalam contoh di atas, jika Anda menulis x++di utama, tampaknya untuk operator++tidak hanya di lingkup global, tetapi juga dalam lingkup di mana jenis x, N::X, didefinisikan, yaitu di namespace N. Dan di sana ia menemukan yang cocok operator++, dan karena itu x++berfungsi. Namun, yang operator++didefinisikan di namespace lain N2tidak akan ditemukan. Karena ADL tidak terbatas pada ruang nama, Anda juga dapat menggunakan f(x)bukannya N::f(x)di main().

celtschk
sumber
Terima kasih! Tidak pernah benar-benar mengerti mengapa itu ada di sana!
user965369
20

Tidak semuanya baik, menurut saya. Orang-orang, termasuk vendor penyusun, telah menghinanya karena perilakunya yang terkadang tidak menguntungkan.

ADL bertanggung jawab untuk perombakan besar untuk for-range loop di C ++ 11. Untuk memahami mengapa ADL kadang-kadang dapat memiliki efek yang tidak diinginkan, pertimbangkan bahwa tidak hanya ruang nama tempat argumen didefinisikan dipertimbangkan, tetapi juga argumen argumen templat argumen, dari tipe parameter tipe fungsi / pointee jenis tipe pointer dari argumen tersebut , dan sebagainya.

Contoh menggunakan boost

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

Ini menghasilkan ambiguitas jika pengguna menggunakan perpustakaan boost.range, karena keduanya std::beginditemukan (menggunakan ADL std::vector) dan boost::beginditemukan (menggunakan ADL boost::shared_ptr).

Johannes Schaub - litb
sumber
Saya selalu bertanya-tanya apa manfaatnya untuk mempertimbangkan argumen templat di tempat pertama.
Dennis Zickefoose
Apakah adil untuk mengatakan ADL direkomendasikan hanya untuk operator dan lebih baik menulis ruang nama secara eksplisit untuk fungsi lain?
balki
Apakah itu juga mempertimbangkan ruang nama dari kelas dasar argumen? (Itu akan menjadi gila jika ya, tentu saja).
Alex B
3
bagaimana cara memperbaiki? gunakan std :: begin?
paulm
2
@ paulm Ya, std::beginmenghapus ambiguitas namespace.
Nikos