Iteratoriaus atšaukimo taisyklės

Kokios yra C ++ konteinerių atšaukimo taisyklės?

Pageidautina santraukų sąrašo formatu.

<sub> (Pastaba: tai reiškia, kad rašote į dažniausiai užduodamus klausimus apie C ++ stekų perpildymą . Jei norite kritikuoti idėją pateikti DUK šioje formoje, tuomet skelbimas apie tai prasidėjo . Klausimas stebimas C + + pokalbyje , kur pirmą kartą prasidėjo DUK idėja, todėl jūsų atsakymą greičiausiai skaitys tie, kurie pateikė šią idėją.) Sub>

465
22 июня '11 в 13:01 2011-06-22 13:01 „Orbit“ lengvumo lenktynės nustatomos birželio 22 d. 11 val. 01.01.2011. 2011-06-22 13:01
@ 5 atsakymai

C ++ 17 (Visos nuorodos paimtos iš galutinio CPP17 - n4659 darbo projekto)


įterpti

Sekos konteineriai

  • vector : insert , emplace_back , emplace , „ push_back funkcijos sukelia perskirstymą, jei naujas dydis yra didesnis nei senas. Perskirstymas negalioja visoms nuorodoms, rodyklėms ir iteratoriams, kurie yra sekos elementai. Jei perskirstymas neįvyksta, visi iteratoriai ir nuorodos iki įterpimo taško lieka galioti. [26.3.11.5/1]
    Kalbant apie reserve funkciją, perskirstymas negalioja visoms nuorodoms, rodyklėms ir iteratoriams, kurie yra sekos elementai. Pertvarų, atsiradusių po to, kai reserve() funkcija yra iškviesta, perskirstymas neturėtų įvykti tol, kol įterpimas padidina vektoriaus dydį nei capacity() vertė capacity() . [26.3.11.3/6]

  • deque : įterpimas deque viduryje panaikina visus iteratorius ir nuorodas į deque elementus. Įterpimas bet kokiame deque gale panaikina visus deque iteratorius, bet neturi įtakos nuorodų į deque elementus teisėtumui. [26.3.8.4/1]

  • list : neturi įtakos iteratorių ir nuorodų patikimumui. Jei išimtis išimta, nėra jokio poveikio. [26.3.10.4/1].
    Į šią taisyklę insert funkcijos, insert , emplace_front , emplace_back , emplace , push_front .

  • forward_list : nė vienas insert_after perkrovos neturėtų paveikti iteratorių ir nuorodų patikimumo [26.3.9.5/1]

  • array : Kaip taisyklė , masyvo iteratoriai niekada negalioja visą masyvo naudojimo laiką. Tačiau reikia pažymėti, kad permutacijos metu iteratorius ir toliau nurodys tą patį masyvo elementą ir taip pakeis jo vertę.

Asociatyviniai konteineriai

  • All Associative Containers emplace All Associative Containers : insert ir emplace neturėtų turėti įtakos iteratorių ir konteinerių nuorodų galiojimui [26.2.6 / 9]

Nereguliuojami asociatyvūs konteineriai

  • All Unordered Associative Containers : perrašymas panaikina iteratorius, keičia elementus ir keičia elementus, kuriuose jie rodomi, tačiau negalioja rodyklės ar elementų nuorodos. [26.2.7 / 9]
    emplace insert ir emplace neturėtų turėti įtakos nuorodų į konteinerio elementus teisėtumui, bet gali panaikinti visus konteinerio iteratorius. [26.2.7 / 14]
    insert ir emplace neturėtų paveikti iteratorių galiojimo, jei (N+n) <= z * B , kur N yra elementų skaičius prieš įdėjimo operaciją, n yra įterptų elementų skaičius, B yra konteinerių skaičius, o z - maksimalus koeficientas konteinerio pakrovimas. [26.2.7 / 15]

  • All Unordered Associative Containers a.merge(a2) All Unordered Associative Containers : Sujungimo operacijos atveju (pvz., a.merge(a2) ), iteratoriai, susiję su perduotais elementais, ir visi iteratoriai, susiję su a bus panaikinti, tačiau elementų, likusių a2 , iteratoriai lieka galioti. (91 lentelė. Nereguliuojami reikalavimai asociatyviems konteineriams)

Konteinerių adapteriai

  • stack : paveldėta iš pagrindinio konteinerio
  • queue : paveldėta iš pagrindinio konteinerio
  • priority_queue : paveldėtas iš pagrindinio konteinerio

valymas

