vektor vs daftar di STL

238

Saya perhatikan di Efektif STL itu

vektor adalah jenis urutan yang harus digunakan secara default.

Apa artinya? Tampaknya mengabaikan efisiensi vectordapat melakukan apa saja.

Adakah yang bisa menawarkan saya skenario di mana vectorbukan merupakan opsi yang layak tetapi listharus digunakan?

c++ list vector stl skydoor
sumber
6
Meskipun bukan itu yang Anda tanyakan, ada baiknya menunjukkan bahwa pengaturan default ke vektor juga berarti Anda dapat dengan mudah berinteraksi dengan kode lama, pustaka C, atau pustaka non-templat, karena vektor adalah pembungkus tipis di sekitar array dinamis "tradisional" dari sebuah pointer. dan ukuran.
18
Bjarne Strostrup sebenarnya membuat tes di mana ia menghasilkan angka acak dan kemudian menambahkannya ke daftar dan vektor masing-masing. Penyisipan dibuat sehingga daftar / vektor dipesan setiap saat. Meskipun ini biasanya "daftar domain", vektor mengungguli daftar dengan margin yang BESAR. Alasannya karena akses memori lambat dan caching berfungsi lebih baik untuk data sekuensial. Semuanya tersedia dalam keynote-nya dari "GoingNative 2012"
menghindari
4
baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque
Adam Burry
1
Jika Anda ingin melihat keynote oleh Bjarne Stroustrup yang @evading sebutkan, saya menemukannya di sini: youtu.be/OB-bdWKwXsU?t=2672
brain56

Jawaban:

98

Situasi di mana Anda ingin memasukkan banyak item ke mana saja tetapi akhir urutan berulang kali.

Lihat jaminan kompleksitas untuk setiap jenis wadah:

Apa jaminan kompleksitas dari kontainer standar?

Martin York
sumber
2
Memasukkan elemen pada akhirnya juga diperhitungkan karena dapat menyebabkan alokasi memori dan biaya penyalinan elemen. Dan juga, memasukkan elenet pada awal vektor hampir tidak mungkin, listtelahpush_front
Notinlist
9
Tidak, memasukkan elemen pada akhir vektor adalah waktu konstan diamortisasi. Alokasi memori hanya terjadi sesekali, dan Anda dapat melakukan pra-alokasi vektor untuk mencegahnya. Tentu saja, jika Anda HARUS telah memastikan penyisipan waktu konstan yang konsisten, saya kira ini masih menjadi masalah.
Brian
16
@Notinlist - Apakah "hampir mustahil" untuk Anda? v.insert (v.begin (), i)
Manuel
5
@Notinlist - Saya setuju dengan Anda, hanya saja saya tidak ingin OP berpikir bahwa antarmuka tidak ada jika seseorang ingin menembak dirinya sendiri di kaki (kinerja).
Manuel
16
Bjarne Strostrup sebenarnya membuat tes di mana ia menghasilkan angka acak dan kemudian menambahkannya ke daftar dan vektor masing-masing. Penyisipan dibuat sehingga daftar / vektor dipesan setiap saat. Meskipun ini biasanya "daftar domain", vektor mengungguli daftar dengan margin yang BESAR. Alasannya karena akses memori lambat dan caching berfungsi lebih baik untuk data sekuensial. Itu semua tersedia dalam keynote-nya dari "GoingNative 2012"
menghindari
409

vektor:

  • Memori yang berdekatan.
  • Pra-alokasikan ruang untuk elemen masa depan, sehingga ruang tambahan diperlukan di luar apa yang diperlukan untuk elemen itu sendiri.
  • Setiap elemen hanya membutuhkan ruang untuk jenis elemen itu sendiri (tidak ada pointer tambahan).
  • Dapat mengalokasikan kembali memori untuk seluruh vektor kapan pun Anda menambahkan elemen.
  • Penyisipan pada akhirnya konstan, waktu diamortisasi, tetapi penyisipan di tempat lain adalah O (n) yang mahal.
  • Penghapusan pada akhir vektor adalah waktu yang konstan, tetapi sisanya adalah O (n).
  • Anda dapat mengakses elemen-elemennya secara acak.
  • Iterator tidak valid jika Anda menambah atau menghapus elemen ke atau dari vektor.
  • Anda dapat dengan mudah mendapatkan array yang mendasarinya jika Anda membutuhkan array elemen.

