Pertanyaan Mengapa menggunakan std :: less sebagai fungsi default untuk membandingkan kunci di std :: map dan std :: set?


Saya bertanya-tanya mengapa std::map dan std::set menggunakan std::less sebagai fungsi standar untuk membandingkan kunci. Mengapa tidak menggunakan functor yang berfungsi mirip dengan strcmp? Sesuatu seperti:

  template <typename T> struct compare
  {
     // Return less than 0 if lhs < rhs
     // Return 0 if lhs == rhs
     // Return greater than 0 if lhs > rhs
     int operator()(T const& lhs, T const& rhs)
     {
        return (lhs-rhs);
     }
  }

Katakan a map memiliki dua objek di dalamnya, dengan kunci key1 dan key2. Sekarang kita ingin memasukkan objek lain dengan kunci key3.

Ketika menggunakan std::less, yang insert fungsi perlu panggilan pertama std::less::operator() dengan key1 dan key3. Menganggap std::less::operator()(key1, key3) mengembalikan salah. Itu harus dihubungi std::less::operator() lagi dengan tombol-tombol yang ditukar, std::less::operator()(key3, key1), untuk memutuskan apakah key1 adalah sama dengan key3 atau key3 lebih besar dari key1. Ada dua panggilan ke std::less::operator() untuk membuat keputusan jika panggilan pertama menghasilkan kesalahan.

Hadir std::map::insert bekas compare, akan ada cukup informasi untuk membuat keputusan yang tepat hanya dengan satu panggilan.

Tergantung pada jenis kunci di peta, std::less::operator()(key1, key2) bisa jadi mahal.

Kecuali saya kehilangan sesuatu yang sangat mendasar, tidak seharusnya std::map dan std::set gunakan sesuatu seperti compare dari pada std::less sebagai fungsi standar untuk membandingkan kunci?


32
2018-03-10 18:33


asal


Jawaban:


Saya memutuskan untuk bertanya kepada Alexander Stepanov (perancang STL) tentang hal ini. Saya diizinkan mengutipnya sebagai berikut:

Awalnya, saya mengusulkan perbandingan 3 arah. Komite standar bertanya     saya berubah menjadi operator perbandingan standar. Saya melakukan apa yang diperintahkan kepada saya.     Saya telah menganjurkan menambahkan komponen 3-way ke standar untuk     lebih dari 20 tahun.

Tetapi perhatikan bahwa mungkin tidak intuitif, 2 arah bukanlah overhead yang besar. Anda tidak perlu membuat perbandingan dua kali lebih banyak. Ini hanya satu perbandingan per node dalam perjalanan ke bawah (tidak ada pemeriksaan kesetaraan). Biaya tidak dapat kembali lebih awal (ketika kuncinya adalah non-daun) dan satu perbandingan tambahan di akhir (menukar argumen untuk memeriksa kesetaraan). Jika saya tidak salah, itu membuatnya

1 + 1/2*1 + 1/4*2 + 1/8*3 + ...
= 1 + 1/2+1/4+1/8+... + 1/4+1/8+... + ...
-> 3  (depth -> infty)

perbandingan tambahan rata-rata pada pohon seimbang yang mengandung elemen tanya.

Di sisi lain, perbandingan 3-arah tidak memiliki overhead yang buruk: Branchless 3-way integer comparison. Sekarang apakah cabang tambahan untuk memeriksa hasil perbandingan terhadap 0 (kesetaraan) di setiap node lebih rendah daripada membayar ~ 3 perbandingan tambahan di akhir adalah pertanyaan lain. Mungkin tidak terlalu penting. Tapi saya pikir perbandingan itu sendiri seharusnya bernilai 3, sehingga keputusan apakah akan menggunakan semua 3 hasil dapat diubah.

Pembaruan: Lihat komentar di bawah karena alasan saya menganggap perbandingan 3 arah lebih baik di pohon, tetapi tidak harus dalam bentuk datar.


20
2018-05-04 03:11



Wadah berbasis pohon hanya membutuhkan Ketat Total Pemesanan Yang Ketat.

Lihat https://www.sgi.com/tech/stl/StrictWeakOrdering.html

  1. akses tulis

    Titik penyisipan untuk peta dan set sepenuhnya ditentukan oleh satu pencarian biner, mis. lower_bound atau upper_bound. Kompleksitas runtime pencarian biner adalah O(log n)

  2. akses baca

    Hal yang sama berlaku untuk pencarian: pencarian jauh lebih efisien daripada pemindaian kesetaraan linear, justru karena sebagian besar elemen tidak perlu dibandingkan. Triknya adalah bahwa kontainernya sudah dipesan.


Hasilnya adalah bahwa equality informasi tidak perlu hadir. Hanya, barang-barang itu bisa pemesanan setara.

Dalam prakteknya ini hanya berarti lebih sedikit kendala pada jenis elemen Anda, lebih sedikit pekerjaan untuk menerapkan persyaratan dan kinerja optimal dalam skenario penggunaan umum. Akan selalu ada trade-off. (Misalnya untuk koleksi besar, tabel hash (tidak dipesan set dan peta) seringkali lebih efisien. Perhatikan bahwa ini melakukan memerlukan equatable elemen, dan mereka menggunakan skema hashing untuk pencarian cepat)


17
2018-03-10 19:31