Apa aturan pembatalan iterator untuk wadah C ++?

Lebih disukai dalam format daftar ringkasan.

_{(Catatan: Ini dimaksudkan sebagai entri untuk FAQ C ++ Stack Overflow . Jika Anda ingin mengkritik gagasan memberikan FAQ dalam formulir ini, maka posting pada meta yang memulai semua ini akan menjadi tempat untuk melakukan itu. Jawaban untuk pertanyaan itu dipantau di chatroom C ++ , di mana ide FAQ dimulai sejak awal, jadi jawaban Anda sangat mungkin untuk dibaca oleh mereka yang mengemukakan ide itu.)}

C ++ 17 (Semua referensi berasal dari draft kerja akhir CPP17 - n4659 )

Insersi

Wadah urutan

• vector: Fungsi insert, emplace_back, emplace, push_backpenyebabnya realokasi jika ukuran baru lebih besar dari kapasitas tua. Realokasi membatalkan semua referensi, pointer, dan iterator yang mengacu pada elemen dalam urutan. Jika tidak ada realokasi, semua iterator dan referensi sebelum titik penyisipan tetap valid. [26.3.11.5/1]
  Sehubungan dengan reservefungsi tersebut, realokasi membatalkan semua referensi, pointer, dan iterator yang merujuk pada elemen-elemen dalam urutan. Tidak ada realokasi yang akan terjadi selama penyisipan yang terjadi setelah panggilan reserve()hingga waktu penyisipan akan membuat ukuran vektor lebih besar dari nilai capacity(). [26.3.11.3/6]

• deque: Penyisipan di tengah-tengah deque membatalkan semua iterator dan referensi untuk elemen-elemen dari deque. Penyisipan di kedua ujung deque membatalkan semua iterator ke deque, tetapi tidak memiliki efek pada validitas referensi ke elemen deque. [26.3.8.4/1]

• list: Tidak memengaruhi validitas iterator dan referensi. Jika pengecualian dilemparkan tidak ada efek. [26.3.10.4/1].
  The insert, emplace_front, emplace_back, emplace, push_front, push_backfungsi tercakup dalam aturan ini.

• forward_list: Tidak satu pun dari kelebihan ini insert_afterakan memengaruhi validitas iterator dan referensi [26.3.9.5/1]

• array: Sebagai aturan , iterator ke array tidak pernah dibatalkan sepanjang masa pakai array. Orang harus mencatat, bagaimanapun, bahwa selama swap, iterator akan terus menunjuk ke elemen array yang sama, dan dengan demikian akan mengubah nilainya.

Wadah Asosiatif

• All Associative Containers: The insertdan emplaceanggota tidak akan mempengaruhi validitas iterator dan referensi ke wadah [26.2.6 / 9]

Kontainer Asosiatif Tidak Berurutan

• All Unordered Associative Containers: Rehashing mematahkan iterator, mengubah urutan antar elemen, dan perubahan yang memasukkan elemen bucket, tetapi tidak membatalkan pointer atau referensi ke elemen. [26.2.7 / 9]
  Anggota insertdan emplacetidak akan mempengaruhi validitas referensi untuk elemen wadah, tetapi dapat membatalkan semua iterator ke wadah. [26.2.7 / 14]
  Anggota insertdan emplaceanggota tidak akan memengaruhi validitas iterator jika (N+n) <= z * B, di mana Njumlah elemen dalam wadah sebelum operasi penyisipan, nadalah jumlah elemen yang dimasukkan, Badalah jumlah bucket wadah, dan zmerupakan faktor muatan maksimum kontainer. [26.2.7 / 15]

• All Unordered Associative Containers: Dalam kasus operasi penggabungan (misalnya, a.merge(a2)), iterator yang merujuk pada elemen yang ditransfer dan semua iterator yang merujuk aakan tidak valid, tetapi iterator pada elemen yang tersisa a2akan tetap valid. (Tabel 91 - Persyaratan wadah asosiatif tidak teratur)

Adaptor Kontainer

• stack: diwarisi dari wadah yang mendasarinya
• queue: diwarisi dari wadah yang mendasarinya
• priority_queue: diwarisi dari wadah yang mendasarinya

Penghapusan

Wadah urutan

• vector: Fungsi erasedan pop_backmembatalkan iterator dan referensi pada atau setelah titik penghapusan. [26.3.11.5/3]

