Kapan sebaiknya vektor / daftar digunakan?

17

Saya dapat memahami kapan harus menggunakan daftar, tetapi saya tidak mengerti kapan lebih baik menggunakan vektor daripada menggunakan daftar di video game: kapan lebih baik memiliki akses acak cepat?

(Dan saya mengerti mengapa lebih cepat memasukkan / menghapus daftar karena itu hanya menghilangkan / menambah pointer, tetapi masih harus menemukan item yang sesuai ...)

c++ algorithm data-structure jokoon
sumber
Menambahkan kembali tag vektor ke ini - jika daftar adalah tag yang valid, maka vektor juga.
Kylotan
Agaknya vektor dihapus karena digunakan untuk berarti vektor matematika, bukan std :: vector.
1
bagaimana kalau nix mereka berdua dan menempatkan container.
deft_code
@ Silyl: Ini seperti kata Joe. Pertanyaan ini jelas tentang vektor, tetapi tidak termasuk dalam tag vektor.
doppelgreener
1
Jadi, apakah kita menghapus tag yang ambigu? Itu terdengar seperti keputusan yang salah bagi saya - lebih baik pencarian Anda menghasilkan terlalu banyak informasi daripada tidak cukup. Melewatkan hasil yang tidak diinginkan lebih mudah daripada mencari ide untuk menemukan sinonim.
Kylotan

Jawaban:

29

Aturan praktis saya, dan saya yakin akan ada perdebatan tentang ini, adalah untuk tidak pernah menggunakan daftar (kecuali jika Anda perlu, sangat sering menghapus hal-hal dari tengah daftar besar).

Kecepatan yang akan Anda peroleh dengan memasukkan semua elemen Anda ke dalam wadah dalam memori yang bersebelahan (dan karenanya lebih ramah-cache) sebanding dengan biaya tambahan untuk menambah / menghapus / mengubah ukuran vektor.

Sunting: Hanya untuk memperjelas lebih banyak, tentu saja tidak perlu mengatakan bahwa segala jenis pertanyaan "yang lebih cepat" harus diuji pada platform apa pun dengan set data apa pun yang sesuai dengan kebutuhan khusus Anda. Jika saya hanya perlu koleksi elemen saya hanya menggunakan vektor (atau deque, yang merupakan hal yang hampir sama) kecuali ada alasan bagus untuk tidak melakukannya.

Tetrad
sumber
1
Saya pikir ini sangat tergantung pada kebutuhan Anda, jika Anda tidak perlu mengakses elemen tertentu dan hanya perlu membaca semuanya dan Anda sering menambah dan menghapus elemen, daftar adalah solusi yang lebih baik.
Frédérick Imbeault
11
@ Frédérick: Itu adalah kebijaksanaan standar C ++, tapi itu juga hampir selalu salah. Vektor, terutama ketika berhadapan dengan vektor pointer (yang hampir selalu Anda gunakan untuk game), sangat cepat untuk menghapus barang dari tengah - ini adalah waktu linier, tetapi ini adalah overhead yang sangat kecil per item. Ini juga jauh lebih cepat untuk beralih secara berurutan pada suatu vektor.
1
Saya tidak yakin struktur seperti apa yang Anda peroleh dengan tepat - optimasi semacam ini membutuhkan contoh nyata untuk mengatakan sesuatu secara definitif. Sebagai contoh, reaksi pertama saya terhadap use case Anda adalah set unordered, yang memungkinkan penyisipan, penghapusan, dan pencarian yang sama cepatnya; dalam set pengalaman saya bagus untuk objek dalam editor. Tetapi karena editor memiliki banyak persyaratan kinerja waktu nyata yang lebih longgar - mis. Tidak apa-apa jika menanggapi tombol "Hapus", tekan membutuhkan 1/20 per detik atau mengambil 1/2 dari 10% kedua dari waktu - tingkat optimasi ini juga jarang berlaku untuk mereka.
1
@ Frédérick Imbeault Diubah tidak terlalu menjadi masalah, itu adalah Add \ Remove yang menyebabkan masalah. Dari tambahkan \ titik dihapus ke ujung vektor disalin untuk menjaga vektor berdekatan. Jika urutan elemen tidak masalah, Anda dapat menukar elemen yang dihapus dengan elemen terakhir, lalu pop itu untuk dihapus dan tambahkan ke akhir untuk ditambahkan.
stonemetal
4
Tentu saja, mengambil alamat elemen dalam vektor dan menyimpannya tidak aman. Tetapi secara umum Anda hampir tidak pernah melakukan itu, alih-alih lebih suka memiliki vektor pointer elemen dan menyalin pointer di sekitar (atau sesuatu yang serupa).
Tetrad
8

