Dalam skenario apa saya menggunakan wadah STL tertentu?

Saya telah membaca tentang wadah STL dalam buku saya tentang C ++, khususnya bagian tentang STL dan wadahnya. Sekarang saya mengerti masing-masing dan masing-masing dari mereka memiliki sifat khusus mereka sendiri, dan saya hampir menghafal mereka semua ... Tapi apa yang saya belum pahami adalah di mana skenario masing-masing digunakan.

Apa penjelasannya? Kode contoh lebih disukai.

Lembar cheat ini memberikan ringkasan yang cukup bagus dari berbagai wadah.

Lihat diagram alur di bagian bawah sebagai panduan untuk digunakan dalam berbagai skenario penggunaan:

_{Dibuat oleh David Moore dan berlisensi CC BY-SA 3.0}

Berikut adalah diagram alur yang terinspirasi oleh versi David Moore (lihat di atas) yang saya buat, yang mutakhir (kebanyakan) dengan standar baru (C ++ 11). Ini hanya pendapat pribadi saya, itu tidak bisa dibantah, tapi saya pikir itu bisa berharga untuk diskusi ini:

Jawaban sederhana: gunakan std::vectoruntuk semuanya kecuali Anda memiliki alasan kuat untuk melakukan sebaliknya.

Ketika Anda menemukan kasus di mana Anda berpikir, "Wah, std::vectortidak berfungsi dengan baik di sini karena X", lanjutkan berdasarkan X.

Lihatlah Efektif STL oleh Scott Meyers. Ada baiknya menjelaskan cara menggunakan STL.

Jika Anda ingin menyimpan sejumlah objek yang ditentukan / tidak ditentukan dan Anda tidak akan pernah menghapusnya, maka vektorlah yang Anda inginkan. Ini adalah pengganti default untuk array C, dan berfungsi seperti itu, tetapi tidak meluap. Anda dapat mengatur ukurannya sebelumnya juga dengan cadangan ().

Jika Anda ingin menyimpan jumlah objek yang tidak ditentukan, tetapi Anda akan menambahkan dan menghapusnya, maka Anda mungkin menginginkan daftar ... karena Anda dapat menghapus elemen tanpa memindahkan elemen berikut - tidak seperti vektor. Namun, dibutuhkan lebih banyak memori daripada vektor, dan Anda tidak dapat mengakses elemen secara berurutan.

Jika Anda ingin mengambil banyak elemen dan hanya menemukan nilai unik dari elemen tersebut, membacanya semuanya menjadi satu set akan melakukannya, dan itu akan mengurutkannya untuk Anda juga.

Jika Anda memiliki banyak pasangan nilai kunci, dan Anda ingin mengurutkannya berdasarkan kunci, maka peta itu berguna ... tetapi itu hanya akan menampung satu nilai per kunci. Jika Anda membutuhkan lebih dari satu nilai per kunci, Anda bisa memiliki vektor / daftar sebagai nilai Anda di peta, atau menggunakan multimap.

Itu tidak ada di STL, tetapi ada di pembaruan TR1 ke STL: jika Anda memiliki banyak pasangan nilai kunci yang akan Anda cari dengan kunci, dan Anda tidak peduli dengan pesanan mereka, Anda mungkin ingin menggunakan hash - yaitu tr1 :: unordered_map. Saya telah menggunakannya dengan Visual C ++ 7.1, di mana ia disebut stdext :: hash_map. Ini memiliki pencarian O (1) bukan pencarian O (log n) untuk peta.

Saya mendesain ulang diagram alur untuk memiliki 3 properti:

1. Saya pikir wadah STL dibagi menjadi 2 kelas utama. Wadah dasar dan yang memanfaatkan wadah dasar untuk menerapkan kebijakan.
2. Pada awalnya diagram alur harus membagi proses pengambilan keputusan dengan situasi utama yang harus kita putuskan dan kemudian uraikan pada setiap kasus.
3. Beberapa kontainer yang diperluas memiliki kemungkinan untuk memilih wadah dasar yang berbeda sebagai wadah dalamnya. Flowchart harus mempertimbangkan situasi di mana masing-masing wadah dasar dapat digunakan.

Diagram alir:

Info lebih lanjut disediakan di tautan ini .