• deque: Operasi hapus yang menghapus elemen terakhir dari dequeinvalidate hanya iterator masa lalu-akhir dan semua iterator dan referensi ke elemen terhapus. Operasi hapus yang menghapus elemen pertama dari a dequetetapi bukan elemen terakhir hanya membatalkan iterator dan referensi ke elemen yang terhapus. Operasi hapus yang tidak menghapus elemen pertama atau elemen terakhir dari dequemembatalkan iterator masa lalu-akhir dan semua iterator dan referensi ke semua elemen dari deque. [Catatan: pop_frontdan pop_backsedang menghapus operasi. —Kirim catatan] [26.3.8.4/4]

• list: Hanya memvalidasi iterator dan referensi ke elemen yang dihapus. [26.3.10.4/3]. Hal ini berlaku untuk erase, pop_front, pop_back, clearfungsi.
  removedan remove_iffungsi anggota: Menghapus semua elemen dalam daftar yang dirujuk oleh daftar iterator iyang memiliki ketentuan sebagai berikut: *i == value, pred(*i) != false. Batalkan hanya iterator dan referensi untuk elemen yang dihapus [26.3.10.5/15].
  uniquefungsi anggota - Menghapus semua kecuali elemen pertama dari setiap grup yang terdiri dari elemen yang sama yang dirujuk oleh iterator idalam rentang [first + 1, last)yang *i == *(i-1)(untuk versi unik tanpa argumen) ataupred(*i, *(i - 1))(untuk versi unik dengan argumen predikat) berlaku. Validasi hanya iterator dan referensi untuk elemen yang terhapus. [26.3.10.5/19]

• forward_list: erase_afterhanya akan membatalkan iterator dan referensi ke elemen yang dihapus. [26.3.9.5/1].
  removedan remove_iffungsi anggota - Menghapus semua elemen dalam daftar yang dirujuk oleh daftar iterator i yang dipegang oleh kondisi berikut: *i == value(untuk remove()), pred(*i)benar (untuk remove_if()). Validasi hanya iterator dan referensi untuk elemen yang terhapus. [26.3.9.6/12].
  uniquefungsi anggota - Menghapus semua kecuali elemen pertama dari setiap grup berurutan dari elemen yang sama yang disebut oleh iterator i dalam rentang [pertama + 1, terakhir) untuk yang *i == *(i-1)(untuk versi tanpa argumen) atau pred(*i, *(i - 1))(untuk versi dengan predikat argumen) berlaku. Validasi hanya iterator dan referensi untuk elemen yang terhapus. [26.3.9.6/16]

• All Sequence Containers: clearmembatalkan semua referensi, pointer, dan iterator yang mengacu pada elemen a dan dapat membatalkan iterator masa lalu-akhir (Tabel 87 - Persyaratan wadah urutan). Tetapi untuk forward_list, cleartidak membatalkan iterator masa lalu. [26.3.9.5/32]

• All Sequence Containers: assignmembatalkan semua referensi, petunjuk dan iterator yang mengacu pada elemen wadah. Untuk vectordan deque, juga membatalkan iterator masa lalu-akhir. (Tabel 87 - Persyaratan wadah urutan)

Wadah Asosiatif

• All Associative Containers: eraseAnggota hanya akan membatalkan iterator dan referensi untuk elemen yang dihapus [26.2.6 / 9]

• All Associative Containers: extractAnggota hanya membatalkan iterator ke elemen yang dihapus; pointer dan referensi ke elemen yang dihapus tetap valid [26.2.6 / 10]

Adaptor Kontainer

• stack: diwarisi dari wadah yang mendasarinya
• queue: diwarisi dari wadah yang mendasarinya
• priority_queue: diwarisi dari wadah yang mendasarinya

Persyaratan kontainer umum terkait dengan pembatalan iterator:

• Kecuali ditentukan lain (baik secara eksplisit atau dengan mendefinisikan fungsi dalam fungsi lainnya), menjalankan fungsi anggota kontainer atau meneruskan wadah sebagai argumen ke fungsi perpustakaan tidak akan membatalkan iterator untuk, atau mengubah nilai, objek di dalam wadah itu . [26.2.1 / 12]

