STL Vector: Element entfernen

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

THX 1138

..mh noch zu früh am morgen.
muss ich mal in ruhe studieren.

danke

THX 1138

camper schrieb:

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

dumme fragen: (falls es sowas gibt )
warum machts Du ein template? oder ist das nur allgemein formuliert so wie in der referenz?
wenn ich remove_if implementiere wird trotzdem remove_copy_if aufgerufen? wo ist denn dann der vorteil?

CStoll

remove_if() und Konsorten sollst du nicht implementieren - binde dir einfach den Header <algorithm> ein und gut ist. Sieh diese Code-Beispiele einfach als Variante an, wie die STL-Algorithmen umgesetzt werden könnten (wie es wirklich aussieht, kann dir ein Blick in die <algorithm> beantworten).

(und die sind als Templates definiert, damit du sie problemlos auf jede Art von Iteratoren loslassen kannst)