std :: vector versus std :: array di C ++

Apa perbedaan antara a std::vectordan a std::arraydi C ++? Kapan sebaiknya satu lebih disukai daripada yang lain? Apa pro dan kontra dari masing-masing? Semua buku teks saya lakukan adalah daftar bagaimana mereka sama.

std::vectoradalah kelas template yang merangkum array dinamis ¹ , disimpan di heap, yang tumbuh dan menyusut secara otomatis jika elemen ditambahkan atau dihapus. Ini menyediakan semua kait ( begin(),, end()iterator, dll) yang membuatnya berfungsi dengan baik dengan sisa STL. Ini juga memiliki beberapa metode berguna yang memungkinkan Anda melakukan operasi yang pada array normal akan rumit, seperti misalnya memasukkan elemen di tengah-tengah vektor (ini menangani semua pekerjaan memindahkan elemen berikut di belakang layar).

Karena ia menyimpan elemen-elemen dalam memori yang dialokasikan pada heap, ia memiliki beberapa overhead sehubungan dengan array statis.

std::arrayadalah kelas templat yang merangkum array berukuran statis, disimpan di dalam objek itu sendiri, yang berarti bahwa, jika Anda instantiate kelas pada stack, array itu sendiri akan berada di stack. Ukurannya harus diketahui pada waktu kompilasi (dilewatkan sebagai parameter templat), dan tidak dapat tumbuh atau menyusut.

Ini lebih terbatas daripada std::vector, tetapi seringkali lebih efisien, terutama untuk ukuran kecil, karena dalam praktiknya sebagian besar pembungkus ringan di sekitar array gaya-C. Namun, ini lebih aman, karena konversi implisit ke penunjuk dinonaktifkan, dan menyediakan banyak fungsi terkait STL std::vectordan wadah lainnya, sehingga Anda dapat menggunakannya dengan mudah dengan algoritma & co STL. Bagaimanapun, untuk batasan ukuran tetap itu jauh lebih fleksibel daripada std::vector.

Untuk pengantar std::array, lihat artikel ini ; untuk pengantar cepat ke std::vectordan untuk operasi yang memungkinkan, Anda mungkin ingin melihat dokumentasinya .

1. Sebenarnya, saya berpikir bahwa dalam standar mereka dijelaskan dalam hal kompleksitas maksimum dari operasi yang berbeda (misalnya akses acak dalam waktu konstan, iterasi atas semua elemen dalam waktu linier, penambahan dan penghapusan elemen pada akhirnya dalam waktu diamortisasi konstan, dll), tetapi AFAIK tidak ada metode lain untuk memenuhi persyaratan tersebut selain menggunakan array dinamis. Seperti yang dinyatakan oleh @Lucretiel, standar sebenarnya mengharuskan elemen disimpan secara bersebelahan, jadi itu adalah array dinamis, disimpan di mana pengalokasi terkait meletakkannya.

Menggunakan std::vector<T>kelas:

• ... sama cepatnya dengan menggunakan array bawaan, dengan asumsi Anda hanya melakukan hal-hal yang dapat dilakukan oleh array bawaan (baca dan tulis ke elemen yang ada).

• ... secara otomatis mengubah ukuran ketika elemen baru dimasukkan.

• ... memungkinkan Anda untuk memasukkan elemen baru di awal atau di tengah vektor, secara otomatis "menggeser" elemen lainnya "ke atas" (apakah itu masuk akal?). Hal ini memungkinkan Anda untuk menghapus elemen di mana saja di std::vector, juga, secara otomatis menggeser sisa elemen ke bawah.

• ... memungkinkan Anda untuk melakukan membaca rentang-diperiksa dengan at()metode (Anda selalu dapat menggunakan pengindeks []jika Anda tidak ingin pemeriksaan ini dilakukan).

Ada dua tiga peringatan utama untuk digunakan std::vector<T>:

1. Anda tidak memiliki akses yang dapat diandalkan ke pointer yang mendasarinya, yang mungkin menjadi masalah jika Anda berurusan dengan fungsi pihak ketiga yang menuntut alamat array.

2. The std::vector<bool>kelas konyol. Ini diimplementasikan sebagai bitfield yang terkondensasi, bukan sebagai array. Hindari jika Anda menginginkan array bools!