• tidak ada swap()fungsi yang membatalkan referensi, petunjuk, atau iterator yang merujuk pada elemen wadah yang ditukar. [Catatan: iterator end () tidak merujuk ke elemen apa pun, sehingga mungkin tidak valid. —Kirim catatan] [26.2.1 / (11.6)]

Sebagai contoh persyaratan di atas:

• transformalgoritma: Fungsi opdan binary_optidak boleh membatalkan iterator atau subranges, atau memodifikasi elemen dalam rentang [28.6.4 / 1]

• accumulatealgoritme: Dalam rentang [pertama, terakhir], binary_optidak boleh memodifikasi elemen atau membatalkan iterator atau subrange [29.8.2 / 1]

• reducealgoritma: binary_op tidak akan membatalkan iterator atau subranges, atau memodifikasi elemen dalam rentang [pertama, terakhir]. [29.8.3 / 5]

dan seterusnya...

C ++ 03 (Sumber: Aturan validasi Iterator (C ++ 03) )

Insersi

Wadah urutan

• vector: semua iterator dan referensi sebelum titik penyisipan tidak terpengaruh, kecuali ukuran wadah baru lebih besar dari kapasitas sebelumnya (dalam hal ini semua iterator dan referensi tidak valid) [23.2.4.3/1]
• deque: semua iterator dan referensi tidak valid, kecuali jika anggota yang dimasukkan berada di ujung (depan atau belakang) dari deque (dalam hal ini semua iterator tidak valid, tetapi referensi ke elemen tidak terpengaruh) [23.2.1.3/1]
• list: semua iterator dan referensi tidak terpengaruh [23.2.2.3/1]

Wadah asosiatif

• [multi]{set,map}: semua iterator dan referensi tidak terpengaruh [23.1.2 / 8]

Adaptor kontainer

• stack: diwarisi dari wadah yang mendasarinya
• queue: diwarisi dari wadah yang mendasarinya
• priority_queue: diwarisi dari wadah yang mendasarinya

Penghapusan

Wadah urutan

• vector: setiap iterator dan referensi setelah titik penghapusan tidak valid [23.2.4.3/3]
• deque: semua iterator dan referensi tidak valid, kecuali anggota yang terhapus berada di ujung (depan atau belakang) dari deque (dalam hal ini hanya iterator dan referensi ke anggota yang terhapus yang dibatalkan) [23.2.1.3/4]
• list: hanya iterator dan referensi ke elemen yang dihapus tidak valid [23.2.2.3/3]

Wadah asosiatif

• [multi]{set,map}: hanya iterator dan referensi untuk elemen yang dihapus tidak valid [23.1.2 / 8]

Adaptor kontainer

• stack: diwarisi dari wadah yang mendasarinya
• queue: diwarisi dari wadah yang mendasarinya
• priority_queue: diwarisi dari wadah yang mendasarinya

Mengubah ukuran

• vector: sesuai masukkan / hapus [23.2.4.2/6]
• deque: sesuai masukkan / hapus [23.2.1.2/1]
• list: sesuai masukkan / hapus [23.2.2.2/1]

Catatan 1

Kecuali ditentukan lain (baik secara eksplisit atau dengan mendefinisikan fungsi dalam fungsi lainnya), menjalankan fungsi anggota kontainer atau meneruskan wadah sebagai argumen ke fungsi perpustakaan tidak akan membatalkan iterator untuk, atau mengubah nilai, objek di dalam wadah itu . [23.1 / 11]

Catatan 2

Tidak jelas dalam C ++ 2003 apakah iterator "end" tunduk pada aturan di atas ; Anda harus mengasumsikan bahwa mereka (karena ini adalah kasusnya).

Catatan 3

Aturan untuk pembatalan pointer adalah sama dengan aturan untuk pembatalan referensi.

C ++ 11 (Sumber: Aturan validasi Iterator (C ++ 0x) )

Insersi

Wadah urutan

• vector: semua iterator dan referensi sebelum titik penyisipan tidak terpengaruh, kecuali ukuran wadah baru lebih besar dari kapasitas sebelumnya (dalam hal ini semua iterator dan referensi tidak valid) [23.3.6.5/1]
• deque: semua iterator dan referensi tidak valid, kecuali jika anggota yang dimasukkan berada di ujung (depan atau belakang) dari deque (dalam hal ini semua iterator tidak valid, tetapi referensi ke elemen tidak terpengaruh) [23.3.3.4/1]
• list: semua iterator dan referensi tidak terpengaruh [23.3.5.4/1]
• forward_list: semua iterator dan referensi tidak terpengaruh (berlaku untuk insert_after) [23.3.4.5/1]
• array: (n / a)

