Pertanyaan Apakah adil untuk selalu merekomendasikan std :: vector over realloc?


Dari FAQ Bjarne Stroustrup:

Jika Anda merasa perlu untuk realloc () - dan banyak yang melakukannya - kemudian pertimbangkan untuk menggunakannya   vektor perpustakaan standar.

Saya akan mengawali pertanyaan saya dengan menyetujui itu std::vector lebih baik karena berbagai alasan, dan saya pribadi akan selalu memilih untuk menggunakannya daripada menulis array dinamis saya sendiri dengan alokasi memori C.

Tapi, std::vector fragmen memori saat tumbuh karena C ++ tidak memiliki kesamaan realloc (sunting Untuk mengklarifikasi, saya tahu itu std::vectorpenyimpanan berdekatan dan tidak akan terfragmentasi, maksud saya fragmentasi ruang memori yang disebabkan oleh mengalokasikan dan deallocating, yang realloc dapat menghindari dengan memperluas alokasi yang ada). Jadi apakah adil untuk selalu merekomendasikannya realloc? Dengan sangat hati-hati, tidak bisakah Anda menulis sesuatu yang berfungsi seperti itu std::vector tetapi menggunakan fungsi alokasi C, yang memiliki kemungkinan untuk mengembangkan memorinya tanpa memindahkan alamatnya dan menyalin elemen yang ada, menjadikannya sebagai baik atau lebih baik dalam hal fragmentasi dan kinerja?

Dan terkait (pertanyaan bonus!), Mengapa tidak C ++ memiliki setara dengan realloc? Sepertinya hal yang aneh untuk dihilangkan dalam bahasa yang begitu terfokus pada kinerja. Bagian dalam FAQ Bjarne memiliki judul itu persis (minus penekanan), tetapi jawabannya tidak menjawab 'mengapa'. Apakah itu hanya kelalaian yang disengaja? Apakah ada ketidaksesuaian mendasar dengan bagaimana new/delete kerja? Apakah itu tidak benar-benar memberikan manfaat yang tampaknya dalam prakteknya?

Edit: ok, jadi saya telah mengabaikan untuk mempertimbangkan C nastiness realloc - std::vector tidak bisa ditulis ulang menggunakan realloc karena hanya bekerja dengan POD, tidak melempar dan sebagainya. Mungkin wadah khusus POD yang ditulis untuk menangani keburukan akan menjadi ide yang baik untuk beberapa situasi. Bagaimanapun juga, pertanyaan yang lebih menarik menjadi: akan std::vector manfaat dari C ++ setara realloc, yang (kurang lebih) telah dijawab di sini:

Apakah std :: vector * harus * memindahkan objek ketika kapasitas tumbuh? Atau, dapatkah pengalokasi "realokasi"?

Sayangnya, jawabannya sepertinya "ya, tapi komite standar tidak memilihnya". Ini berharap.


4
2018-04-08 09:31


asal


Jawaban:


Perbandingan langsung

                        |  std::vector     | C memory functions
------------------------+------------------+------------------------
default capacity        | undefined        | undefined
default grow            | towards capacity | undefined
deterministic capacity  | available        | no
deterministic grow      | available        | no
deterministic mem.-move | available        | no
non-POD types           | yes              | f***ing no (*)
no-throw                | no               | yes

deterministic mem.-move mengikuti dari deterministic capacity/grow. Ini saatnya realloc dan std::vector harus memindahkan elemen yang disimpan ke lokasi memori baru.

Saya pikir determinisme (yang tersedia) berkaitan dengan pemindahan memori menjadi dua kali penting ketika Anda mempertimbangkan untuk memindahkan (pintar) referensi apa pun.

CATATAN: Dalam hal ini, saya menggunakan istilah "deterministik" sehubungan dengan kode sumber saya seumur hidup, yaitu seumur hidupnya di berbagai versi pustaka yang berbeda dengan berbagai panji kompilasi, dll.


Sumber

Itu fragmen memori sebanyak realloc tidak:

Ringkasan vektor template kelas [vector.overview]

Unsur-unsur a   vektor disimpan bersebelahan, artinya jika v adalah vector<T, Allocator>dimana T adalah beberapa jenis selain bool, maka itu mematuhi identitas &v[n] == &v[0] + n untuk semua 0 <= n < v.size()

Dengan kata lain, memori yang digunakan adalah satu bagian.

Satu perbedaan besar adalah itu realloc sebenarnya dapat meningkatkan porsi memori yang dialokasikan tanpa memerintahkannya untuk melakukannya, namun, tidak diperlukan untuk melakukannya (man 3 realloc):

pria 3 realloc

Fungsi realloc () mengubah ukuran blok memori yang ditunjukkan oleh ptr ke byte ukuran. Isinya akan          tidak berubah dalam kisaran mulai dari awal wilayah hingga minimum ukuran lama dan baru. Jika baru          ukuran lebih besar dari ukuran lama, memori tambahan tidak akan diinisialisasi. Jika ptr adalah NULL, maka panggilan itu          setara dengan malloc (ukuran), untuk semua nilai ukuran; jika ukuran sama dengan nol, dan ptr bukan NULL, maka panggilan          setara dengan gratis (ptr). Kecuali ptr adalah NULL, itu pasti dikembalikan oleh panggilan sebelumnya ke malloc (),          loc () atau realloc (). Jika daerah yang dituju telah dipindahkan, bebas (ptr) dilakukan.