3. Selama penggunaan, std::vector<T>s akan menjadi sedikit lebih besar dari array C ++ dengan jumlah elemen yang sama. Ini karena mereka perlu melacak sejumlah kecil informasi lain, seperti ukuran mereka saat ini, dan karena setiap kali std::vector<T>diubah ukurannya, mereka menyimpan lebih banyak ruang daripada yang mereka butuhkan. Ini untuk mencegah mereka harus mengubah ukuran setiap kali elemen baru dimasukkan. Perilaku ini dapat diubah dengan memberikan kebiasaan allocator, tetapi saya tidak pernah merasa perlu melakukan itu!

Sunting: Setelah membaca balasan Zud untuk pertanyaan itu, saya merasa saya harus menambahkan ini:

The std::array<T>kelas tidak sama dengan C ++ array yang. std::array<T>adalah pembungkus yang sangat tipis di sekitar array C ++, dengan tujuan utama menyembunyikan pointer dari pengguna kelas (dalam C ++, array secara implisit dilemparkan sebagai pointer, seringkali untuk efek yang mengecewakan). The std::array<T>kelas juga menyimpan ukuran (panjang), yang bisa sangat berguna.

Untuk menekankan poin yang dibuat oleh @MatteoItalia, perbedaan efisiensi adalah di mana data disimpan. Memori tumpukan (diperlukan dengan vector) memerlukan panggilan ke sistem untuk mengalokasikan memori dan ini bisa mahal jika Anda menghitung siklus. Stack memory (mungkin untuk array) secara virtual "zero-overhead" dalam hal waktu, karena memori dialokasikan dengan hanya menyesuaikan stack pointer dan dilakukan hanya sekali saat masuk ke suatu fungsi. Tumpukan juga menghindari fragmentasi memori. Yang pasti, std::arraytidak akan selalu ada di tumpukan; itu tergantung di mana Anda mengalokasikannya, tetapi itu masih akan melibatkan alokasi memori kurang dari tumpukan dibandingkan dengan vektor. Jika Anda punya

• "array" kecil (di bawah 100 elemen katakan) - (tumpukan khas sekitar 8MB, jadi jangan mengalokasikan lebih dari beberapa KB pada tumpukan atau kurang jika kode Anda bersifat rekursif)
• ukuran akan diperbaiki
• masa pakai berada dalam lingkup fungsi (atau nilai anggota dengan masa hidup yang sama dengan kelas induk)
• Anda menghitung siklus,

pasti menggunakan std::arraylebih dari satu vektor. Jika salah satu dari persyaratan itu tidak benar, maka gunakan a std::vector.

Jika Anda mempertimbangkan untuk menggunakan array multidimensi, maka ada satu perbedaan tambahan antara std :: array dan std :: vector. Array multidimensi std :: akan memiliki elemen yang dikemas dalam memori di semua dimensi, seperti halnya array gaya ac. Std :: vektor multidimensi tidak akan dikemas dalam semua dimensi.

Diberikan deklarasi berikut:

int cConc[3][5];
std::array<std::array<int, 5>, 3> aConc;
int **ptrConc;      // initialized to [3][5] via new and destructed via delete
std::vector<std::vector<int>> vConc;    // initialized to [3][5]

Pointer ke elemen pertama dalam array c-style (cConc) atau std :: array (aConc) dapat diulang melalui seluruh array dengan menambahkan 1 ke setiap elemen sebelumnya. Mereka penuh sesak.

Pointer ke elemen pertama dalam array vektor (vConc) atau array pointer (ptrConc) hanya dapat diulang melalui elemen 5 (dalam hal ini) pertama, dan kemudian ada 12 byte (pada sistem saya) dari overhead untuk vektor berikutnya.

Ini berarti bahwa array std :: vector> yang diinisialisasi sebagai array [3] [1000] akan jauh lebih kecil dalam memori daripada array yang diinisialisasi sebagai array [1000] [3], dan keduanya akan lebih besar dalam memori daripada std: array dialokasikan dengan cara baik.

Ini juga berarti bahwa Anda tidak dapat dengan mudah mengirimkan array vektor (atau penunjuk) multidimensi ke, katakanlah, openGL tanpa memperhitungkan overhead memori, tetapi Anda dapat secara naif meneruskan array std :: array multidimensi ke openGL dan menjalankannya.

Vektor adalah kelas wadah sementara array adalah memori yang dialokasikan.