Apa gunanya menggunakan daftar di atas vektor, di C ++?

Saya telah menjalankan 3 percobaan berbeda yang melibatkan daftar dan vektor C ++.

Mereka dengan vektor terbukti lebih efisien, bahkan ketika banyak penyisipan di tengah terlibat.

Karenanya pertanyaan: dalam hal apa daftar lebih masuk akal daripada vektor?

Jika vektor tampak lebih efisien dalam banyak kasus, dan mempertimbangkan seberapa mirip anggota mereka, maka keuntungan apa yang tersisa untuk daftar?

1. Hasilkan bilangan bulat N dan masukkan ke dalam wadah agar wadah tetap terurut. Penyisipan telah dilakukan secara naif, dengan membaca elemen satu per satu dan memasukkan yang baru sebelum yang lebih besar pertama.
   Dengan daftar, waktu melewati atap ketika dimensi meningkat, dibandingkan dengan vektor.

2. Masukkan N bilangan bulat di ujung wadah.
   Untuk daftar dan vektor, waktu meningkat dengan urutan besarnya yang sama, meskipun 3 kali lebih cepat dengan vektor.

3. Masukkan bilangan bulat N dalam sebuah wadah.
   Mulai timer.
   Sortir wadah menggunakan list.sort untuk daftar, dan std :: sort untuk vektor. Hentikan timer.
   Sekali lagi, waktu meningkat dengan urutan besarnya yang sama, tetapi rata-rata 5 kali lebih cepat dengan vektor.

Saya mungkin terus melakukan tes dan mencari tahu beberapa contoh di mana daftar akan terbukti lebih baik.

Tapi pengalaman bersama kalian membaca pesan ini mungkin memberikan jawaban yang lebih produktif.

Anda mungkin pernah menemukan situasi di mana daftar lebih nyaman digunakan, atau berkinerja lebih baik?

Jawaban singkatnya adalah bahwa kasus tampaknya sedikit dan jarang. Mungkin ada beberapa.

Salah satunya adalah ketika Anda perlu menyimpan sejumlah kecil objek besar - terutama, objek yang sangat besar sehingga tidak praktis untuk mengalokasikan ruang bahkan untuk beberapa tambahan dari mereka. Pada dasarnya tidak ada cara untuk menghentikan vektor atau deque dari mengalokasikan ruang untuk objek tambahan - begitulah mereka didefinisikan (yaitu, mereka harus mengalokasikan ruang ekstra untuk memenuhi persyaratan kompleksitas mereka). Jika flat-out Anda tidak memungkinkan ruang tambahan dialokasikan, std::listmungkin satu - satunya wadah standar yang memenuhi kebutuhan Anda.

Lain akan ketika / jika Anda akan menyimpan iterator ke titik "menarik" dalam daftar untuk jangka waktu yang lama, dan ketika Anda melakukan penyisipan dan / atau penghapusan, Anda (hampir) selalu melakukannya dari suatu tempat di mana Anda sudah memiliki iterator, jadi Anda tidak perlu menelusuri daftar untuk sampai ke titik di mana Anda akan melakukan penyisipan atau penghapusan. Jelas hal yang sama berlaku jika Anda bekerja dengan lebih dari satu tempat, tetapi masih berencana untuk menyimpan iterator di setiap tempat yang kemungkinan akan Anda gunakan untuk bekerja, sehingga Anda paling memanipulasi tempat yang dapat Anda jangkau secara langsung, dan jarang sekali menelusuri daftar untuk mendapatkan ke tempat-tempat itu.

Untuk contoh yang pertama, pertimbangkan browser web. Mungkin menyimpan daftar Tabobjek yang ditautkan , dengan masing-masing objek tab mewakili pada tab terbuka di browser. Setiap tab mungkin beberapa lusin megabita data (lebih, terutama jika sesuatu seperti video terlibat). Jumlah khas tab terbuka Anda mungkin dengan mudah kurang dari selusin, dan 100 mungkin mendekati ekstrem atas.