Sekos konteineriai

  • vector : erase ir pop_back negaliojantiems iteratoriams ir nuorodos į arba po ištrynimo taško. [26.3.11.5/3]

  • deque : ištrinti operaciją, kuri ištrina paskutinį deque elementą, panaikina tik paskutinį iteratorių ir visus iteratorius bei nuorodas į ištrintus elementus. deque operacija, kuri ištrina pirmąjį deque elementą, bet ne paskutinį elementą, panaikina tik iteratorius ir nuorodas į ištrintus elementus. deque operacija, kuri neištrina nei pirmojo elemento, nei paskutinio deque elemento, panaikina iteratoriaus pabaigą ir visus iteratorius bei nuorodas į visus deque elementus. [Pastaba: pop_front ir pop_back yra trinti operacijos. —Butinė pastaba] [26.3.8.4/4]

  • list : panaikina tik iteratorius ir nuorodas į ištrintus elementus. [26.3.10.4/3]. Tai taikoma erase , pop_front , pop_back , clear funkcijoms.
    remove_if remove remove_if : pašalina visus sąraše esančius elementus, nurodytus sąrašo iteratoriumi i , kuriems taikomos šios sąlygos: *i == value , pred(*i) != false . Neleidžia naudoti iteratorių ir nuorodų į ištrintus elementus [26.3.10.5/15].
    unique nario funkcija - pašalina visus elementus, išskyrus pirmąjį iš kiekvienos iš eilės lygių elementų, nurodytų iteratoriaus i , intervale [first + 1, last) , kuriam *i == *(i-1) (unikalioms versijoms be argumentų) arba pred(*i, *(i - 1)) (unikalios versijos su predikato argumentu). Panaikina tik iteratorius ir nuorodas į ištrintus elementus. [26.3.10.5/19]

  • forward_list : erase_after turėtų panaikinti tik iteratorius ir nuorodas į ištrintus elementus. [26.3.9.5/1].
    remove_if nariai remove remove_if - pašalina visus sąraše esančius elementus, nurodytus sąrašo iteratoriumi i, kuriems taikomos šios sąlygos: *i == value ( remove() ), pred(*i) - tiesa ( remove_if() ) . Panaikina tik iteratorius ir nuorodas į ištrintus elementus. [26.3.9.6/12].
    unique nario funkcija - pašalina visus elementus, išskyrus pirmąjį iš kiekvienos iš eilės lygių elementų grupės, kurią iteratorius nurodo intervale [first + 1, last], kuriam *i == *(i-1) (versijai be argumentų) ) arba pred(*i, *(i - 1)) (versijai su predikatiniu argumentu). Panaikina tik iteratorius ir nuorodas į ištrintus elementus. [26.3.9.6/16]

  • All Sequence Containers : clear panaikina visas nuorodas, nuorodas ir iteratorius, nurodančius elementus a, ir gali panaikinti „pabaigos“ iteratorių (87 lentelė - Reikalavimai sekos talpykloms). Tačiau, jei forward_list , clear į forward_list , clear , negalioja praeities iteratoriai. [26.3.9.5/32]

  • All Sequence Containers : assign panaikina visas nuorodas, nuorodas ir iteratorius, nurodančius konteinerio elementus. Be vector ir deque , jis taip pat panaikina iteratorių po pabaigos. (87 lentelė. Reikalavimai sekos sekai)

Asociatyviniai konteineriai

  • All Associative Containers asociatyvūs All Associative Containers : erase nariai turėtų panaikinti tik iteratorius ir nuorodas į ištrintus elementus [26.2.6 / 9]

  • All Associative Containers : extract nariai panaikina tik ištrintus elementus; nuorodos ir nuorodos į išbrauktą punktą lieka galioti [26.2.6 / 10]

Konteinerių adapteriai

  • stack : paveldėta iš pagrindinio konteinerio
  • queue : paveldėta iš pagrindinio konteinerio
  • priority_queue : paveldėtas iš pagrindinio konteinerio

Bendrieji konteinerio reikalavimai iteratoriaus negaliojimui:

  • Jei nenurodyta kitaip (aiškiai arba apibrėžiant funkciją kitų funkcijų atžvilgiu), skambinant konteinerio nario funkcijai arba perduodant konteinerį kaip argumentą į bibliotekos funkciją, neturėtų būti panaikinti iteratoriai arba keičiamos objektų vertės šioje talpykloje [26.2.1 / 12 ]

  • jokia swap() funkcija nepanaikina jokių nuorodų, nuorodų ar iteratorių, susijusių su konteinerių pakeitimo elementais. [Pastaba: pabaigos () iteratorius nėra susijęs su jokiu elementu, todėl jis gali būti panaikintas. - Galutinė pastaba] [26.2.1 / (11.6)]

