STL Vector: Element entfernen

[THX 1138]

hi

hilfe, entweder bin ich zu blöd oder schon zu lang wach

folgendes:

void rabbit_manager::eat()
{
	for( r_iter it=my_rabbits.begin(); it != my_rabbits.end(); it++ ) {
		if( !(*it)->eat() )
			delete *it;
	}
}

will einfach nicht gehn.
der hase soll fressen, und wenn er nichts kriegt sterben.

aber ich hab dauernd exceptions wie die folgende

First chance exception at $7C81EB33. Exception class EAccessViolation with message 'Access violation at address 00403DDD in module 'RabbitHabit.exe'. Read of address 626264BA'. Process RabbitHabit.exe (2808)

ohne die zeile

delete *it;

gehts eben, aber der rabbit tut nicht sterben, logischerweise.

steh echt aufm schlauch
danke schonmal

[Caipi]

Hallo,
Kann keinen Fehler entdecken. Wie sieht die Definition des std::vektors mit den rabbits denn aus und wie fügst du einen rabbit hinzu?

Gruß Caipi

[finix]

Du löscht die Toten irgendwie nicht gleich aus dem Container... kann's sein dass du später nochmal versuchst auf verweste Hasen zuzugreifen?

[evilissimo]

finix schrieb:

Du löscht die Toten irgendwie nicht gleich aus dem Container... kann's sein dass du später nochmal versuchst auf verweste Hasen zuzugreifen?

"verweste Hasen"

@1310-Logik

Du musst die Leiche mit Hilfe des Iterators auch noch aus dem vector löschen.

void rabbit_manager::eat()
{
    r_iter it=my_rabbits.begin();
    while(it != my_rabbits.end()){
        if( !(*it)->eat() ){
            delete *it;
            it = vec.erase(it);
            continue;
        }
        ++it;
    }
}

das zuweisen des rückgabewerts von erase ist wichtig damit dein iterator gültig bleibt.

Nun klappts auch mit den(/m) Hasen (Nachbarn) *g*

[THX 1138]

ah danke evilissimo
das wirds sein

versuch tatsächlich später nochmal verweste hasen zu bewegen
ihh leichenfläderei

hab die löschroutine einfach aus dem destruktor kopiert und mit if abfrage versehn. mir fehlt noch etwas übung mit stl containern.
werds dann mal probiern mit erase

jo danke euch allen

[Braunstein]

Hallo,

Hier nur noch ein Beispiel ohne while

struct rabbitdie
{
       bool operator()( rabbit*& elem)
       {
            if( !elem->eat() )
            {
              delete elem; 
              return true;
            }
            return false;
       }
};

void rabbit_manager::eat()
{
   my_rabbits.erase(remove_if(my_rabbits.begin(), my_rabbits.begin(), rabbitdie()), my_rabbits.end());
}

[THX 1138]

kapier ich jetzt ned
was macht den

remove_if(...)

ist es ohne while den besser/schneller?
ich hab zwischen 50 und 500 hasen zu erwarten.
denn die vermehren sich wie die karnickel

thx

[CStoll]

remove_if() "löscht" alle Elemente des Vektors, für die das gegebene Prädikat false zurückgegeben hat (in dem Beispiel bedeutet false "der Hase ist verhungert") - das darumliegende erase() kürzt deinen Vektor dann entsprechend.

(und ja, es dürfte schneller sein, da es nur einmal über die komplette Liste läuft - die while()-Schleife muß bei jedem verhungerten Hasen alle Nachfolger nach vorne kopieren)

[HumeSikkins]

http://www.sgi.com/tech/stl/remove_if.html

Wichtig ist, dass remove_if nicht wirklich Elemente entfernt (es hat keinen Zugriff auf den Container). Es baut die Sequenz nur so um, dass alle Elemente, die das Prädikat nicht erfüllen im Bereich [begin, newEnd) liegen. Die Elemente im Bereich [newEnd, oldEnd) sind nachher unbestimmt, aber keines liefert false wenn man das Prädikat darauf anwendet.

[THX 1138]

HumeSikkins schrieb:

...Die Elemente im Bereich [newEnd, oldEnd) sind nachher unbestimmt..

