[C++] Verwijderen uit vector terwijl iterating

[TheBlasphemer]

Hey,

Ik zoek iets om tijdens het doorlopen van een vector een van de elementen te verwijderen.
Waar ik zelf mee kwam was dit:

code:

          vector<Player *>::iterator plyr,nextplyr;
          for (plyr=vPlayers.begin(); plyr!=vPlayers.end();) {
              nextplyr=plyr+1;
              if (!(*plyr)->PreSelect(&readfds,&writefds,&errorfds,&highest)) {
                delete (*plyr);
                vPlayers.erase(plyr);                                                      
              }
              plyr=nextplyr;  
          }

echter crashed hij bij het deleten
Ik heb al even gegoogled, maar zou zo snel niet weten welke trefwoorden ik hiervoor moet gebruiken
Weet iemand misschien hoe je zoiets oplost ?

Alvast bedankt,
TB

[styno]

Wellicht handig om regel 5 en 6 om te wisselen.

[ Voor 5% gewijzigd door styno op 23-01-2006 13:27 ]

[Zoijar]

iterator invalidation...zoek daar maar op

als je delete uit een vector invalidate je al je iterators... wat je hier wilt is een list, waar je uit kan erasen zonder alle overige iterators dan degene die je erased te invalidaten.

En uiteraard is std::remove_if() nog beter dan het zelf doen, of eerst een transform() oid. Vector van raw pointers, leuk, wat gebeurt er als iets een exception gooit tijdens het doorlopen en deleten?

[TheBlasphemer]

Styno schreef op maandag 23 januari 2006 @ 13:26:
Wellicht handig om regel 5 en 6 om te wisselen.

de delete (*plyr) die delete het player object, maar laat de pointer (die in de vector staat) alleen. Daarna moet die pointer pas uit de vector. heb al geprobeerd om te draaien, maar dat gaf zelfde (crash) effect.

[.oisyn]

Styno schreef op maandag 23 januari 2006 @ 13:26:
Wellicht handig om regel 5 en 6 om te wisselen.

Dat zou ik maar niet doen.

TheBlasphemer: vector::erase returnt een iterator naar het volgende element, gebruik die om aan plyr toe te kennen (en je zou een else kunnen maken waarin je plyr ophoogt, zodat die hele nextplyr niet nodig is)

[ Voor 37% gewijzigd door .oisyn op 23-01-2006 13:37 ]

[Zoijar]

copy_if is hier overigens ideaal, maar de STL bevat die helaas niet. Boost wel ( http://www.crystalclearso...lgorithmExtensions/CopyIf ) Maar je kan ook zelf een simpele functor gebruiken die een back_inserter en een unary predicate als argument krijgt, en dan een transform daarmee doen.

Grappig toch hoeveel mensen de STL gebruiken, en hoe weinig weten hoe je hem moet gebruiken....

(de return van vector::erase zou je kunnen gebruiken, maar realiseer je wel dat hoogst waarschijnlijk de gehele vector gekopieerd wordt, of opgeschoven... die maakt jouw doorlopen van N items een mooie N^2 operatie, ipv linear. Niet echt fijn)

[ Voor 23% gewijzigd door Zoijar op 23-01-2006 13:42 ]

[TheBlasphemer]

.oisyn schreef op maandag 23 januari 2006 @ 13:32:
[...]


Dat zou ik maar niet doen.

TheBlasphemer: vector::erase returnt een iterator naar het volgende element, gebruik die om aan plyr toe te kennen (en je zou een else kunnen maken waarin je plyr ophoogt, zodat die hele nextplyr niet nodig is)

Bedankt! deze tip werkte
Misschien wordt het nu wel een N^2 zoals Zoijar zei, maar aangezien er maar zelden entries gedelete worden (alleen als spelers disconnecten) zal dit wel mevallen

[.oisyn]

Zoijar schreef op maandag 23 januari 2006 @ 13:38:
(de return van vector::erase zou je kunnen gebruiken, maar realiseer je wel dat hoogst waarschijnlijk de gehele vector gekopieerd wordt, of opgeschoven... die maakt jouw doorlopen van N items een mooie N^2 operatie, ipv linear. Niet echt fijn)

Big deal, het zijn pointers, dat kost practisch niets
Als de order niets uitmaakt zou je 'm evt. kunnen swappen met het laatste element in de vector, en vervolgens een pop_back kunnen doen.

[ Voor 16% gewijzigd door .oisyn op 23-01-2006 13:52 ]

[Zoijar]

Misschien maakt het niet zo veel uit, maar waarom zou je moedwillig een lastig op te sporen (performance) bug laten zitten? Dat soort dingen zorgt dus echt voor slechte software tegenwoordig... "ach, O(n) of O(n^2) wat maakt het uit..." totdat de software en het applicatie domein groeit... klassieke fout. Mijn favoriet is alle elementen (shared-pointers ipv raw) die je nog gebruikt kopieren naar een nieuwe vector (die je wel resized van te voren naar bv 110%!) en daarna je oude vector gewoon weg gooien waarbij alles automatisch wordt opgeruimd. Minder fout gevoelig, niet n^2, en je vector blijft ook niet heel groot.

Een swap en een pop_back is wel een goed idee ja. En dan niet vergeten om hetzelfde element weer te bekijken. Of dus gewoon een list gebruiken. Hoewel het swap/pop_back hetzelfde is als het standaard beschikbare remove_if(). Dat is misschien nog wel mooier. remove_if zet alle items die voldoen aan de if aan het einde van de vector in lineaire tijd, en returned dan de nieuwe range. Vervolgens kan je van [new_end, end) lopen, alles wissen, en dan je vector shrinken tot new_end (hij blijft dan wel groot, als je het geheugen echt terug wilt moet je alsnog copy/swap gebruiken)

[.oisyn]

Op het moment dat je vaak veel elementen uit een vector moet verwijderen is het tijd om je af te vragen of een vector wel de geschikte container was in the first place.

[Verwijderd]

Let op als je erase in een for loop gebruikt: de increment operator kan er dan voor zorgen dat bij een erase het volgende element wordt overgeslagen. Zie het volgende stukje code:

code:

for (some_iter iter=container.begin(); iter!=container.end(); iter++) {
  if (remove) iter = container.erase(iter);
}

Bij een erase wordt hier de iterator tweemaal verhoogd, eenmaal door de erase operatie en daarna door de increment operator van de for loop. Dit kan hele lelijke bugs tot gevolg hebben (tell me about it). Beter is dus een while loop te gebruiken for for_each, of de increment operator uit de for constructie halen:

code:

for (some_iter iter=container.begin(); iter!=container.end();) {
  if (remove) iter = container.erase(iter);
  else iter++;
}

[MSalters]

Wat is er mis met std::remove_if? Dat is precies hiervoor uitgevonden.