Kaip minėtų reikalavimų pavyzdžiai:

  • transform algoritmas: op ir binary_op funkcijos neturėtų panaikinti iteratorių ar subrangų arba keisti elementus intervaluose [28.6.4 / 1]

  • accumulate algoritmą: diapazone [pirmas, paskutinis] binary_op neturėtų keisti elementų ir negalioja iteratorių ar subrangų [29.8.2 / 1]

  • reduce : reduce algoritmas neturėtų panaikinti iteratorių ar subrangų, taip pat neturi keisti diapazono elementų [pirmas, paskutinis]. [29.8.3 / 5]

ir tt ...

9
02 янв. atsakymas duotas PW 02 jan. 2019-01-02 13:44 '19, 13:44 pm 2019-01-02 13:44

C ++ 03 (Šaltinis: „ Iterator“ atšaukimo taisyklės (C ++ 03) )


Įterpti

Sekos konteineriai

  • vector : visi iteratoriai ir nuorodos į įterpimo tašką neturi įtakos, jei naujo konteinerio dydis yra didesnis nei ankstesnė talpa (šiuo atveju visi iteratoriai ir nuorodos negalioja) [23.2.4.3/1]
  • deque : visi iteratoriai ir nuorodos negalioja, jei įterptas elementas nėra denio gale (priekyje arba gale) (šiuo atveju visi iteratoriai yra netinkami, tačiau nuorodos į elementus neturi įtakos) [23.2.1.3/1]
  • list : visi iteratoriai ir nuorodos neturi įtakos [23.2.2.3/1]

Asociatyviniai konteineriai

  • [multi]{set,map} : visi iteratoriai ir nuorodos neturi įtakos [23.1.2 / 8]

Konteinerių adapteriai

  • stack : paveldėta iš pagrindinio konteinerio
  • queue : paveldėta iš pagrindinio konteinerio
  • priority_queue : paveldėtas iš pagrindinio konteinerio

Trinti

Sekos konteineriai

  • vector : kiekvienas iteratorius ir nuoroda po ištrynimo taško negalioja [23.2.4.3/3]
  • deque : visi iteratoriai ir nuorodos negalioja, nebent ištrinti elementai yra denio gale (priekyje arba gale) (šiuo atveju tik iteratoriai ir nuorodos į ištrintus elementus yra neteisingi) [23.2.1.3/4]
  • list : neteisingi tik iteratoriai ir nuorodos į ištrintą elementą [23.2.2.3/3]

Asociatyviniai konteineriai

  • [multi]{set,map} : tik iteratoriai ir nuorodos į ištrintus elementus yra neteisingi [23.1.2 / 8]

Konteinerių adapteriai

  • stack : paveldėta iš pagrindinio konteinerio
  • queue : paveldėta iš pagrindinio konteinerio
  • priority_queue : paveldėtas iš pagrindinio konteinerio

Keisti dydį

  • vector : pagal įterpimą / ištrynimą [23.2.4.2/6]
  • deque : pagal deque / ištrynimą [23.2.1.2/1]
  • list : pagal įrašą / ištrinti [23.2.2.2/1]

1 pastaba

Jei nenurodyta kitaip (aiškiai arba apibrėžiant funkciją kitų funkcijų atžvilgiu), nuoroda į konteinerio nario funkciją arba perduodama konteinerį kaip argumentą bibliotekos funkcijai, neatšaukia iteratorių arba nekeičia šio konteinerio objektų reikšmių. [23.1 / 11]

2 pastaba

„C ++ 2003“ neaišku, ar „galutiniai“ iteratoriai laikosi pirmiau minėtų taisyklių ; bet kuriuo atveju jūs turite daryti prielaidą, kad jie yra (kaip ir praktikoje).

3 pastaba

Nuorodų negaliojimo taisyklės yra pavadinimai kaip nuorodų panaikinimo taisyklės.

400
22 июня '11 в 13:01 2011-06-22 13:01 atsakymas į šviesumo lenktynes ​​Orbitoje pateiktas birželio 22 d. 11 val. 01.01. 2011-06-22 13:01

C ++ 11 (Šaltinis: „ Iterator“ atšaukimo taisyklės (C ++ 0x) )


Įterpti