Jadi itu bisa meningkatkan ukuran, tetapi tidak diperlukan.

SEBUAH std::vector tidak hanya membawa a size, tetapi juga a capacity. Jika Anda tahu sebelumnya, Anda akan membutuhkan besar vector, namun Anda tidak dapat menginisialisasi semuanya sekarang, Anda berhak untuk meningkatkan kapasitas vektor Anda seperti ini:

std::vector<T> vec(32);
vec.reserve(1024);
// vec has size 32, but reserved a memory region of 1024 elements

Jadi tidak seperti itu realloc, saat ketika realokasi terjadi dapat menjadi deterministik std::vector.

Untuk menjawab pertanyaan Anda: Karena ada std::vector, realloc tidak diperlukan. Dan, realloc tidak diizinkan untuk jenis non-POD; mencoba untuk digunakan malloc, free dan realloc langsung pada non-POD menghasilkan perilaku tidak terdefinisi.


3
2018-04-08 09:37



new/new[] dan delete/delete[] biasanya berlapis di atas fungsi alokasi perpustakaan C (ala malloc/realloc/free), mungkin dengan lapisan tambahan untuk pengoptimalan objek kecil yang menggunakan satu mallocdaerah -ed untuk cepat memuaskan banyak kecil new permintaan. Layering ini berarti mendukung new dan delete mengambil sedikit usaha implementasi pada bagian penulis perpustakaan C ++ awal.

Untuk memanfaatkan fungsi pengubahan ukuran tempat di realloc untuk C + +, meskipun, perubahan invasif ke realloc fungsi pustaka diperlukan agar jika berpindah ke wilayah memori baru aku s diperlukan, kode perpustakaan C ++ mendapat kesempatan untuk menyalin-membangun / menghancurkan objek yang dipindahkan. Ini bisa dilakukan seperti:

  • panggilan balik terjadi setelah realloc menyadari suatu langkah diperlukan, meminta perpustakaan C ++ untuk melakukan gerakan data yang sebenarnya daripada melakukan memcpy() copy bytewise gaya, atau

  • sebagai tambahan fungsi resize-in-place-or-fail-without-moving sehingga kode C ++ library bisa mencobanya, lalu kembali pada malloc dan salinan yang benar / aman sebelum menghapus objek asli dan membatalkan memori asli.

Seperti kebanyakan perpustakaan C realloc fungsi tidak memiliki fasilitas hook / query seperti itu, C ++ Standard - dan Standard library - tidak memerlukannya. Seperti yang ditunjukkan Mehrdad, jawaban ini mendokumentasikan pengakuan SGI tentang masalah ini.

Mengingat ekstensif menggunakan C ++ hari ini, itu akan - IMHO - masuk akal untuk mengirim malloc/realloc/free Implementasi di C + + perpustakaan itu sendiri yang menyediakan seperti hook / query, sehingga penulis C ++ perpustakaan yang melihat utilitas di realloc dapat memanfaatkannya secara bebas; itu akan menjadi kandidat yang layak untuk dimasukkan dalam Standar masa depan.

Dengan sangat hati-hati, tidak bisakah Anda menulis sesuatu yang berfungsi seperti std :: vector tetapi menggunakan fungsi alokasi C, yang memiliki kemungkinan untuk menumbuhkan memorinya tanpa memindahkan alamatnya dan menyalin elemen yang ada, menjadikannya sebagai baik atau lebih baik dalam hal fragmentasi dan kinerja?

Seperti di atas - tidak - itu tidak mungkin untuk menyalin-membangun / merusak objek dengan sejumlah perawatan tanpa perubahan pada realloc API.


3
2018-04-08 10:10



std::vector fragmen memori saat tumbuh karena C ++ tidak memiliki kesamaan realloc.

realloc akan mem-fragmen memori dengan cara yang sama, karena itu melakukan hal yang sama - mengalokasikan blok baru dan menyalin isinya, jika blok lama tidak cukup besar.

Dengan sangat hati-hati, tidak bisakah Anda menulis sesuatu yang berfungsi seperti itu std::vector tetapi menggunakan fungsi alokasi C, yang memiliki kemungkinan untuk mengembangkan memorinya tanpa memindahkan alamatnya dan menyalin elemen yang ada, menjadikannya sebagai baik atau lebih baik dalam hal fragmentasi dan kinerja?

Seperti itulah vector tidak. Anda dapat mengontrol kapasitas independen dari ukuran, dan itu hanya akan dialokasikan ketika kapasitas dilampaui. realloc serupa, tetapi tidak berarti untuk mengontrol kapasitas - pembuatan vector lebih baik dalam hal fragmentasi dan kinerja.

mengapa C ++ tidak setara dengan realloc?

Karena itu std::vector, yang melakukan hal yang sama dengan lebih banyak fleksibilitas. Serta memungkinkan Anda untuk mengontrol persis bagaimana dan kapan memori dialokasikan, ia bekerja dengan jenis bergerak, sementara realloc akan sangat salah ketika digunakan dengan jenis yang tidak sepele.


2
2018-04-08 09:38



Ada alasan bagus mengapa C ++ tidak memilikinya realloc; alih-alih mengulanginya, saya akan mengarahkan Anda ke jawabannya sini.

Dan sebagai catatan, yang tepat vector implementasi meringankan masalah fragmentasi sampai batas tertentu, dengan memilih faktor pertumbuhan mendekati rasio emas, jadi itu tidak sepenuhnya hilang.


2
2018-04-08 09:43