Pertanyaan Mengapa tidak ada kelebihan dari find / lower_bound untuk std :: map dan tidak ada kelebihan dari sort untuk std :: list?


Saya tahu bahwa Anda tidak boleh menggunakannya std::find(some_map.begin(), some_map.end()) atau std::lower_bound, karena akan membutuhkan waktu linier dan bukan logaritma yang disediakan oleh some_map.lower_bound. Hal serupa terjadi dengan std::list: ada std::list::sort berfungsi untuk menyortir, tetapi Anda tidak dapat memanggil std::sort(some_list.begin(), some_list.end()), karena iterator bukanlah akses acak.

Namun, std::swap, misalnya, memiliki overload untuk kontainer standar, sehingga panggilan swap(some_map, other_map) mengambil O (1), bukan O (n). Mengapa standar C ++ tidak memberi kita versi khusus lower_bound dan find untuk peta dan set? Apakah ada alasan yang mendalam?


5
2018-03-07 20:01


asal


Jawaban:


Saya tidak berpikir ada alasan yang mendalam, tapi lebih filosofis dari apapun. Bentuk fungsi bebas dari algoritma standar, termasuk yang Anda sebutkan, mengambil pasangan iterator yang menunjukkan rentang di mana mereka akan melintasi. Tidak ada cara bagi algoritma untuk menentukan jenis wadah yang mendasari dari iterator ini.

Menyediakan spesialisasi, atau kelebihan beban, akan menjadi keberangkatan dari model ini karena Anda harus meneruskan penampung itu sendiri ke algoritme.

swap berbeda karena itu mengambil contoh dari jenis yang terlibat sebagai argumen, dan bukan hanya iterator.


5
2018-03-07 20:07



Aturan yang diikuti oleh STL adalah bahwa algoritma fungsi bebas beroperasi pada iterator dan generik, tidak peduli tentang jenis jangkauan iterators milik (selain kategori iterator). Jika jenis kontainer tertentu dapat menerapkan operasi lebih efisien daripada menggunakan std::algo(cont.begin(), cont.end()) maka operasi itu disediakan sebagai fungsi anggota wadah dan disebut sebagai cont.algo().

Jadi kamu punya std::map<>::lower_bound() dan std::map<>::find() dan std::list<>::sort().


3
2018-03-07 20:16



Fakta sederhana bahwa fungsi-fungsi tersebut harus bekerja dalam hal pasangan iterator akan menghasilkan overhead yang cukup signifikan, bahkan jika khusus untuk map / set iterators.

Perlu diingat bahwa:

  • Fungsi-fungsi tersebut dapat disebut dengan sepasang iterator, bukan hanya awal / akhir.

  • Iterator peta / set biasanya diimplementasikan sebagai penunjuk ke a daun simpul, sementara simpul awal dari anggota find/lower_bound adalah akar simpul pohon.

Memiliki anggota find dan lower_bound lebih baik, karena pointer ke root node secara langsung disimpan sebagai anggota objek peta / set.

Seorang non-anggota hipotetis find harus melintasi pohon untuk menemukan leluhur bersama terendah antara dua node input, dan kemudian melakukan dfs - sementara masih berhati-hati untuk mencari hanya dalam kisaran [pertama, terakhir] - yang secara signifikan lebih mahal.

Ya, Anda dapat melacak node root di dalam iterator, kemudian mengoptimalkan jika fungsi dipanggil dengan pasangan awal / akhir ... hanya untuk menghindari fungsi anggota?


2
2018-03-07 21:17



Ada alasan "filosofi desain" yang bagus untuk tidak menyediakan mereka yang terlalu banyak. Secara khusus, seluruh interaksi kontainer / algoritma STL dirancang untuk melalui berbagai konsep iterator yang berbeda sehingga kedua bagian tersebut tetap independen, sehingga Anda dapat menentukan jenis penampung baru tanpa harus membebani semua algoritme, dan sehingga Anda dapat menentukan algoritma baru tanpa harus membebani semua kontainer.

Di luar pilihan desain tersebut, ada alasan teknis yang sangat bagus mengapa algoritme ini (sortir, batas bawah, dll.) Tidak dapat diisi berlebih untuk wadah khusus seperti list atau map / set. Alasannya adalah bahwa pada umumnya tidak ada alasan untuk iterator untuk secara eksplisit terhubung ke wadah induknya. Dengan kata lain, Anda bisa mendapatkan daftar iterator (mulai / akhir) dari daftar penampung, tetapi Anda tidak dapat memperoleh (referensi ke) wadah daftar dari daftar iterator. Hal yang sama berlaku untuk map / set iterators. Iterator dapat diimplementasikan menjadi "buta" untuk wadah induk mereka. Misalnya, wadah seperti list biasanya berisi, sebagai anggota data, pointer ke kepala dan simpul ekor, dan objek alokator, tetapi iterator itu sendiri (biasanya hanya pointer ke node) tidak perlu tahu tentang kepala / ekor atau pengalokasi, mereka hanya memiliki untuk menjalankan pointer tautan sebelumnya / berikutnya untuk mundur / maju dalam daftar. Jadi, jika Anda menerapkan terlalu banyak std::sort Untuk list kontainer, tidak akan ada cara untuk mengambil daftar penampung dari iterator yang diteruskan ke fungsi pengurutan. Dan, dalam semua kasus yang Anda sebutkan, versi algoritme yang sesuai untuk wadah khusus tersebut "terpusat" dalam arti bahwa mereka perlu dijalankan pada tingkat penampung, bukan pada tingkat "pemutus" iterator. Itu sebabnya mereka masuk akal sebagai fungsi anggota, dan itulah mengapa Anda tidak bisa mendapatkannya dari iterator.

Namun, jika Anda perlu memiliki cara umum untuk memanggil algoritme ini terlepas dari penampung yang Anda miliki, maka Anda dapat memberikan template fungsi yang kelebihan beban di tingkat penampung jika Anda mau. Semudah ini:

template <typename Container>
void sort_container(Container& c) {
  std::sort(begin(c), end(c));
};

template <typename T, typename Alloc>
void sort_container(std::list<T, Alloc>& c) {
  c.sort();
};

template <typename Key, typename T, typename Compare, typename Alloc>
void sort_container(std::map<Key, T, Compare, Alloc>&) { /* nothing */ };

//... so on..

Intinya di sini adalah bahwa jika Anda sudah terikat dengan kontainer STL, maka Anda dapat mengikat dengan algoritma STL dengan cara ini jika Anda ingin ... tapi jangan berharap pustaka standar C ++ memaksa Anda untuk memiliki jenis antar-ketergantungan antara kontainer dan algoritma, karena tidak semua orang menginginkannya (misalnya, banyak orang sangat menyukai algoritma STL, tetapi tidak memiliki cinta untuk kontainer STL (yang memiliki banyak masalah)).


1
2018-03-07 21:45