Gunakan daftar ketika pembatalan iterator yang disebabkan oleh memodifikasi bagian tengah struktur data Anda akan menyebabkan masalah, atau Anda perlu menjaga elemen Anda diurutkan sehingga swap dan pop trick untuk penghapusan koleksi menengah cepat tidak akan berfungsi dan Anda memiliki besar jumlah koleksi pertengahan dihapus.

Anda mungkin juga ingin mempertimbangkan untuk menggunakan Deque. Ini memiliki karakteristik kinerja yang mirip dengan vektor tetapi tidak memiliki kebutuhan vektor untuk memori yang berdekatan, dan sedikit lebih fleksibel.

stonemetal
sumber
1 untuk menjadi satu-satunya orang yang menyebutkan deques - Anda mendapatkan memori yang berdekatan dan manfaat kecepatan pencarian vektor, dengan menyisipkan / menghapus cepat di kedua ujungnya.
5

Pilihan Anda harus mencerminkan kebutuhan Anda. Semua elemen vektor terus-menerus dalam memori dan daftar memiliki petunjuk ke elemen berikutnya / sebelumnya sehingga masing-masing memiliki kelebihan / kekurangan:

Daftar:

  • Setiap elemen membutuhkan 2 bilangan bulat untuk menunjuk elemen sebelumnya dan berikutnya, jadi paling umum, itu 8 byte lebih untuk setiap elemen dalam daftar Anda
  • Sisipkan linear dalam waktu: O (n)
  • Hapus adalah operasi konstan: O (1)
  • Akses elemen x linear dalam waktu: O (n)

Vektor:

  • Membutuhkan lebih sedikit memori (tidak ada petunjuk ke elemen lain, ini adalah algoritma matematika sederhana)
  • Hapus linear dalam waktu: O (n)
  • Mengakses elemen x adalah konstan: O (1) (Itu karena elemen-elemen tersebut bersambung dalam memori sehingga merupakan operasi matematika sederhana vectorPtr + (x * bytesOfTheType))
  • Masukkan bisa dalam waktu linier, tetapi paling umum, ini adalah operasi konstan: O (1) (Itu karena vektor dalam array tetapi selalu cadangan 2 kali kapasitasnya ketika array penuh sehingga salinan array tidak sering)

Jadi daftar lebih baik ketika program Anda perlu menambah dan menghapus elemen sering, tetapi tidak pernah mengakses (atau jarang mengakses) elemen tertentu tanpa perlu yang lain sebelumnya. Vektor harus digunakan untuk waktu akses yang lebih baik, tetapi tidak memiliki efisiensi ketika Anda perlu menghapus atau menambahkan elemen.

Lihat posting ini di stackoverflow, ini menyajikan grafik yang sangat bagus dengan pertanyaan dasar tentang kebutuhan Anda yang mengarahkan Anda ke wadah tertentu tergantung pada jawaban Anda:

/programming/366432/extending-stdlist

Frédérick Imbeault
sumber
3
Grafik itu benar-benar perlu dimulai dengan "Apakah Anda menyimpan pointer dan kurang dari seribu? Tidak -> vektor" node.
Ya mungkin Anda benar, saya tidak menganggap jenis yang disimpan itu juga harus dianalisis.
Frédérick Imbeault
2

