[C++] Gedrag van list::erase

[jsiegmund]

Ik loop met een iterator door een lijst van een willekeurig type, en verwijder wat waarden uit die lijst. Nu loopt m'n programmacode steeds vast op het punt dat hij aankomt bij de plaats waar een waarde stond die verwijderd is. Ik dacht dat het ophogen van de iterator netjes een pointer naar het volgende element in de lijst zou geven, tot aan het einde. Maar hij point nu dus naar een geheugenplaats waar een waarde stond die ik ge-erased heb. Hoe kun je dit vermijden of oplossen?

[Verwijderd]

Ik begrijp niet precies wat je doet, maar na een erase(it), wordt it invalid. Doe je na de erase er nog iets mee? Kijk er eens naar.

[Zoijar]

Dat komt omdat een iterator die naar een element wijst dat verwijderd is, niet meer valid is. De oplossing is om eerst je iterator te verhogen, en dan pas het element te wissen. Dus iets van

C++:

for (container::iterator i = list.begin(); i != list.end();) {
   if (needs_del) {list.erase(i++);}
   else {++i;}
}

[ Voor 13% gewijzigd door Zoijar op 13-06-2005 15:04 . Reden: for loopje erbij ]

[MSalters]

list::erase invalideert precies 1 iterator waarde, namelijk naar het element wat je net verwijderd hebt. Je kunt 'm dus ook niet meer verhogen, want onder water is dat typisch een 'ptr = ptr->next' assignment waarbij *ptr en dus ook ptr->next zojuist weggegooid is.

Gelukkig krijg je van list::erase (iterator) de daaropvolgende iterator terug.

[Zoijar]

earse(i++) werkt ook, omdat je erase call de (oude) waarde van i krijgt, en i eerst wordt opgehoogd voor de functie call, ie. fetch&increment. (daarom is ++i ook iha efficienter, omdat er dan geen temporary copy gemaakt hoeft te worden)

[.oisyn]

Zoijar schreef op maandag 13 juni 2005 @ 15:28:
(daarom is ++i ook iha efficienter, omdat er dan geen temporary copy gemaakt hoeft te worden)

Dat zijn echter fabeltjes, de temporary wordt over het algemeen gewoon weggeoptimized (een iterator is vaak ook niet meer dan een pointer naar een node of element) (hetzelfde geldt ook voor elke iteratie weer comparen tegen end())

[ Voor 9% gewijzigd door .oisyn op 13-06-2005 16:09 ]

[Zoijar]

.oisyn schreef op maandag 13 juni 2005 @ 16:07:
Dat zijn echter fabeltjes, de temporary wordt over het algemeen gewoon weggeoptimized

Mwa, in dit geval misschien wel, maar bij een reference counted big int class misschien wel niet...

[.oisyn]

het ging over STL iterators, niet over refcounted bigint classes

[ Voor 4% gewijzigd door .oisyn op 13-06-2005 17:19 ]

[Zoijar]

Maar van een iterator weet je ook niet wat het is. STL bouwt er juist op dat er geen onnodige aannames gedaan worden over (generieke) ojecten. Oh well Het ging er idd niet om.

[MSalters]

.oisyn schreef op maandag 13 juni 2005 @ 16:07:
[...]
Dat zijn echter fabeltjes, de temporary wordt over het algemeen gewoon weggeoptimized (een iterator is vaak ook niet meer dan een pointer naar een node of element) (hetzelfde geldt ook voor elke iteratie weer comparen tegen end())