gibt das dann nicht ein speicherleck, oder wird das mit erase weggemacht?

[THX 1138]

ahso ne sorry
habs geschnallt.
remove_if gibt nen iterator zurück, alles klar

soweit danke euch allen
werds später gleich testen

[camper]

CStoll schrieb:

remove_if() "löscht" alle Elemente des Vektors, für die das gegebene Prädikat false zurückgegeben hat (in dem Beispiel bedeutet false "der Hase ist verhungert") - das darumliegende erase() kürzt deinen Vektor dann entsprechend.

(und ja, es dürfte schneller sein, da es nur einmal über die komplette Liste läuft - die while()-Schleife muß bei jedem verhungerten Hasen alle Nachfolger nach vorne kopieren)

ich kann nicht erkennen, dass es mit remove_if schneller läuft. da remove_if die zugrunde liegende sequenz intakt und die elemente, die dem prädikat nicht entsprechen, in reihenfolge lässt, kann das ganze nur durch umkopieren von elementen in derselben grössenordnung erreicht werden (der algorithmus, den ich im sinn habe, hat O(n*m), n=elemente im container, m=anzahl der 'hits' - falls du einen besseren kennst, skizziere ihn doch mal bitte kurz). eine std::list hat dieses problem übrigens nicht. mein vorschlag wäre remove_copy_if:

struct rabbitdie
{
       bool operator()( rabbit* elem) const
       {
            if( !elem->eat() )
            {
              delete elem;
              return true;
            }
            return false;
       }
};

void rabbit_manager::eat()
{
   vector<rabbit*> tmp;
   tmp.reserve( my_rabbits.size() );
   remove_copy_if( my_rabbits.begin(), my_rabbits.end(), back_inserter( tmp ), rabbitdie() );
   my_rabbits.swap( tmp );
}

[THX 1138]

langsam bitte
verwirrt mich mal nicht so..

hab probleme das remove_if zu implementieren:

//.h
using namespace std;

typedef vector<rabbit*> rabbits;
typedef rabbits::iterator r_iter;
//.cpp

void rabbit_manager::eat()
{
	my_rabbits.erase( remove_if( my_rabbits.begin(), my_rabbits.end(), rabbitdie()), my_rabbits.end());
}

[C++ Error] RabbitManager.cpp(88): E2268 Call to undefined function 'remove_if'
[C++ Error] RabbitManager.cpp(89): E2285 Could not find a match for 'rabbits::erase(undefined,r_iter)'

schätze mal es ist ein namespace problem, aber std::remove_if(..) oder ähnliches geht auch ned

eat() gibt übrigens schon ne bool zurück, brauch ich da das struct rabbitdie() überhaupt?

[Braunstein]

ist algorithm inkludiert?
Du brauchst rabbitdie schon, immerhin muß der Pointer ja auch gelöschtb werden.

[THX 1138]

<algorithm> ???

was is das? ( sorry echt anfänger )

bool rabbit::eat()
{
	if( my_parent->a_grass_manager->field[my_pos.x][my_pos.y] ) {
		my_parent->a_grass_manager->kill( my_pos );
		return true;
	}
	return false;
}

reicht das nicht, wenn ich das als ne memberfunktion hab?

[THX 1138]

#include <algorithm>

siehe da es funzt...
das muss mir mal einer erklären der die muse hat.
links reichen auch

danke jedenf"all"s

[CStoll]

camper schrieb:

CStoll schrieb:

remove_if() "löscht" alle Elemente des Vektors, für die das gegebene Prädikat false zurückgegeben hat (in dem Beispiel bedeutet false "der Hase ist verhungert") - das darumliegende erase() kürzt deinen Vektor dann entsprechend.

(und ja, es dürfte schneller sein, da es nur einmal über die komplette Liste läuft - die while()-Schleife muß bei jedem verhungerten Hasen alle Nachfolger nach vorne kopieren)

ich kann nicht erkennen, dass es mit remove_if schneller läuft. da remove_if die zugrunde liegende sequenz intakt und die elemente, die dem prädikat nicht entsprechen, in reihenfolge lässt, kann das ganze nur durch umkopieren von elementen in derselben grössenordnung erreicht werden (der algorithmus, den ich im sinn habe, hat O(n*m), n=elemente im container, m=anzahl der 'hits' - falls du einen besseren kennst, skizziere ihn doch mal bitte kurz).