Biasanya daftar digunakan untuk struktur seperti antrian di mana ada banyak append dan hapus operasi. Contoh: Daftar entitas yang terus berubah yang harus diperbarui. Daftar itu sendiri hanya berisi entitas di layar dan karenanya sering berubah.

Vektor (atau array) lebih cocok untuk koleksi yang tidak banyak berubah dan di mana Anda membutuhkan akses cepat ke masing-masing item dalam koleksi. Contoh: Peta-ubin tempat Anda harus mencari ubin pada indeks yang diberikan.

Pendapat Tetrads mungkin benar, tetapi itu tergantung pada bahasa pemrograman yang digunakan. Saya melihat bahwa Anda menandai pertanyaan Anda c++, tetapi saya mencoba memberikan jawaban yang tidak spesifik bahasa.

bummzack
sumber
Yah saya mungkin juga telah meletakkan C di dalamnya, tetapi tidak ada wadah seperti di C, tapi itu sesuatu untuk dipikirkan: apakah ada beberapa STL seperti perpustakaan untuk C?
jokoon
Saya telah menggunakan glib ( library.gnome.org/devel/glib ) di masa lalu, yang mengimplementasikan sejumlah struktur data standar untuk C. Saya membencinya karena biasanya terlalu bertele-tele dan sangat ingin menjadi C ++, tetapi sudah matang dan stabil.
0

Di game konsol kami tidak pernah menggunakan std :: list karena:

  1. itu alokasi memori setiap kali Anda menambahkan item baru. alokasi memori lambat.
  2. itu penuh dengan petunjuk. pointer buruk. pointer adalah miss cache. cache miss buruk.

even std :: vector kehilangan dukungan pada konsol karena:

  1. Anda sering hanya peduli tentang, misalnya, posisi semua objek. seperti misalnya Anda ingin bertabrakan satu sama lain, dalam hal ini Anda tidak peduli apa warnanya. jadi Anda ingin semua posisi bersebelahan dalam memori dan Anda ingin warna berada di tempat lain yang jauh, untuk menghindari polusi cache. tetapi std :: vector mengharuskan Anda untuk menyimpan semuanya untuk setiap objek dalam memori yang berdekatan (mis. posisi lalu warna.) jadi jika Anda benar-benar bekerja yang hanya membaca posisi, Anda perlu membaca semua warna ke dalam cache juga, bahkan jika Anda tidak menggunakannya. ini boros.
bmcnett
sumber
5
@ bmcnett "[] .. tapi std :: vector mengharuskan Anda untuk menyimpan semuanya untuk setiap objek dalam memori yang berdekatan" - itu bukan pertanyaan tentang wadah, ini pertanyaan tentang tata letak data Anda, Anda dapat memiliki semua posisi dalam sepotong memori yang berkelanjutan dengan std :: vector:struct point{float x, y, z, w}; std::vector<point> positions;
Maik Semder
sekolahku akan menyukai ini :)
jokoon
2
-1 karena jawaban ini tidak menambahkan apa pun ke daftar vs diskusi vektor sudah ada di sini, dan klaimnya tentang vektor mencemari cache salah, seperti kata Maik.
Anda salah mengerti klaim saya. saya tidak pernah mengatakan bahwa di antara semua kontainer std :: vector sangat bersalah karena mencemari cache. semua wadah, dan bahkan array, hampir sama bersalahnya. std :: vector gagal karena objek C ++ sendiri tidak disukai. C ++ mengamanatkan bahwa data setiap objek berdekatan dalam memori. Anda dapat menyiasatinya dengan menghindari objek C ++, misalnya dengan menggunakan std :: vector <position> seperti yang disebutkan di atas.
bmcnett
3
Kecuali pointadalah objek C ++ (sebagaimana std::vector, sesuatu yang sederhana float). Saya tahu perbedaan yang Anda coba gambar, tetapi Anda melakukan pekerjaan yang buruk untuk menjelaskannya.