daftar:

  • Memori tidak bersebelahan.
  • Tidak ada memori yang dialokasikan sebelumnya. Memori overhead untuk daftar itu sendiri konstan.
  • Setiap elemen membutuhkan ruang ekstra untuk node yang menyimpan elemen, termasuk pointer ke elemen berikutnya dan sebelumnya dalam daftar.
  • Tidak perlu mengalokasikan kembali memori untuk seluruh daftar hanya karena Anda menambahkan elemen.
  • Penyisipan dan penghapusan murah di mana pun dalam daftar itu terjadi.
  • Murah untuk menggabungkan daftar dengan splicing.
  • Anda tidak dapat mengakses elemen secara acak, jadi mendapatkan elemen tertentu dalam daftar bisa mahal.
  • Iterator tetap valid bahkan ketika Anda menambah atau menghapus elemen dari daftar.
  • Jika Anda membutuhkan array elemen, Anda harus membuat yang baru dan menambahkan semuanya ke sana, karena tidak ada array yang mendasarinya.

Secara umum, gunakan vektor ketika Anda tidak peduli apa jenis wadah berurutan yang Anda gunakan, tetapi jika Anda melakukan banyak penyisipan atau penghapusan ke dan dari mana saja di dalam wadah selain dari akhir, Anda akan ingin untuk menggunakan daftar. Atau jika Anda memerlukan akses acak, maka Anda akan menginginkan vektor, bukan daftar. Selain itu, ada beberapa contoh di mana Anda akan membutuhkan satu atau yang lain berdasarkan aplikasi Anda, tetapi secara umum, itu adalah pedoman yang baik.

Jonathan M Davis
sumber
2
Juga, mengalokasikan dari toko gratis tidak gratis. :) Menambahkan item baru ke vektor melakukan alokasi toko gratis O (log n), tetapi Anda dapat menelepon reserve()untuk mengurangi itu ke O (1). Menambahkan item baru ke daftar (mis. Tidak membuat splicing) melakukan O (n) alokasi toko gratis.
bk1e
7
Pertimbangan lain adalah bahwa listmembebaskan memori ketika Anda menghapus elemen, tetapi vectortidak. A vectortidak mengurangi kapasitasnya ketika Anda mengurangi ukurannya, kecuali jika Anda menggunakan swap()triknya.
bk1e
@ bk1e: Saya benar-benar ingin tahu trik Anda dalam cadangan () dan swap () :)
Dzung Nguyen
2
@nXqd: jika Anda perlu menambahkan elemen N ke vektor, panggil v.reserve (v.size () + N) sehingga hanya menjalankan satu alokasi toko gratis. Trik swap () ada di sini: stackoverflow.com/questions/253157/how-to-downsize-stdvector
bk1e
1
@simplename No. Apa yang dikatakannya benar. vektor mengalokasikan ruang ekstra di luar ruang untuk elemen yang saat ini dalam vektor; bahwa kapasitas ekstra kemudian digunakan untuk menumbuhkan vektor sehingga tumbuh itu diamortisasi O (1).
Jonathan M Davis
35

Jika Anda tidak perlu sering memasukkan elemen maka vektor akan lebih efisien. Ini memiliki lokasi cache CPU yang jauh lebih baik daripada daftar. Dengan kata lain, mengakses satu elemen membuatnya sangat mungkin bahwa elemen berikutnya ada dalam cache dan dapat diambil tanpa harus membaca RAM yang lambat.

Hans Passant
sumber
32

Sebagian besar jawaban di sini kehilangan satu detail penting: untuk apa?

Apa yang ingin Anda simpan di wadahnya?