Wadah asosiatif

• [multi]{set,map}: semua iterator dan referensi tidak terpengaruh [23.2.4 / 9]

Wadah asosiatif yang tidak disortir

• unordered_[multi]{set,map}: semua iterator batal ketika terjadi pengulangan, tetapi referensi tidak terpengaruh [23.2.5 / 8] Rehashing tidak terjadi jika penyisipan tidak menyebabkan ukuran wadah melebihi di z * Bmana zfaktor beban maksimum dan Bjumlah ember saat ini. [23.2.5 / 14]

Adaptor kontainer

• stack: diwarisi dari wadah yang mendasarinya
• queue: diwarisi dari wadah yang mendasarinya
• priority_queue: diwarisi dari wadah yang mendasarinya

Penghapusan

Wadah urutan

• vector: setiap iterator dan referensi pada atau setelah titik penghapusan tidak valid [23.3.6.5/3]
• deque: menghapus elemen terakhir hanya membatalkan iterator dan referensi ke elemen yang dihapus dan iterator masa lalu-akhir; menghapus elemen pertama hanya akan membatalkan iterator dan referensi untuk elemen yang dihapus; menghapus elemen lain akan membatalkan semua iterator dan referensi (termasuk iterator masa lalu-akhir) [23.3.3.4/4]
• list: hanya iterator dan referensi ke elemen yang dihapus tidak valid [23.3.5.4/3]
• forward_list: hanya iterator dan referensi ke elemen yang dihapus tidak valid (berlaku untuk erase_after) [23.3.4.5/1]
• array: (n / a)

Wadah asosiatif

• [multi]{set,map}: hanya iterator dan referensi untuk elemen yang dihapus tidak valid [23.2.4 / 9]

Wadah asosiatif yang tidak berurutan

• unordered_[multi]{set,map}: hanya iterator dan referensi untuk elemen yang dihapus tidak valid [23.2.5 / 13]

Adaptor kontainer

• stack: diwarisi dari wadah yang mendasarinya
• queue: diwarisi dari wadah yang mendasarinya
• priority_queue: diwarisi dari wadah yang mendasarinya

Mengubah ukuran

• vector: sesuai masukkan / hapus [23.3.6.5/12]
• deque: sesuai masukkan / hapus [23.3.3.3/3]
• list: sesuai masukkan / hapus [23.3.5.3/1]
• forward_list: sesuai masukkan / hapus [23.3.4.5/25]
• array: (n / a)

Catatan 1

Kecuali ditentukan lain (baik secara eksplisit atau dengan mendefinisikan fungsi dalam fungsi lainnya), menjalankan fungsi anggota kontainer atau meneruskan wadah sebagai argumen ke fungsi perpustakaan tidak akan membatalkan iterator untuk, atau mengubah nilai, objek di dalam wadah itu . [23.2.1 / 11]

Catatan 2

fungsi no swap () membatalkan referensi, petunjuk, atau iterator yang merujuk pada elemen wadah yang sedang ditukar. [Catatan: iterator end () tidak merujuk ke elemen apa pun, sehingga mungkin tidak valid . —Kirim catatan] [23.2.1 / 10]

Catatan 3

Selain peringatan di atas tentang swap(), tidak jelas apakah iterator "akhir" tunduk pada aturan per-kontainer yang tercantum di atas ; Anda harus berasumsi bahwa mereka memang demikian.

Catatan 4

vectordan semua wadah asosiatif yang tidak berurutan mendukung reserve(n)yang menjamin bahwa tidak ada pengubahan ukuran otomatis akan terjadi setidaknya sampai ukuran wadah bertambah n. Perhatian harus diambil dengan wadah asosiatif tidak berurutan karena proposal di masa mendatang akan memungkinkan spesifikasi faktor muatan minimum, yang akan memungkinkan pengulangan terjadi insertsetelah eraseoperasi yang cukup mengurangi ukuran wadah di bawah minimum; jaminan harus dianggap berpotensi batal setelah erase.