end() is (uit m'n hoofd) bij alle STL containers een O(1) operatie.

Het verhaal van i++ vs ++i is geen fabeltje, alleen de classes waarbij het grootste verschil zit zijn juist die simpele iterators die je als beginner het meeste gebruikt. Een projectie iterator zit niet in de standaard library, maar alle implementaties ervan hebben zware iterators - zeker als de onderliggende iterator meer is dan een T*. Omdat dat soort iterators minder snel inlined is de kans voor een optimizer om het verschil te elimineren bovendien kleiner.

[Soultaker]

Sowieso moet je als serieuze C++-programmeur het verschil kennen (PHP-programmeurs hebben bijvoorbeeld in het algemeen geen flauw idee); wat is er dan op tegen om je aan te wennen om de preincrement-operator te gebruiken tenzij je specifiek de oude waarde nodig hebt? Ik gebruik zelf de preincrement-operator altijd wanneer ik de return value niet nodig heb; als je dat consistent toepast is de afwijkende situatie duidelijk genoeg.

MSalters schreef op maandag 13 juni 2005 @ 21:06:
Het verhaal van i++ vs ++i is geen fabeltje, alleen de classes waarbij het grootste verschil zit zijn juist die simpele iterators die je als beginner het meeste gebruikt. [..] Omdat dat soort iterators minder snel inlined is de kans voor een optimizer om het verschil te elimineren bovendien kleiner.

Dat zeg je nu wel, maar het lijkt me dat zo'n postincrement-operator op z'n simpelst zo gedefinieerd wordt:

C++:

inline T incr(T &v) {
  T old = v;
  ++v;
  return old;
}

C++ staat de compiler in ieder geval expliciet toe de kopie van de return value weg te optimaliseren. Aangezien de call geïnlined wordt, heeft de compiler ook wel door dat de kopie helemaal nergens gebruikt wordt, dus met een beetje mazzel kan 'ie die hele 'old' variabele weghalen (of dat echt gebeurt hangt maar net af van welke side effects de copy constructor en destructor van T hebben), waardoor de postincrement-operatie effectief omgeschreven is naar een preincrement-operatie.

Het lijkt mij dat deze situatie zich redelijk vaak voordoet, maar dat is meer op gevoel dan dat ik het echt onderzocht heb. In de STL zijn iterators van containers sowieso meestal (altijd?) verpakte pointers, dus daar kan het niet echt uitmaken.

[Zoijar]

Soultaker schreef op dinsdag 14 juni 2005 @ 00:37:
C++ staat de compiler in ieder geval expliciet toe de kopie van de return value weg te optimaliseren.

Volgens mij alleen als de return als unnamed temporary gegenereerd wordt. Dus iets als "return MyClass(x,y,z); Dit een local, named variabele, en die mag je niet zo maar weg optimizen. Het is in ieder geval niet een standaard optimalisatie; itt. de unamed temporary, die heel specifiek 'return value optimization' heet.

[.oisyn]

Het gaat erom dat de compiler de functie als inline ziet en daardoor precies de lifetime van die variabele kan tracken, en dus weg kan optimizen.

[jsiegmund]

Hmm okee, het probleem is me wel duidelijk maar hoe kom ik er nu handig vanaf.. ik heb 2 iteratoren, zeg iter1 en iter2... die eerste doorloopt een lijst van voor naar achter totdat ie bij het einde is. De 2e echter pikt a.d.h.v. een aantal criteria steeds een index uit de lijst die verwijderd moet worden, deze is dus *ergens* in de lijst. Het gaat fout op het moment dat iter2 een waarde verwijderd heeft waar iter1 na een tijdje overheen gaat. Uiteraard is dat logisch, maar hoe los je dat op? Eigenlijk moet de lijst na de erase gewoon weer netjes aaneensluitend zijn, zodat de eerste iter door kan lopen.

[Woy]

Het lijkt me dat je lijst nog steeds gewoon aaneengesloten is als je er een Item uit gegooid hebt. Het lijkt me alleen een probleem als Iter1 en Iter2 naar hetzelfde element wijzen en dan gooi je het element waar iter1 naar wijst weg.

Maar mischien begrijp ik het niet helemaal goed.

[Verwijderd]

rwb schreef op dinsdag 14 juni 2005 @ 14:13:
Het lijkt me dat je lijst nog steeds gewoon aaneengesloten is als je er een Item uit gegooid hebt. Het lijkt me alleen een probleem als Iter1 en Iter2 naar hetzelfde element wijzen en dan gooi je het element waar iter1 naar wijst weg.

Maar mischien begrijp ik het niet helemaal goed.

Dat lijkt misschien wel zo, maar helaas betekent dat niet dat een iterator per definitie altijd geldig is.
Als je een iterator hebt die naar element X wijst, en je voert een erase uit op dat element, dan staat die iterator na die erase ins blauwe Hinein te wijzen; je kunt dus geen 'next' of '++' meer op die iterator doen.
Je moet derhalve, als je belsuit een element te wissen, eerst een tijdelijke iterator aanmaken die naar het te wissen element wijst; daarna je loop-iterator naar het volgende element zetten, en daarna de erase op de tijdelijke iterator uitvoeren.

De erase zou inderdaad een iterator naar het volgende element moeten teruggeven, maar ik ben gevallen tegengekomen waar hij dat niet deed; dan is dit dus de veiligste methode.

[Woy]

Verwijderd schreef op dinsdag 14 juni 2005 @ 14:23:
[...]


Dat lijkt misschien wel zo, maar helaas betekent dat niet dat een iterator per definitie altijd geldig is.
Als je een iterator hebt die naar element X wijst, en je voert een erase uit op dat element, dan staat die iterator na die erase ins blauwe Hinein te wijzen; je kunt dus geen 'next' of '++' meer op die iterator doen.
Je moet derhalve, als je belsuit een element te wissen, eerst een tijdelijke iterator aanmaken die naar het te wissen element wijst; daarna je loop-iterator naar het volgende element zetten, en daarna de erase op de tijdelijke iterator uitvoeren.

De erase zou inderdaad een iterator naar het volgende element moeten teruggeven, maar ik ben gevallen tegengekomen waar hij dat niet deed; dan is dit dus de veiligste methode.

Ik zeg toch ook nergens dat dat niet zo is. Ik zeg alleen dat je lijst wel gewoon aaneengesloten blijft als je een item verwijderd. Een andere iterator kan er dan nog steeds gewoon doorheen lopen. Alleen als die iterator toevallig naar het element wijst wat je verwijderd hebt dan heb je een probleem.

[Zoijar]

iCe01 schreef op dinsdag 14 juni 2005 @ 12:33:
Hmm okee, het probleem is me wel duidelijk maar hoe kom ik er nu handig vanaf.. ik heb 2 iteratoren, zeg iter1 en iter2... die eerste doorloopt een lijst van voor naar achter totdat ie bij het einde is. De 2e echter pikt a.d.h.v. een aantal criteria steeds een index uit de lijst die verwijderd moet worden, deze is dus *ergens* in de lijst. Het gaat fout op het moment dat iter2 een waarde verwijderd heeft waar iter1 na een tijdje overheen gaat. Uiteraard is dat logisch, maar hoe los je dat op? Eigenlijk moet de lijst na de erase gewoon weer netjes aaneensluitend zijn, zodat de eerste iter door kan lopen.

Oa zoals ik oven al poste, maar je kan ook gewoon een STL functie gebruiken... predicate remove() zou een goeie zijn? Post anders eens code...

[MSalters]

Zoijar schreef op dinsdag 14 juni 2005 @ 11:10:
[...]

Volgens mij alleen als de return als unnamed temporary gegenereerd wordt. Dus iets als "return MyClass(x,y,z); Dit een local, named variabele, en die mag je niet zo maar weg optimizen. Het is in ieder geval niet een standaard optimalisatie; itt. de unamed temporary, die heel specifiek 'return value optimization' heet.

NRVO bestaat evengoed, en mag ook. De reden is dat het object wat geretourneerd wordt zelf altijd unnamed is.
Een dieper probleem is dat in implementaties blijkt dat het relatief makkelijk is om RVO of NRVO te doen, maar beide is lastiger.

[MSalters]

Soultaker schreef op dinsdag 14 juni 2005 @ 00:37:
... het lijkt me dat zo'n postincrement-operator op z'n simpelst zo gedefinieerd wordt:

C++:

inline T incr(T &v) {
  T old = v;
  ++v;
  return old;
}

C++ staat de compiler in ieder geval expliciet toe de kopie van de return value weg te optimaliseren. Aangezien de call geïnlined wordt,

Onterechte aanname, denk ik. Typisch zijn ook de copy ctor en pre-increment ook inlined. De vraag is dan voor de compiler, volg ik alle drie de hints op, of wordt het totaal dan te groot?

In de STL zijn iterators van containers sowieso meestal (altijd?) verpakte pointers, dus daar kan het niet echt uitmaken.

std::deque<>::iterator is dat volgens mij zelden (segmented array, dus een segment identifier en index binnen segment), maar voor vector, list, en associatieve containers geldt dat natuurlijk wel vaak ( afgezien van vector kunnen ze allemaal als node-based worden geimplementeerd).

unordered_maps (hashes) gaan in C++0x weer wat complexere iterators krijgen.

Input iterators zijn natuurlijk een ander verhaal, die hebben alleen ++i. De waarde van i++ is onzinnig, je kunt niet bij de oude waarde als je de nieuwe hebt.

[MSalters]

Verwijderd schreef op dinsdag 14 juni 2005 @ 14:23:
De erase zou inderdaad een iterator naar het volgende element moeten teruggeven, maar ik ben gevallen tegengekomen waar hij dat niet deed; dan is dit dus de veiligste methode.

Oh? " The iterator returned from a.erase(q) points to the element immediately following q prior to the element being erased. If no such element exists, a.end() is returned."
Uiteraard geldt dat voor sequences en niet voor de associatieve containers (map/set) maar dat zijn ook hele andere containers.

[Soultaker]

MSalters schreef op dinsdag 14 juni 2005 @ 22:47:
Onterechte aanname, denk ik. Typisch zijn ook de copy ctor en pre-increment ook inlined. De vraag is dan voor de compiler, volg ik alle drie de hints op, of wordt het totaal dan te groot?

Accoord, maar als je iterator een beetje simpel is, dan is de code die in de plaats van de function call komt net zo simpel of simpeler dan de function call die er eerst stond. Dan lijkt het me niet onredelijk dat de compiler nog eens wil inlinen want ook al heeft 'ie dat al een paar keer gedaan, de code is er niet groter van geworden. Dat geldt zeker voor pointers maar ook wel nog wel voor deque-iterators lijkt me.

Alle praat over optimalisaties die een compiler doet zijn toch een beetje loos (voor zover de standaard ze toelaat tenminste) omdat niemand kan garanderen wat een compiler wel of niet doet. Een aanname die voor de ene compiler onterecht is kan voor een andere vanzelfsprekend zijn.

[ Voor 22% gewijzigd door Soultaker op 15-06-2005 01:18 ]

[Zoijar]

Compilers optimaliseren een stuk meer dan je niet denkt, en een stuk minder dan je wel denkt... Daarom was mijn punt dat het het veiligste is om wel gewoon ++i te gebruiken als je weet dat je alleen ++i nodig hebt. Je weet niet met wat voor iterator je te maken hebt, je weet niet met wat voor implementatie je te maken hebt (O(1) kan wel degelijk langzamer zijn dan O(n^2) voor een specifiek geval) en je weet niet met wat voor compiler je te doen heb...daarom, als je wel weet dat je geen "previous value" nodig hebt, gebruik dan gewoon ++i. Worst case is het gelijke performance. Inline is bv zo'n mooie compiler hint die vaak domweg genegeerd wordt. Je denkt vaak zelf dat je een functie makkelijk kan inlinen, maar een compiler ziet dan weer alle mogelijkheden, en beslist dat het net niet kan in een van de gevallen. Of je compiler ziet net weer niet dat alle mogelijkheden eigenlijk hetzelfde zijn; iets dat jij wel weer ziet...zet je geld gewoon op safe...