STL Vector: Element entfernen

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)

Braunstein

Ich hab mal einen Blick in die algorithm geworfen und da nahezu identische Codes vorgefunden (bis auf ein paar andere Variablennamen und if statt ?)

THX 1138

sorry fürs nervig fragen stellen..

werd dann Deine variante mit dem korrigierten fehler gleich mal probieren wenn ich zuhase bin.
ich sass da gestern ewig (und hab mir <vector> und <algorithm> angeguckt mitem debugger, schritt für schritt. )
der vector war nach einem durchgang immer leer und hat seltsame zeiger ins nirvana geliefert. nun is klar wieso

dankedanke erstmal

THX 1138

ja natürlich geht es mit remove_if, etwas cpu zeit spart es wohl auch (grobe vermutung nach taskmanager).

da hör ich doch meinen alten lehrer: "abschreiben bringt nichts"
und copy paste schon gar nichts

na gut danke nochmal euch allen.
werd mich nun aufs nächste problem stürzen...

bye