remove_if() kopiert jedes Element maximal einmal um, die while-Schleife würde die Elemente maximal "#gelöschte" mal umkopieren (bei jedem erase() wird der Block hinter der aktuellen Position einen Schritt nach vorne geschoben).

Dieser Algorithmus hat eine Laufzeit von O(n):

It remove_if(It beg,It end,Pred pr)
{
  for(It dest=beg;beg!=end;++beg)
    if(!pr(*beg)) *dest++=*beg;
}

@1310: Um eine Funktion einsetzen zu können, muß der Compiler ihre Definition kennen - und die Definition der STL-Algorithmen steht im Header <algorithm>.

[camper]

CStoll schrieb:

camper schrieb:

CStoll schrieb:

remove_if() "löscht" alle Elemente des Vektors, für die das gegebene Prädikat false zurückgegeben hat (in dem Beispiel bedeutet false "der Hase ist verhungert") - das darumliegende erase() kürzt deinen Vektor dann entsprechend.

(und ja, es dürfte schneller sein, da es nur einmal über die komplette Liste läuft - die while()-Schleife muß bei jedem verhungerten Hasen alle Nachfolger nach vorne kopieren)

ich kann nicht erkennen, dass es mit remove_if schneller läuft. da remove_if die zugrunde liegende sequenz intakt und die elemente, die dem prädikat nicht entsprechen, in reihenfolge lässt, kann das ganze nur durch umkopieren von elementen in derselben grössenordnung erreicht werden (der algorithmus, den ich im sinn habe, hat O(n*m), n=elemente im container, m=anzahl der 'hits' - falls du einen besseren kennst, skizziere ihn doch mal bitte kurz).

remove_if() kopiert jedes Element maximal einmal um, die while-Schleife würde die Elemente maximal "#gelöschte" mal umkopieren (bei jedem erase() wird der Block hinter der aktuellen Position einen Schritt nach vorne geschoben).

Dieser Algorithmus hat eine Laufzeit von O(n):

It remove_if(It beg,It end,Pred pr)
{
  for(It dest=beg;beg!=end;++beg)
    if(!pr(*beg)) *dest++=*beg;
}

stimmt natürlich. keine ahnung wieso ich gedacht habe, die entfernten elemente würden hinter das ende der neuen sequenz kopiert werden.

[THX 1138]

äähm falls es jemand interessiert:

campers lösung mit remove_copy_if funktioniert,
die mit remove_if nicht.
warum kann ich nicht sagen, speed ist aber ok.

den letzten algorhytmus kapier ich nicht wirklich

It remove_if(It beg,It end,Pred pr)
{
  for(It dest=beg;beg!=end;++beg)
    if(!pr(*beg)) *dest++=*beg;
}

aber trotdzem besten dank

[camper]

1310-Logik schrieb:

äähm falls es jemand interessiert:

campers lösung mit remove_copy_if funktioniert,
die mit remove_if nicht.
warum kann ich nicht sagen, speed ist aber ok.

den letzten algorhytmus kapier ich nicht wirklich

It remove_if(It beg,It end,Pred pr)
{
  for(It dest=beg;beg!=end;++beg)
    if(!pr(*beg)) *dest++=*beg;
}

aber trotdzem besten dank

in der remove_if variante war ein kleiner fehler (zweimal myrabbits.begin), richtig ist:

void rabbit_manager::eat()
{
   my_rabbits.erase(remove_if(my_rabbits.begin(), my_rabbits.end(), rabbitdie()), my_rabbits.end());
}

das remove_if ist nur, um zu zeigen, wie es im prinzip funktioniniert. letzlich wird es etwa so aussehen:

template<typename I, typename O, typename Pred>
I remove_copy_if(I first, I last, O out, Pred p)
{
    for ( ; first != last ; ++first )
        if ( !p( *first ) )
            out++ = *first;
    return out;
}
template<typename I, typename Pred>
I remove_if(I first, I last, Pred p)
{
    I x = first = find_if( first, last, p );
    return x == last ? last : remove_copy_if( ++x, last, first, p );
}