Mengapa std :: stack menggunakan std :: deque secara default?

91

Karena satu-satunya operasi yang diperlukan agar container digunakan dalam stack adalah:

  • kembali()
  • push_back ()
  • pop_back ()

Mengapa penampung default untuknya adalah deque, bukan vektor?

Jangan deque realokasi memberikan buffer dari elemen sebelum front () sehingga push_front () adalah operasi yang efisien? Bukankah elemen-elemen ini terbuang percuma karena mereka tidak akan pernah digunakan dalam konteks tumpukan?

Jika tidak ada overhead untuk menggunakan deque dengan cara ini dan bukan vektor, mengapa default untuk priority_queue vektor bukan deque juga? (priority_queue membutuhkan front (), push_back (), dan pop_back () - pada dasarnya sama dengan stack)

Diperbarui berdasarkan Jawaban di bawah ini:

Tampaknya cara deque biasanya diimplementasikan adalah larik ukuran variabel dari larik ukuran tetap. Ini membuat pertumbuhan lebih cepat daripada vektor (yang membutuhkan realokasi dan penyalinan), jadi untuk sesuatu seperti tumpukan yang semuanya tentang menambah dan menghapus elemen, deque kemungkinan merupakan pilihan yang lebih baik.

priority_queue sangat membutuhkan pengindeksan, karena setiap penghapusan dan penyisipan mengharuskan Anda menjalankan pop_heap () atau push_heap (). Ini mungkin membuat vektor menjadi pilihan yang lebih baik di sana karena penambahan elemen masih tetap diamortisasi.

c++ stl containers Greg Rogers
sumber
1
Alasan di 'pembaruan' Anda kurang tepat. vektor biasanya menambah dan menghilangkan elemen dari ujung lebih cepat daripada deque. deque lebih cepat untuk menumbuhkan memori , tidak mendorong elemen.
Mooing Duck

Jawaban:

75

Saat container berkembang, realokasi untuk vektor memerlukan penyalinan semua elemen ke dalam blok memori yang baru. Mengembangkan deque mengalokasikan blok baru dan menautkannya ke daftar blok - tidak diperlukan salinan.

Tentu saja Anda dapat menentukan bahwa backing container yang berbeda akan digunakan jika Anda mau. Jadi jika Anda memiliki tumpukan yang Anda tahu tidak akan bertambah banyak, beri tahu untuk menggunakan vektor alih-alih deque jika itu pilihan Anda.

Michael Burr
sumber
1
Tetapi ketika daftar pointer ke blok bertambah, daftar ini terkadang harus dialokasikan kembali seperti yang harus dilakukan oleh vektor; secara asimtotik, setiap peningkatan efisiensi adalah dengan faktor konstan. Dan manipulasi iterator yang diperlukan untuk melakukan push dan pop dengan benar jauh lebih rumit std::dequedaripada sebelumnya std::vector, dan operasi ini cenderung lebih sering digunakan daripada realokasi. Saya sulit percaya bahwa itu std::dequeakan pernah mengalahkan std::vectordalam latihan.
Marc van Leeuwen
@ Michael Burr: Lalu mengapa tidak digunakan list, mengapa deque?
bappak
@MarcvanLeeuwen tentang Anda mengatakan Anda sulit percaya ... bisakah Anda membuat sudut pandang yang jelas? apakah maksud Anda sekarang Anda percaya bahwa std::dequeAnda memiliki kesempatan untuk mengalahkan std::vectordalam latihan, atau apakah Anda masih meragukannya? Terima kasih.
aafulei
@fleix Saya tidak mengerti mengapa sangat penting apakah saya secara pribadi memiliki waktu yang lebih mudah untuk mempercayai yang std::dequeakan dilakukan sebaik std::vectordalam aplikasi praktis. Tetapi untuk apa nilainya, pengalaman pribadi saya adalah bahwa saya memerlukan struktur data tumpukan dan antrian bukan untuk satu tugas besar dan kompleksitas-krusial, tetapi untuk banyak kesempatan kecil yang ditaburkan melalui kode saya. Karena itu saya lebih peduli tentang perilaku di kecil daripada di besar; dan deque bersinar sangat membosankan di sana. Preferensi saya adalah menggunakan tidak keduanya, tetapi sebagai gantinya (diterapkan sendiri) daftar tertaut tunggal. Tapi jarak tempuh Anda mungkin berbeda.
Marc van Leeuwen
12

Lihat Guru Minggu 54 Herb Sutter untuk manfaat relatif vektor dan deque di mana keduanya akan berhasil.

Saya membayangkan ketidakkonsistenan antara priority_queue dan queue hanya karena orang yang berbeda menerapkannya.

James Hopkin
sumber
2
priority_queue sebenarnya tidak menggunakan push / pop_front, dan referensi ke elemen selain yang pertama tidak valid oleh operasi heap. Jadi, tidak ada manfaat deque yang berlaku, tidak seperti kasus antrean biasa.
Potatoswatter
9
Juga, priority_queueharus tetap diurutkan, sehingga overhead yang lebih tinggi dari pengaksesan acak deque::iteratorlebih bermasalah.
Potatoswatter
1
@Potatoswatter: priority_queuememiliki "urutan ajaib" yang dipertahankan, tidak diurutkan. Namun, maksud Anda tetap berlaku.
Mooing Duck