Sekos konteineriai

  • vector : visi iteratoriai ir nuorodos iki įterpimo taško neturi įtakos, jei naujo konteinerio dydis yra didesnis nei ankstesnė talpa (šiuo atveju visi iteratoriai ir nuorodos negalioja) [23.3.6.5/1]
  • deque : visi iteratoriai ir nuorodos negalioja, jei įterptas elementas nėra detex gale (priekyje arba gale) (šiuo atveju visi iteratoriai yra netinkami, tačiau nuorodos į elementus neturi įtakos) [23.3.3.4/1]
  • list : visi iteratoriai ir nuorodos neturi įtakos [23.3.5.4/1]
  • forward_list : visi iteratoriai ir nuorodos nedaro įtakos ( insert_after ) [23.3.4.5/1]
  • array : (n / a)

Asociatyviniai konteineriai

  • [multi]{set,map} : visi iteratoriai ir nuorodos neturi įtakos [23.2.4 / 9]

Neišrūšiuoti asociatyvūs konteineriai

  • unordered_[multi]{set,map} : visi pakartotinio įkėlimo iteratoriai negalioja, bet nuorodos neturi įtakos [23.2.5 / 8]. Pakartotinis atkūrimas neįvyksta, jei įterpimas nereiškia, kad konteineris yra didesnis nei z * B , kur z yra didžiausias apkrovos koeficientas, o B - dabartinis kibirų skaičius. [23.2.5 / 14]

Konteinerių adapteriai

  • stack : paveldėta iš pagrindinio konteinerio
  • queue : paveldėta iš pagrindinio konteinerio
  • priority_queue : paveldėtas iš pagrindinio konteinerio

Trinti

Sekos konteineriai

  • vector : kiekvienas iteratorius ir nuoroda ištrynimo taške arba po jo yra neteisingi [23.3.6.5/3]
  • deque : paskutinio elemento trynimas panaikina tik iteratorius ir nuorodas į ištrintus elementus ir praeities pabaigos iteratorių; pirmojo elemento ištrynimas panaikina tik iteratorius ir nuorodas į ištrintus elementus; bet kokių kitų elementų ištrynimas panaikina visus iteratorius ir nuorodas (įskaitant ankstesnį iteratorių) [23.3.3.4/4]
  • list : neteisingi tik iteratoriai ir nuorodos į ištrintą elementą [23.3.5.4/3]
  • forward_list : tik iteratoriai ir nuorodos į ištrintą elementą yra negaliojantys (taikomi erase_after ) [23.3.4.5/1]
  • array : (n / a)

Asociatyviniai konteineriai

  • [multi]{set,map} : tik iteratoriai ir nuorodos į ištrintus elementus yra neteisingi [23.2.4 / 9]

Nereguliuojami asociatyvūs konteineriai

  • unordered_[multi]{set,map} : tik iteratoriai ir nuorodos į ištrintus elementus yra neteisingi [23.2.5 / 13]

Konteinerių adapteriai

  • stack : paveldėta iš pagrindinio konteinerio
  • queue : paveldėta iš pagrindinio konteinerio
  • priority_queue : paveldėtas iš pagrindinio konteinerio

Keisti dydį

  • vector : pagal įterpimą / ištrynimą [23.3.6.5/12]
  • deque : pagal įterpimo / ištrynimo duomenis [23.3.3.3/3]
  • list : pagal įrašą / ištrinti [23.3.5.3/1]
  • forward_list : pagal įterpti / ištrinti [23.3.4.5/25]
  • array : (n / a)

1 pastaba

Jei nenurodyta kitaip (aiškiai arba apibrėžiant funkciją kitų funkcijų atžvilgiu), nuoroda į konteinerio nario funkciją arba perduodama konteinerį kaip argumentą bibliotekos funkcijai, neatšaukia iteratorių arba nekeičia šio konteinerio objektų reikšmių. [23.2.1 / 11]

2 pastaba

Funkcija

be apsikeitimo () neteisingos nuorodos, nuorodos ar iteratoriai, susiję su konteinerio elementais, yra keičiami. [Pastaba: pabaigos () iteratorius nepriklauso vienam, todėl jis gali būti neteisingas . -įrašyti pastabą] [23.2.1 / 10]

3 pastaba

Be pirmiau minėto atsakomybės atsisakymo dėl swap() , neaišku, ar „galutiniai“ iteratoriai laikosi pirmiau nurodytų taisyklių kiekvienam konteineriui ; jūs bet kuriuo atveju turite daryti prielaidą, kad jie yra.

4 pastaba

vector ir visas nereguliuojamasis asociatyvių konteinerių palaikymo reserve(n) , kuris užtikrina, kad automatiškai keisti dydį nebus, bent jau tol, kol konteinerio dydis nepadidės iki n . Turi būti pasirūpinta nesereguliuotais asociatyviais konteineriais, nes ateityje pasiūlymas leis jums nurodyti minimalų apkrovos koeficientą, kuris leistų jums pakartoti operaciją ant insert po to, kai erase operacijos sumažina talpyklos dydį žemiau minimalaus; garantija turi būti laikoma negaliojančia po erase .