Poin penting hanya sebentar disebutkan sejauh ini, adalah bahwa jika Anda memerlukan memori yang berdekatan (seperti array C memberikan), maka Anda dapat hanya menggunakan vector, arrayatau string.

Gunakan arrayjika ukuran diketahui pada waktu kompilasi.

Gunakan stringjika Anda hanya perlu bekerja dengan tipe karakter dan membutuhkan string, bukan hanya wadah tujuan umum.

Gunakan vectordalam semua kasus lain ( vectorbagaimanapun juga harus menjadi pilihan default dari wadah).

Dengan ketiganya, Anda dapat menggunakan data()fungsi anggota untuk mendapatkan pointer ke elemen pertama wadah.

Itu semua tergantung pada apa yang ingin Anda simpan dan apa yang ingin Anda lakukan dengan wadah. Berikut adalah beberapa (sangat tidak lengkap) contoh untuk kelas kontainer yang paling sering saya gunakan:

vector: Tata letak yang ringkas dengan sedikit atau tanpa overhead memori per objek yang terkandung. Efisien untuk diulangi. Menambahkan, menyisipkan, dan menghapus bisa mahal, terutama untuk objek yang kompleks. Murah untuk menemukan objek yang terkandung oleh indeks, misalnya myVector [10]. Gunakan di mana Anda akan menggunakan array di C. Bagus di mana Anda memiliki banyak objek sederhana (misalnya int). Jangan lupa untuk menggunakan reserve()sebelum menambahkan banyak objek ke wadah.

list: Overhead memori kecil per objek yang terkandung. Efisien untuk diulangi. Tambahkan, masukkan, dan hapus itu murah. Gunakan tempat Anda akan menggunakan daftar tertaut di C.

set(dan multiset): overhead memori signifikan per objek yang terkandung. Gunakan tempat Anda perlu mencari tahu dengan cepat apakah wadah itu berisi objek yang diberikan, atau gabungkan wadah secara efisien.

map(dan multimap): overhead memori signifikan per objek yang terkandung. Gunakan tempat Anda ingin menyimpan pasangan nilai kunci dan mencari nilai dengan kunci dengan cepat.

Bagan alur pada lembar contekan yang disarankan oleh zdan menyediakan panduan yang lebih lengkap.

Satu pelajaran yang saya pelajari adalah: Cobalah untuk membungkusnya dalam kelas, karena mengubah jenis wadah suatu hari dapat menghasilkan kejutan besar.

class CollectionOfFoo {
    Collection<Foo*> foos;
    .. delegate methods specifically 
}

Tidak perlu banyak biaya di muka, dan menghemat waktu dalam debugging ketika Anda ingin istirahat setiap kali seseorang melakukan operasi x pada struktur ini.

Datang untuk memilih struktur data yang sempurna untuk suatu pekerjaan:

Setiap struktur data menyediakan beberapa operasi, yang dapat beragam kompleksitas waktu:

O (1), O (lg N), O (N), dll.

Anda pada dasarnya harus mengambil tebakan terbaik, di mana operasi akan dilakukan paling banyak, dan menggunakan struktur data yang memiliki operasi itu sebagai O (1).

Sederhana, bukan (-:

Saya memperluas diagram alur Mikael Persson yang fantastis. Saya menambahkan beberapa kategori wadah, wadah array, dan beberapa catatan. Jika Anda ingin salinan Anda sendiri, inilah Gambar Google. Terima kasih, Mikael untuk melakukan pekerjaan dasar! C ++ Pemilih Kontainer

Saya menjawab ini dalam pertanyaan lain yang ditandai sebagai dup yang satu ini. Tetapi saya merasa senang untuk merujuk pada beberapa artikel bagus mengenai keputusan untuk memilih wadah standar.

Seperti @David Thornley menjawab, std :: vector adalah cara untuk pergi jika tidak ada kebutuhan khusus lainnya. Ini adalah saran yang diberikan oleh pencipta C ++, Bjarne Stroustrup di blog 2014.

Berikut ini tautan untuk artikel https://isocpp.org/blog/2014/06/stroustrup-lists

dan mengutip dari yang itu,

Dan, ya, rekomendasi saya adalah menggunakan std :: vector secara default.

Dalam komentar tersebut, pengguna @NathanOliver juga menyediakan blog bagus lainnya, yang memiliki ukuran yang lebih konkret. https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html .