Hal ini mungkin layak menambahkan bahwa iterator insert apapun ( std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator) dijamin untuk tetap berlaku selama semua sisipan dilakukan melalui iterator ini dan tidak ada yang independen iterator-membatalkan acara lainnya terjadi.

Sebagai contoh, ketika Anda melakukan serangkaian operasi penyisipan ke dalam std::vectordengan menggunakan std::insert_iteratorsangat mungkin bahwa penyisipan ini akan memicu realokasi vektor, yang akan membatalkan semua iterator yang "menunjuk" ke dalam vektor itu. Namun, masukkan iterator yang dipermasalahkan dijamin tetap valid, yakni Anda dapat melanjutkan urutan penyisipan dengan aman. Tidak perlu khawatir tentang memicu realokasi vektor sama sekali.

Ini, sekali lagi, hanya berlaku untuk penyisipan yang dilakukan melalui iterator penyisipan itu sendiri. Jika acara iterator-invalidating dipicu oleh beberapa aksi independen pada container, maka iterator insert menjadi invalidated juga sesuai dengan aturan umum.

Misalnya kode ini

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

dijamin untuk melakukan urutan penyisipan yang valid ke dalam vektor, bahkan jika vektor "memutuskan" untuk merelokasi di suatu tempat di tengah proses ini. Iterator itjelas akan menjadi tidak valid, tetapi it_insakan tetap valid.

Karena pertanyaan ini menarik begitu banyak suara dan jenis menjadi FAQ, saya kira akan lebih baik untuk menulis jawaban terpisah untuk menyebutkan satu perbedaan yang signifikan antara C ++ 03 dan C ++ 11 mengenai dampak std::vectoroperasi penyisipan pada validitas iterator dan referensi sehubungan dengan reserve()dan capacity(), yang gagal dijawab oleh jawaban yang paling dipilih.

C ++ 03:

Realokasi membatalkan semua referensi, pointer, dan iterator yang mengacu pada elemen dalam urutan. Dijamin bahwa tidak ada realokasi yang terjadi selama penyisipan yang terjadi setelah panggilan untuk cadangan () sampai saat penyisipan akan membuat ukuran vektor lebih besar dari ukuran yang ditentukan dalam panggilan terbaru untuk cadangan () .

C ++ 11:

Realokasi membatalkan semua referensi, pointer, dan iterator yang mengacu pada elemen dalam urutan. Dijamin bahwa tidak ada realokasi yang terjadi selama penyisipan yang terjadi setelah panggilan untuk cadangan () sampai saat penyisipan akan membuat ukuran vektor lebih besar dari nilai kapasitas () .

Jadi dalam C ++ 03, ini bukan " unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)" seperti yang disebutkan dalam jawaban lain, melainkan " greater than the size specified in the most recent call to reserve()". Ini adalah satu hal yang berbeda dari C ++ 03 dari C ++ 11. Dalam C ++ 03, setelah suatu insert()menyebabkan ukuran vektor untuk mencapai nilai yang ditentukan dalam reserve()panggilan sebelumnya (yang mungkin bisa lebih kecil dari saat ini capacity()karena reserve()dapat menghasilkan lebih besar capacity()dari yang diminta), setiap berikutnya insert()dapat menyebabkan realokasi dan membatalkan semua iterator dan referensi. Di C ++ 11, ini tidak akan terjadi dan Anda selalu bisa percaya capacity()untuk mengetahui dengan pasti bahwa realokasi berikutnya tidak akan terjadi sebelum ukurannya melampaui capacity().

Kesimpulannya, jika Anda bekerja dengan vektor C ++ 03 dan Anda ingin memastikan realokasi tidak akan terjadi ketika Anda melakukan penyisipan, itu adalah nilai dari argumen yang Anda berikan sebelumnya reserve()bahwa Anda harus memeriksa ukurannya, bukan nilai kembali panggilan ke capacity(), jika tidak, Anda mungkin akan terkejut dengan realokasi " prematur ".

Berikut ini adalah tabel ringkasan bagus dari cppreference.com :

Di sini, penyisipan mengacu pada metode apa pun yang menambahkan satu atau lebih elemen ke wadah dan penghapusan mengacu pada metode apa pun yang menghilangkan satu atau lebih elemen dari wadah.