Untuk contoh yang kedua, pertimbangkan pengolah kata yang menyimpan teks sebagai daftar bab yang ditautkan, yang masing-masing mungkin berisi daftar paragraf (katakanlah) yang ditautkan. Ketika pengguna mengedit, mereka biasanya akan menemukan tempat tertentu di mana mereka akan mengedit, dan kemudian melakukan cukup banyak pekerjaan di tempat itu (atau di dalam paragraf itu, tetap). Ya, mereka akan berpindah dari satu paragraf ke paragraf lain sekarang dan lagi, tetapi dalam kebanyakan kasus itu akan menjadi paragraf di dekat tempat mereka sudah bekerja.

Sekali-sekali (hal-hal seperti pencarian dan penggantian global) Anda akhirnya berjalan melalui semua item di semua daftar, tetapi itu cukup jarang, dan bahkan ketika Anda melakukannya, Anda mungkin akan melakukan pekerjaan pencarian yang cukup dalam suatu item di daftar, bahwa waktu untuk melintasi daftar hampir tidak penting.

Perhatikan bahwa dalam kasus tipikal, ini cenderung cocok dengan kriteria pertama - bab berisi sejumlah paragraf yang cukup kecil, masing-masing paragraf cenderung cukup besar (setidaknya relatif terhadap ukuran pointer di simpul, dan semacamnya). Demikian juga, Anda memiliki sejumlah bab yang relatif kecil, yang masing-masing mungkin beberapa kilobyte.

Yang mengatakan, saya harus mengakui bahwa kedua contoh ini mungkin sedikit dibuat-buat, dan sementara daftar tertaut mungkin berfungsi dengan baik untuk keduanya, itu mungkin tidak akan memberikan keuntungan besar dalam kedua kasus juga. Dalam kedua kasus, misalnya, mengalokasikan ruang ekstra dalam vektor untuk beberapa halaman / tab web (kosong) atau beberapa bab kosong tidak akan menjadi masalah nyata.

Menurut Bjarne Stroustrup sendiri, vektor harus selalu menjadi koleksi default untuk urutan data. Anda dapat memilih daftar jika Anda ingin mengoptimalkan penyisipan dan penghapusan elemen, tetapi biasanya Anda tidak harus. Biaya dari daftar ini adalah penggunaan traversal dan memori yang lambat.

Dia membicarakan hal ini dalam presentasi ini .

Pada sekitar 0:44 ia berbicara tentang vektor vs daftar pada umumnya.

Masalah kekompakan. Vektor lebih kompak daripada daftar. Dan pola penggunaan yang dapat diprediksi sangat penting. Dengan vektor, Anda harus mendorong banyak elemen, tetapi cache benar-benar bagus. ... Daftar tidak memiliki akses acak. Tetapi ketika Anda melintasi daftar, Anda tetap melakukan akses acak. Ada simpul di sini, dan pergi ke simpul itu, dalam memori. Jadi Anda sebenarnya secara acak mengakses memori Anda, dan Anda memaksimalkan kesalahan cache Anda, yang merupakan kebalikan dari yang Anda inginkan.

Pada sekitar 1:08, dia diberi pertanyaan tentang masalah ini.

Apa yang harus kita lihat adalah bahwa kita membutuhkan urutan elemen. Dan urutan default elemen dalam C ++ adalah vektor. Sekarang, karena itu ringkas dan efisien. Implementasi, pemetaan ke perangkat keras, penting. Sekarang, jika Anda ingin mengoptimalkan penyisipan dan penghapusan - Anda berkata, 'well, saya tidak ingin versi default dari sebuah urutan. Saya ingin yang khusus, yang merupakan daftar '. Dan jika Anda melakukan itu, Anda harus cukup tahu untuk mengatakan, 'Saya menerima beberapa biaya dan beberapa masalah, seperti perlintasan lambat dan penggunaan memori yang lebih banyak'.

Satu-satunya tempat di mana saya biasanya menggunakan daftar adalah di mana saya perlu menghapus elemen dan tidak membatalkan iterator. std::vectormembatalkan semua iterator saat menyisipkan dan menghapus. std::listmenjamin bahwa iterator untuk elemen yang ada masih valid setelah dimasukkan atau dihapus.