Jika ini adalah kumpulan dari ints, maka std::listakan hilang dalam setiap skenario, terlepas dari apakah Anda dapat realokasi, Anda hanya menghapus dari depan, dll. Daftar lebih lambat untuk dilintasi, setiap penyisipan akan membuat Anda interaksi dengan pengalokasi. Akan sangat sulit untuk menyiapkan contoh, di mana list<int>ketukan vector<int>. Dan bahkan kemudian, deque<int>mungkin lebih baik atau dekat, bukan hanya menggunakan daftar, yang akan memiliki overhead memori yang lebih besar.

Namun, jika Anda berurusan dengan gumpalan data yang besar dan jelek - dan beberapa di antaranya - Anda tidak ingin menempatkan keseluruhan saat memasukkan, dan menyalin karena realokasi akan menjadi bencana - maka Anda mungkin, mungkin, lebih baik dengan list<UglyBlob>dari vector<UglyBlob>.

Namun, jika Anda beralih ke vector<UglyBlob*>atau bahkan vector<shared_ptr<UglyBlob> >, lagi - daftar akan tertinggal.

Jadi, pola akses, jumlah elemen target dll masih mempengaruhi perbandingan, tetapi dalam pandangan saya - ukuran elemen - biaya penyalinan dll.

Tomasz Gandor
sumber
1
Satu lagi refleksi, yang saya miliki ketika membaca "STL Efektif" oleh Meyers: properti aneh list<T>adalah kemungkinan splicedalam O (1) . Jika Anda perlu penyambungan waktu secara konstan, daftar mungkin juga merupakan struktur pilihan;)
Tomasz Gandor
+1 - Bahkan tidak harus menjadi UglyBlob- bahkan objek dengan hanya beberapa anggota string dapat dengan mudah menjadi mahal untuk disalin, sehingga realokasi akan dikenakan biaya. Juga: Jangan abaikan ruang di atas kepala yang vectorbisa menyebabkan pertumbuhan objek dengan ukuran beberapa lusin byte (jika Anda tidak bisa melakukannya reservedi muka).
Martin Ba
Adapun vector<smart_ptr<Large>>vs list<Large>- Saya akan mengatakan, jika Anda membutuhkan akses acak ke elemen, itu vectormasuk akal. Jika Anda tidak memerlukan akses acak, listsepertinya lebih sederhana dan harus berkinerja sama.
Martin Ba
19

Satu kemampuan khusus std :: list adalah splicing (menghubungkan atau memindahkan sebagian atau seluruh daftar ke daftar yang berbeda).

Atau mungkin jika konten Anda sangat mahal untuk disalin. Dalam kasus seperti itu, mungkin lebih murah, misalnya, untuk menyortir koleksi dengan daftar.

Perhatikan juga bahwa jika koleksinya kecil (dan isinya tidak terlalu mahal untuk disalin), vektor mungkin masih mengungguli daftar, bahkan jika Anda menyisipkan dan menghapus di mana saja. Daftar mengalokasikan setiap node secara individual, dan itu mungkin jauh lebih mahal daripada memindahkan beberapa objek sederhana.

Saya tidak berpikir ada aturan yang sangat sulit. Tergantung pada apa yang Anda ingin lakukan dengan wadah, serta seberapa besar Anda mengharapkan wadah dan jenis yang terkandung. Vektor umumnya mengalahkan daftar, karena ia mengalokasikan isinya sebagai satu blok bersebelahan (pada dasarnya array yang dialokasikan secara dinamis, dan dalam kebanyakan keadaan, array adalah cara paling efisien untuk menampung banyak hal).

