C++ Verkettete Listen

[Hanfba3R]

Hallo,

Ich habe irgendwie Probleme mit den verketteten Listen, wollte mal fragen ob/wie ich folgendes realisieren kann:

Also ich habe eine Klasse, dessen Instanzen am Anfang in eine Liste geschoben werden.
Diese Klasse hat unteranderem ein bool(dies ist standardmässig true). Durch (verschiedene Funktionen) wird dies auf false gesetzt.

Kann ich mit einer verketteten Liste die Instanzen bei denen dieser Wert false ist, löschen?
Oder gibt es eine andere Lösung für das was ich machen will?

Danke für jegliche Hilfe

 

[Spartaner117]

Je nach dem um wieviele Items es sich handelt, ist eine STL-Liste mehr oder weniger dafür geeignet. Du merkst es aber dann, wenn die Performance zu stark in den Keller geht.

 

[Hanfba3R]

äähm 30.000 ungefähr. Gibt es dann eine andere Lösung, womit ich die Instanzen löschen kann, bei denen dies auf False ist?

 

[Darii]

Wo ist jetzt dein Problem? Geh die Liste durch und lösch die Elemente bei denen die entsprechende Eigenschaft false ist.

 

[Hanfba3R]

Ja, aber was passiert wenn ich jetzt z.B. Element 3000 lösche, später durch eine weitere Funktion alle Instanzen durch gehe um zu gucken ob der Wert auf false gesetzt werden muss. Aber das Element 3000 gibt's ja garnicht mehr, macht das nichts?

 

[Spartaner117]

Das kommt darauf an was du für eine Liste benutzt.

Eine verkette Liste sollte ja genau diesen Vorteil besitzen, dass einzelne Elemente eingefügt oder gelöscht werden können.

Schau dir mal den Link in meinem vorigen Post an. Zur Not bemüh mal Google. Die Liste sollte alle deine Ansprüche erfüllen.

 

[Hanfba3R]

Also sollte ich eine verkettete Liste benutzen?
Beispiel:

class Beispiel
{
bool aehnlich;
class ()
{
bool = true;
}
void Funktion ()
{
//macht irgendwie das es entweder false oder true ist
}
}

main ()
{
Beispiel *pBeispiel;
pBeispiel = new Beispiel[30];

list <Beispiel> Liste;
list <Beispiel>::iterator i;


for(int i = 0;i < 30;i++)
{
pBeispiel.Funktion();
Liste.push_back(pBeispiel);
}

for(i = i.begin();i != i.end(); ++i)
{
if(*i->aehnlich == false)
{
Liste.erase(i);
}
}
return 0;
}

Wie kann ich mit dem iterator auf das aehnlich zugreifen? So ist das doch bestimmt falsch, odeR?

 

[Spartaner117]

class CBeispiel
{
private:
bool Value;
}

list<CBeispiel> Liste;
list<CBeispiel>::iterator iter;

CBeispiel tempclass;
Liste.push_back(tempclass);

for(iter = Liste.begin(); iter != Liste.end(); iter++)
{
if(iter->Value == false)
Liste.erase(iter);

}

Wenn was unklar ist, einfach laut schreien.

 

[Darii]

Das ist so nicht sicher, mach es lieber so: http://www.velocityreviews.com/forums/t283368-erase-elements-while-iterating-on-a-map.html

 

[Spartaner117]

Stimmt, nicht bedacht. Notlösung wäre, den Iterator nach der Bedinung wieder auf Liste.begin() zu setzen, was aber bei 30.000 Items wohl ziemlich an der Performance zieht.

 

[Raechaer]

Alternativ kannst du auch einfach list::remove_if verwenden.

 

[PW-toXic]

ich programmier zwar weder c noch hab ich mir das ganze genau durchdacht, aber was spricht dagegen seblst eine verkettete Liste mit genau dieser eigenschaft zu programmieren?

sprich entweder du machst in deiner klasse selbst eine next und previous referenz rein, oder du baust dir dafür eine container klasse.
wenn dann eine bestimmte variable auf false gesetzt wird, dann setzt du next auf das übernächste
this.previous.next = this.next; (auf null prüfen usw nicht vergessen..)

unset(this) (oder wie auch immer die syntax ist)


nur ne idee

 

[7H3 N4C3R]

Wenn was unklar ist, einfach laut schreien. :schaf:[/QUOTE]
*SCHREI* :)

Ganz fieser Bug in deinem Code: list.erase( iter) invalidiert den Iterator. Eine gute STL-Implementation löst hier eine Assertion aus, wenn der invalidierte Iterator nochmal inkrementiert wird. Aus diesem Grund gibt erase den nächsten gültigten Iterator zurück:
iter = list.erase( iter);
In diesem Fall darf dann aber die for-Schleife den Iterator nicht mehr inkrementieren. Deshalb löst man sowas i.d.R. über ein while oder über list.remove bzw list.remove_if, damit man sich über solche Probleme keinerlei Gedanken machen muss.

 

[Spartaner117]

Vielen Dank, wieder was dazugelernt.

 

[Hanfba3R]

Ok, hat geklappt! Danke euch