Selain jawaban lain yang telah disediakan, daftar memiliki fitur-fitur tertentu yang tidak ada dalam vektor (karena mereka akan sangat mahal.) Operasi sambatan dan penggabungan menjadi yang paling signifikan. Jika Anda sering memiliki banyak daftar yang perlu ditambahkan atau digabungkan, daftar mungkin merupakan pilihan yang baik.

Tetapi jika Anda tidak perlu melakukan operasi ini, maka mungkin tidak.

Kurangnya cache yang melekat / halaman-ramah daftar terkait cenderung membuat mereka hampir diberhentikan seluruhnya oleh banyak pengembang C ++, dan dengan justifikasi yang baik dalam bentuk default.

Daftar Tertaut Masih Tetap Luar Biasa

Namun daftar yang ditautkan dapat menjadi luar biasa ketika didukung oleh pengalokasi tetap yang memberikan mereka kembali ke lokasi spasial yang pada dasarnya tidak mereka miliki.

Di mana mereka unggul adalah bahwa kita dapat membagi daftar menjadi dua daftar, misalnya, dengan hanya menyimpan pointer baru dan memanipulasi satu atau dua pointer. Kita dapat memindahkan node dari satu daftar ke yang lain dalam waktu yang konstan hanya dengan manipulasi pointer, dan daftar kosong dapat dengan mudah memiliki biaya memori dari satu headpointer.

Akselerator Grid Sederhana

Sebagai contoh praktis, pertimbangkan simulasi visual 2D. Ini memiliki layar gulir dengan peta yang membentang 400x400 (160.000 sel jaringan) yang digunakan untuk mempercepat hal-hal seperti deteksi tabrakan antara jutaan partikel yang bergerak di setiap frame (kami menghindari quad-tree di sini karena mereka sebenarnya cenderung berkinerja lebih buruk dengan tingkat ini). data dinamis). Sejumlah besar partikel terus bergerak di setiap bingkai, yang berarti partikel-partikel itu berpindah dari satu sel ke sel lainnya.

Dalam hal ini, jika setiap partikel adalah node daftar yang terhubung sendiri-sendiri, setiap sel grid dapat memulai sebagai hanya sebuah headpenunjuk yang menunjuk nullptr. Ketika sebuah partikel baru lahir, kita tinggal meletakkannya di sel grid yang berada dengan mengatur headpointer dari sel itu untuk menunjuk ke simpul partikel ini. Ketika sebuah partikel bergerak dari satu sel kisi ke sel berikutnya, kami hanya memanipulasi pointer.

Ini bisa jauh lebih efisien daripada menyimpan 160.000 vectorsuntuk setiap sel kisi dan mendorong kembali dan menghapus dari tengah sepanjang waktu berdasarkan kerangka demi kerangka.

std :: daftar

Ini untuk daftar linting tangan, intrusif, dan terhubung sendiri yang didukung oleh pengalokasi tetap. std::listmewakili daftar yang ditautkan dua kali lipat dan mungkin tidak akan sepadat saat kosong sebagai penunjuk tunggal (bervariasi berdasarkan implementasi vendor), ditambah itu agak merepotkan untuk mengimplementasikan pengalokasi kustom dalam std::allocatorbentuk.

Saya harus mengakui bahwa saya tidak pernah menggunakan listapa pun. Tetapi daftar yang ditautkan masih luar biasa! Namun mereka tidak bagus karena alasan orang sering tergoda untuk menggunakannya, dan tidak begitu bagus kecuali mereka didukung oleh pengalokasi tetap yang sangat efisien yang mengurangi banyak setidaknya kesalahan halaman wajib dan kesalahan cache terkait.

Anda harus mempertimbangkan ukuran elemen dalam wadah.

int elemen vektor sangat cepat karena sebagian besar data masuk ke dalam cache CPU (dan instruksi SIMD mungkin dapat digunakan untuk menyalin data).

Jika ukuran elemen lebih besar maka hasil tes 1 dan 3 dapat berubah secara signifikan.

Dari perbandingan kinerja yang sangat komprehensif :

Ini menarik kesimpulan sederhana tentang penggunaan setiap struktur data:

• Angka-angka: gunakan std::vectorataustd::deque
• Pencarian linear: gunakan std::vectorataustd::deque
• Sisipkan / Hapus acak:
  • Ukuran data kecil: gunakan std::vector
  • Ukuran elemen besar: digunakan std::list(kecuali jika terutama dimaksudkan untuk pencarian)
• Tipe data non-sepele: gunakan std::listkecuali Anda membutuhkan wadah khusus untuk pencarian. Tetapi untuk beberapa modifikasi wadah, itu akan sangat lambat.
• Dorong ke depan: gunakan std::dequeataustd::list

(sebagai catatan std::dequeadalah struktur data yang sangat diremehkan).

Dari sudut pandang kenyamanan std::listmemberikan jaminan bahwa iterator tidak pernah menjadi tidak valid saat Anda memasukkan dan menghapus elemen lain. Ini sering merupakan aspek kunci.

Alasan paling menonjol untuk menggunakan daftar menurut pendapat saya adalah pembatalan iterator : jika Anda menambahkan / menghapus elemen ke vektor, semua pointer, referensi, iterator yang Anda pegang ke elemen-elemen tertentu dari vektor ini mungkin batal dan menyebabkan bug halus .. , atau kesalahan segmentasi.

Ini tidak terjadi dengan daftar.

Aturan yang tepat untuk semua kontainer standar diberikan dalam pos StackOverflow ini .

Singkatnya, tidak ada alasan untuk menggunakan std::list<>:

• Jika Anda membutuhkan wadah yang tidak disortir, std::vector<>aturanlah.
  (Hapus elemen dengan menggantinya dengan elemen terakhir dari vektor.)

• Jika Anda membutuhkan wadah yang diurutkan, std::vector<shared_ptr<>>aturanlah.

• Jika Anda membutuhkan indeks jarang, std::unordered_map<>aturanlah.

Itu dia.

Saya menemukan bahwa hanya ada satu situasi di mana saya cenderung menggunakan daftar tertaut: Ketika saya memiliki objek yang sudah ada sebelumnya yang perlu dihubungkan dengan beberapa cara untuk mengimplementasikan beberapa logika aplikasi tambahan. Namun, dalam kasus itu saya tidak pernah menggunakan std::list<>, melainkan saya menggunakan pointer (pintar) berikutnya di dalam objek, terutama karena kebanyakan kasus penggunaan menghasilkan pohon daripada daftar linier. Dalam beberapa kasus, struktur yang dihasilkan adalah daftar tertaut, dalam kasus lain, itu adalah pohon, atau grafik asiklik terarah. Tujuan utama dari pointer ini adalah untuk selalu membangun struktur logis, tidak pernah untuk mengelola objek. Kami punya std::vector<>untuk itu.

Anda perlu menunjukkan bagaimana Anda melakukan sisipan pada tes pertama Anda. Tes kedua dan ketiga Anda, vektor akan dengan mudah menang.

Penggunaan daftar yang signifikan adalah ketika Anda harus mendukung penghapusan item saat iterasi. Ketika vektor diubah, semua iterator (berpotensi) tidak valid. Dengan daftar, hanya iterator ke elemen yang dihapus tidak valid. Semua iterator lainnya tetap valid.

Urutan penggunaan khas untuk wadah adalah vektor, deque, lalu daftar. Pilihan wadah biasanya didasarkan pada push_back memilih vektor, pop_front pilih deque, masukkan pilih daftar.

Salah satu faktor yang dapat saya pikirkan adalah bahwa ketika vektor tumbuh, memori bebas akan terfragmentasi ketika vektor mendeallocasikan memori dan mengalokasikan blok yang lebih besar berulang-ulang. Ini tidak akan menjadi masalah dengan daftar.

Ini selain fakta bahwa sejumlah besar push_backs tanpa cadangan juga akan menyebabkan salinan selama setiap perubahan ukuran yang membuatnya tidak efisien. Memasukkan di tengah juga menyebabkan perpindahan semua elemen ke kanan, dan bahkan lebih buruk.

Saya tidak tahu apakah ini merupakan perhatian utama, tetapi merupakan alasan yang diberikan kepada saya di tempat kerja saya (pengembangan game mobile), untuk menghindari vektor.