340
22 июня '11 в 18:53 2011-06-22 18:53 atsakymas į Lengvumo lenktynes ​​Orbitoje pateikiamas birželio 22 d. 11 val.

Tikriausiai verta pridurti, kad bet koks bet kokio tipo ( std::back_insert_iterator , std::front_insert_iterator , std::insert_iterator ) įterpiamasis iteratorius bus garantuotas, kol visi įterpimai bus vykdomi per šį iteratorių, o kiti nepriklausomi iteratoriai nepanaikina įvykio vyksta.

Pvz., Kai atliekate įterpimo operacijų seriją į std::vector naudodami std::insert_iterator yra įmanoma, kad šie std::insert_iterator perskirstys vektorių, kuris panaikins visus iteratorius, kurie „taškus“ į šį vektorių. Tačiau užtikrinama, kad atitinkamas įterpiamasis iteratorius lieka galioti, ty galite saugiai tęsti įterpimų seką. Nereikia nerimauti dėl perskirstymo vektoriaus pradžios.

Tai dar kartą reiškia tik įterpimus, įvykdytus per vidų iteratorių. Jei iteratoriaus atšaukimo įvykį sukelia nepriklausomas veiksmas ant konteinerio, įterpimo iteratorius taip pat tampa negaliojantis pagal bendrąsias taisykles.

Pavyzdžiui, šis kodas

 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(); 

garantuojama, kad vektorius atliks galiojančią intarpų seką, net jei vektorius „nusprendžia“ perskirstyti kažkur šio proceso viduryje. Iteratorius, žinoma, taps negaliojančiu, bet it_ins ir toliau galios.

39
05 июля '12 в 2:36 2012-07-05 02:36 atsakymą pateikė AnT liepos 5 d. 12 d. 2:36 2012-07-05 02:36

Kadangi šis klausimas pritraukia tiek daug balsų, ir atrodo, kad jis tampa DUK, manau, kad geriau būtų parašyti atskirą atsakymą, kuriame būtų paminėtas vienas svarbus skirtumas tarp C ++ 03 ir C ++ 11 dėl std::vector įterpimo poveikio iteratorių ir nuorodų realybei atsižvelgiant į reserve() ir capacity() , kurių nebuvo galima matyti naudojant dažniausiai naudojamą atsakymą.

C ++ 03:

Perskirstymas viršija visas nuorodas, nuorodas ir iteratorius, nurodydamas sekos elementus. Garantuojama, kad įterpimo metu nereikės perskirstymo, kuris atsiranda po to, kai vadinamas rezervas (), kol įterpimas padarys vektoriaus dydį didesnį už dydį, nurodytą paskutiniame kvietime rezervuoti () .

C ++ 11:

Perskirstymas viršija visas nuorodas, nuorodas ir iteratorius, nurodydamas sekos elementus. Garantuojama, kad įterpimo metu, atsiradusio po to, kai rezervas () yra iškviestas tol, kol nebus įterpiamas, vektoriaus dydis bus didesnis už talpos vertę () .

Taigi, C ++ 03, tai nėra " unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) ", kaip nurodyta kitame atsakyme, o ne turėtų būti " greater than the size specified in the most recent call to reserve() . Tai yra vienas dalykas, kad C ++ 03 skiriasi nuo C ++ 11. C ++ 03, kai insert() sukelia vektoriaus dydį iki ankstesniame kvietime reserve() (kuri gali būti mažesnė už dabartinę capacity() , nes reserve() gali lemti didesnį capacity() nei užklausą), bet koks vėlesnis insert() gali perskirstyti ir panaikinti visus iteratorius ir nuorodas. C ++ 11 tai neįvyks, ir jūs visada galite pasitikėti capacity() su pasitikėjimu, kad sužinotumėte, jog kitas perskirstymas nebus įvykdytas prieš tai, kai dydis viršys capacity() .

В заключение, если вы работаете с вектором С++ 03, и вы хотите убедиться, что перераспределение не произойдет, когда вы выполните вставку, это значение аргумента, который вы ранее передали в reserve() , который вы должны проверьте размер, а не возвращаемое значение вызова capacity() , иначе вы можете удивляться "преждевременному" перераспределению.

22
ответ дан neverhoodboy 08 марта '14 в 5:24 2014-03-08 05:24

Другие вопросы по меткам или Задайте вопрос