UncleBens
sumber
1
+1. Penyambungan diabaikan, tetapi sayangnya waktu tidak konstan seperti yang diinginkan. : (((Tidak mungkin jika daftar :: ukuran adalah waktu konstan.)
Saya cukup yakin list :: size adalah (diizinkan) linear karena alasan ini.
UncleBens
1
@Roger: list::sizebelum tentu waktu yang konstan. Lihat stackoverflow.com/questions/228908/is-listsize-really-on dan gcc.gnu.org/ml/libstdc++/2005-11/msg00219.html
Potatoswatter
@Potatoswatter: Bahwa standarnya tidak jelas dan akibatnya Anda tidak bisa mengandalkan implementasi yang "sesuai" membuatnya semakin menjadi masalah. Anda benar-benar harus menghindari stdlib untuk mendapatkan jaminan portabel dan dapat diandalkan.
@Roger: ya, sayangnya. Proyek saya saat ini sangat bergantung pada operasi sambatan dan struktur itu hampir lurus C. Bahkan lebih sayangnya, dalam urutan N3000 spliceantara daftar yang berbeda ditentukan sebagai kompleksitas linier dan sizesecara khusus konstan. Jadi, untuk mengakomodasi pemula yang melakukan iterate sizeatau apa pun, seluruh kelas algoritma berada di luar jangkauan untuk STL, atau periode wadah yang "sesuai".
Potatoswatter
13

Baik siswa kelas saya tampaknya tidak dapat menjelaskan kepada saya kapan lebih efektif menggunakan vektor, tetapi mereka terlihat cukup senang ketika menasihati saya untuk menggunakan daftar.

Ini adalah bagaimana saya memahaminya

Daftar : Setiap item berisi alamat ke elemen berikutnya atau sebelumnya, jadi dengan fitur ini, Anda dapat mengacak item, meskipun item tersebut tidak diurutkan, urutannya tidak akan berubah: efisien jika memori Anda terpecah-pecah. Tetapi itu juga memiliki keuntungan lain yang sangat besar: Anda dapat dengan mudah memasukkan / menghapus item, karena satu-satunya hal yang perlu Anda lakukan adalah mengubah beberapa petunjuk. Kekurangan: Untuk membaca item tunggal acak, Anda harus melompat dari satu item ke item lain hingga Anda menemukan alamat yang benar.

Vektor : Saat menggunakan vektor, memori jauh lebih teratur seperti array reguler: setiap item ke-n disimpan tepat setelah (ke-1) item ke-1 dan sebelum (ke-1) ke-ke-ke-1. Mengapa lebih baik daripada daftar? Karena itu memungkinkan akses acak cepat. Begini caranya: jika Anda tahu ukuran item dalam vektor, dan jika mereka berdekatan dalam memori, Anda dapat dengan mudah memprediksi di mana item ke-n berada; Anda tidak perlu menelusuri semua item dalam daftar untuk membaca yang Anda inginkan, dengan vektor, Anda langsung membacanya, dengan daftar yang tidak dapat Anda baca. Di sisi lain, modifikasi array vektor atau ubah nilainya jauh lebih lambat.

Daftar lebih tepat untuk melacak objek yang dapat ditambahkan / dihapus dalam memori. Vektor lebih tepat ketika Anda ingin mengakses elemen dari sejumlah besar item tunggal.

Saya tidak tahu bagaimana daftar dioptimalkan, tetapi Anda harus tahu bahwa jika Anda ingin akses baca cepat, Anda harus menggunakan vektor, karena seberapa baik STL mempercepat daftar, itu tidak akan lebih cepat dalam akses baca daripada vektor.

jokoon
sumber
"modifikasi array vektor atau ubah nilainya jauh lebih lambat" - seperti yang dibaca, ini tampaknya bertentangan dengan apa yang Anda katakan sebelumnya tentang vektor yang cenderung untuk kinerja yang baik karena sifatnya yang rendah dan bersebelahan. maksud Anda bahwa realokasi yang vectordisebabkan oleh mengubah ukurannya bisa lambat? kemudian setuju, tetapi dalam kasus di mana reserve()dapat digunakan, itu menghindari masalah itu.
underscore_d
10

Pada dasarnya vektor adalah array dengan manajemen memori otomatis. Data berdekatan dalam memori. Mencoba memasukkan data di tengah adalah operasi yang mahal.

Dalam daftar, data disimpan di lokasi memori yang tidak terkait. Memasukkan di tengah tidak melibatkan menyalin beberapa data untuk memberikan ruang bagi yang baru.

Untuk menjawab lebih spesifik pertanyaan Anda, saya akan mengutip halaman ini

vektor umumnya yang paling efisien dalam waktu untuk mengakses elemen dan untuk menambah atau menghapus elemen dari akhir urutan. Untuk operasi yang melibatkan menyisipkan atau menghapus elemen pada posisi selain akhir, mereka berkinerja lebih buruk daripada deques dan daftar, dan memiliki iterator dan referensi yang kurang konsisten daripada daftar.

f4.
sumber
9

Kapan saja Anda tidak dapat membatalkan iterator.

secara langsung
sumber
2
Tapi jangan pernah langsung sampai pada kesimpulan tentang iterator tanpa bertanya apakah referensi yang gigih ke dalam dequecukup.
Potatoswatter
8

Ketika Anda memiliki banyak penyisipan atau penghapusan di tengah urutan. misal manajer memori.

AraK
sumber
jadi perbedaan di antara mereka hanyalah efisiensi, bukan tentang masalah fungsional.
skydoor
Mereka berdua memodelkan urutan elemen tentu saja. Ada sedikit perbedaan dalam penggunaannya, seperti yang disebutkan oleh @ secara khusus tetapi Anda harus melihat kompleksitas operasi "yang sering dilakukan" Anda untuk memutuskan urutan mana yang harus dipilih (@Martin menjawab).
AraK
@skydoor - Ada beberapa perbedaan fungsional. Misalnya, hanya vektor yang mendukung akses acak (yaitu, dapat diindeks).
Manuel
2
@skydoor: efisiensi diterjemahkan menjadi kinerja. Performa yang buruk dapat merusak fungsionalitas. Bagaimanapun, kinerja adalah keunggulan C ++.
Potatoswatter
4

Mempertahankan validitas iterator adalah salah satu alasan untuk menggunakan daftar. Lain adalah ketika Anda tidak ingin vektor untuk realokasi ketika mendorong item. Ini dapat dikelola dengan penggunaan cadangan yang cerdas (), tetapi dalam beberapa kasus mungkin lebih mudah atau lebih layak untuk hanya menggunakan daftar.

John Dibling
sumber
4

Saat Anda ingin memindahkan objek di antara kontainer, Anda bisa menggunakan list::splice.

Sebagai contoh, algoritma partisi grafik mungkin memiliki jumlah objek konstan dibagi secara rekursif di antara jumlah kontainer yang meningkat. Objek harus diinisialisasi sekali dan selalu tetap di lokasi yang sama dalam memori. Ini jauh lebih cepat untuk mengatur ulang mereka dengan menata kembali daripada dengan merealokasi.

Sunting: saat pustaka bersiap untuk mengimplementasikan C ++ 0x, kasus umum penyambungan urutan ke dalam daftar menjadi kompleksitas linier dengan panjang urutan. Ini karena splice(sekarang) perlu mengulangi urutan untuk menghitung jumlah elemen di dalamnya. (Karena daftar perlu mencatat ukurannya.) Cukup menghitung dan menautkan kembali daftar masih lebih cepat daripada alternatif lain, dan menyambung seluruh daftar atau elemen tunggal adalah kasus khusus dengan kompleksitas konstan. Tetapi, jika Anda memiliki urutan panjang untuk sambungan, Anda mungkin harus mencari-cari wadah yang lebih baik, kuno, dan tidak sesuai.

Potatoswatter
sumber
2

Satu-satunya aturan keras di mana listharus digunakan adalah di mana Anda perlu mendistribusikan pointer ke elemen wadah.

Berbeda dengan dengan vector, Anda tahu bahwa memori elemen tidak akan dialokasikan kembali. Jika bisa maka Anda mungkin memiliki petunjuk untuk memori yang tidak digunakan, yang terbaik adalah tidak-tidak besar dan paling buruk a SEGFAULT.

(Secara teknis vectordari *_ptrjuga akan bekerja tetapi dalam kasus bahwa Anda meniru listsehingga hanya semantik.)

Aturan lunak lainnya harus dilakukan dengan kemungkinan masalah kinerja memasukkan elemen ke tengah wadah, di mana listlebih disukai.

iPherian
sumber
2

Sederhanakan-
Pada akhir hari ketika Anda bingung memilih wadah di C ++ gunakan gambar diagram alur ini (Ucapkan terima kasih kepada saya): - masukkan deskripsi gambar di sini

Vektor-
1. vektor didasarkan pada memori menular
2. vektor adalah cara untuk pergi untuk kumpulan data kecil
3. vektor melakukan tercepat saat melintasi pada kumpulan data
4. penghapusan penyisipan vektor lambat pada kumpulan data besar tetapi cepat untuk yang sangat kecil

List
1. daftar didasarkan pada memori heap
2. daftar adalah cara untuk pergi untuk sangat besar data set
3. daftar relatif lambat pada melintasi kecil data set tapi cepat pada data set besar
4. daftar penyisipan penghapusan cepat pada kumpulan data besar tetapi lambat pada yang lebih kecil

xyz xyz
sumber
1

Daftar hanyalah pembungkus untuk Linkedlink ganda di stl, sehingga menawarkan fitur yang mungkin Anda harapkan dari d-linklist yaitu O (1) penyisipan dan penghapusan. Sedangkan vektor adalah urutan data yang menular yang berfungsi seperti array dinamis.PS- lebih mudah dilintasi.

Ritankar Paul
sumber
0

Dalam hal vektor dan daftar , perbedaan utama yang muncul pada saya adalah sebagai berikut:

vektor

  • Vektor menyimpan elemen-elemennya dalam memori yang berdekatan. Oleh karena itu, akses acak dimungkinkan di dalam vektor yang berarti bahwa mengakses elemen vektor sangat cepat karena kita dapat dengan mudah mengalikan alamat basis dengan indeks item untuk mengakses elemen itu. Bahkan, hanya dibutuhkan O (1) atau waktu yang konstan untuk tujuan ini.

  • Karena vektor pada dasarnya membungkus sebuah array, setiap kali Anda memasukkan elemen ke dalam vektor (array dinamis), ia harus mengubah ukurannya sendiri dengan menemukan blok memori baru yang berdekatan untuk mengakomodasi elemen-elemen baru yang memakan waktu mahal.

  • Itu tidak mengkonsumsi memori ekstra untuk menyimpan pointer ke elemen lain di dalamnya.

daftar

  • Daftar menyimpan elemen-elemennya dalam memori yang tidak bersebelahan. Oleh karena itu, akses acak tidak dimungkinkan di dalam daftar yang berarti bahwa untuk mengakses elemen-elemennya kita harus menggunakan pointer dan melintasi daftar yang lebih lambat relatif terhadap vektor. Ini membutuhkan O (n) atau waktu linier yang lebih lambat dari O (1).

  • Karena daftar menggunakan memori yang tidak bersebelahan, waktu yang diperlukan untuk memasukkan elemen ke dalam daftar jauh lebih efisien daripada dalam hal rekan vektornya karena realokasi memori dihindari.

  • Mengkonsumsi memori ekstra untuk menyimpan pointer ke elemen sebelum dan sesudah elemen tertentu.

Jadi, mengingat perbedaan-perbedaan ini, kami biasanya mempertimbangkan memori , akses acak sering dan penyisipan untuk menentukan pemenang daftar vektor vs dalam skenario yang diberikan.

Ardent Coder
sumber
0

Daftar adalah Daftar Tertaut Ganda sehingga mudah untuk menyisipkan dan menghapus suatu elemen. Kita hanya perlu mengubah beberapa pointer, sedangkan dalam vektor jika kita ingin memasukkan elemen di tengah maka setiap elemen setelah itu harus bergeser satu indeks. Juga jika ukuran vektor penuh maka pertama-tama harus meningkatkan ukurannya. Jadi ini operasi yang mahal. Jadi dimanapun operasi penyisipan dan penghapusan harus dilakukan lebih sering dalam daftar kasus seperti itu harus digunakan.

Siddesh Pawar
sumber