List sortiere/element löschen...nix klappt

Dagi

Hi,
hab nun schon ewig bei google gesucht und finde einfach keine lösung(die sinnvoll ist).

es geht eg um folgendes.
ich versuche mir grad ein kleines pathfinding-tool zu schreiben und wollte die ganze sache mit STL::list machen.
nun funktioniert das soweit auch ganz okay.
hatte nun aber tagelang einen fehler, bei dem eine fehlermeldung kommt und das programm einfach geschlossen wird.
irgendwann kam ich darauf, das der fehler in diesem code-segment ist:

closedList.push_back(nTempNode);
	for(iList=openList.begin(); iList!=openList.end(); iList++)
	{
		if(iList->ID==nTempNode.ID)
			iList=openList.erase(iList);
	}

in diesem teil, bzw vorher, suche ich den kleinsten "F-Wert" aus der "offenen" Liste, werfe ihn in die "geschlossene" Liste und lösche ihn aus der "offenen".
nun ist es so, das ich irgendwann an den punkt komme, wo das Letzte element der liste das zu löschende ist.
deshalb kam der fehler.
okay, hab dann im internet geschaut, wie man nun das letzte element einer liste löschen kann, fand da leider absolut keine info(oder ich habs falsch verstanden und somit überlesen!?).
also kam mir die idee, meine liste zu sortieren.
okay, google an und los. doch leider fand ich auch da keinen punkt, wie ich dies anstalle, beispiele die ich fand waren alle ausgelegt, auf listen vom tyP

list<int> Listenname;

nun hab ichs leider nicht so einfach, da meine liste vom typ "node" ist

struct Node
{
    Node() : x(0), y(0), ID(0), iIndex(0), iSourcePoint(0), F(0), G(0), H(0) {}
    Node(int iX, int iY, int iID, int index, int source, int iF, int iG, int iH) : 
    x(iX), y(iY), ID(iID), iIndex(index), iSourcePoint(source), F(iF), G(iG), H(iH) {}
    int x;
    int y;
    int ID;
    int iIndex;
    int iSourcePoint;
    int F, G, H;
};

nun konnte ich das problem zwar erstmal temporär beheben...aber fragt nicht wie XD

aber fakt is, das ich ne sinvolle lösung finden möchte aber keine ahnung hab wie ich das momentan anstelle.

hat von euch vielleicht jemand ein tip?
oder kann mir vllt kurz erklären, wie ich meine liste in dem fall sortiere?
meiner meinung nach würde das ja zum einen das problem lösen und andererseits mein programm erheblich beschleunigen.

krümelkacker

Dagi schrieb:

closedList.push_back(nTempNode);
for(iList=openList.begin(); iList!=openList.end(); iList++)
{
    if(iList->ID==nTempNode.ID)
        iList=openList.erase(iList);
}

Der Iterator iList wird nach dem erase ungültig.
Guck mal in Deiner STL-Doku nach, was erase zurückgibt.
Oder verwende gleich list<>::remove_if.
Wenn Du die Schleife immer noch selbst schreiben willst, denke daran, dass das iList++ -- was übrigens ein ++iList sein sollte -- eventuell nicht mehr im Rumpf der for-Schleife auftauchen sollte.

BTW: Wenn Du GCC/g++/libstdc++ verwendest, kannst Du den "STL-Debug-Modus" aktivieren. Der hätte Dir dann auch gesagt, dass der Iterator nicht mehr gültig ist. Schau einfach mal in der Doku Deines Compilers nach, ob es einen solchen Debug-Modus gibt und wie man den dann aktivieren kann.

Mit aktiviertem "STL-Debug"-Modus bekomme ich im Debugger folgendes zu sehen:

(gdb) run
Starting program: /tmp/a.out 
/usr/include/c++/4.4/debug/safe_iterator.h:204:error: [b]attempt to increment 
    a singular iterator[/b].

Objects involved in the operation:
iterator "this" @ 0x0xbffff35c {
type = N11__gnu_debug14_Safe_iteratorINSt6__norm14_List_iteratorIiEENSt7__debug4listIiSaIiEEEEE (mutable iterator);
  state = singular;
  references sequence with type `NSt7__debug4listIiSaIiEEE' @ 0x0xbffff35c
}

Program received signal SIGABRT, Aborted.
0x0012d422 in __kernel_vsyscall ()
(gdb) backtrace
#0  0x0012d422 in __kernel_vsyscall ()
#1  0x00280651 in *__GI_raise (sig=6)
    at ../nptl/sysdeps/unix/sysv/linux/raise.c:64
#2  0x00283a82 in *__GI_abort () at abort.c:92
#3  0x0017d71a in __gnu_debug::_Error_formatter::_M_error (this=0xbffff194)
    at ../../.././libstdc++-v3/src/debug.cc:539
#4  0x08049ecb in __gnu_debug::_Safe_iterator<std::__norm::_List_iterator<int>, std::__debug::list<int, std::allocator<int> > >::operator++() ()
#5  0x0804922d in main ()
(gdb)

Gut, der backtrace ist wenig spektakulär, da ich den fehlerhaften Loop direkt in der main-Funktion hatte. Aber so kann ich zumindest auch bei größeren Programmen nachvollziehen, wer wen aufgerufen hat, was dann zum Fehler führte.

Dagi

danke für deine schnelle antwort
ich weiß nur nicht, ob ich sie recht verstanden habe ^^

also, den fehler hab ich gefunden, als ich aus dem programm gekickt wurde und sah, das durch das löschen des elementes der inhalt von

iList

leer war bzw datenmüll beinhaltete und es somit zu dem prob kam.
mir war es nur ein rätsel wieso es so weit kam, bis ich dann heute morgen sah, das es daran liegt, das ich das letzte element lösche und somit iList auf ein.. 'nix' zeigt

deshalb kam die idee auf, die liste zu sortieren, somit kann ich zumindest ausschließen, das mein "kleinster f-wert" das letzte element der liste ist

achso, wieso muss es in der schleife eigentlich

++iList

sein?
dachte das hat nur was mit prioritäten zu tun.

krümelkacker

Dagi schrieb:

ich weiß nur nicht, ob ich sie recht verstanden habe ^^

Das weiß ich auch nicht.

Dagi schrieb:

das es daran liegt, das ich das letzte element lösche und somit iList auf ein.. 'nix' zeigt

Nein. Es liegt daran, dass nach einem erase, der Iterator ungültig wird und Du kein ++ mehr drauf aufrufen oder sonst was mit ihm anstellen darfst (außer einer Neuzuweisung).
RTFM: list<>::erase, list<>::remove_if

achso, wieso muss es in der schleife eigentlich ++iList; sein?

++iList; verändert nur den Iterator
iList++; verändert den Iterator und liefert eine Kopie des alten Iterators zurück, welche Du hier gar nicht benötigst.

Dagi

okay, hab mir das jetzt mal angeschaut bzw etwas über remove_if gelesen aber irgendwie komem ich damit noch immer nicht hin.

kann mir vllt jemand nochmal nen tip geben?.

wenn ich das richtig sehe muss ich ja in das "remove_if(..)" den true/fals vergleich reinbringen.
gelöscht werden soll das element(aus der liste) welches = nTempNode ist.

also doch eg

list<Node> openList;
...
Node nTempNode;
...
openList.remove_if( das element = nTempNode );

hab das zwar gesehen wie man es macht, wenn es sich um z.b. eine list<int> handelt, zumindest in etwa, aber sehe keine idee, wie ich das nun übertragen kann. ich hab ja entweder direkt "nTempNode" bzw, wenn es so nicht geht, die "nTempNode.ID", womit ich ja eg ne feste zuweisung hab.

krümelkacker

Dagi schrieb:

kann mir vllt jemand nochmal nen tip geben?.

Schlaue Bücher besorgen. Das ist mein Ernst. Das ist das Gegenteil von Zeitverschwendung.

Dagi schrieb:

list<Node> openList;
...
Node nTempNode;
...
openList.remove_if( das element = nTempNode );

Wenn Du hier die Gleichheit im Sinne des == Operators meinst, kannst Du

openList.remove(nTempNode);

benutzen. Ich dachte, Du wolltest irgend eine ID vergleichen. Das geht natürlich auch, siehe function object. Beispiele findest Du überall. Kennst Du diese Seite schon? Da gibt's auch ein Beispiel dazu.

Bitte das nächste mal ein bissel mehr anstrengen. Danke.

kk

Dagi

ja, die seiten kenne ich bereits
mein problem ist wohl eher, das ich nicht weiß wie ich die beispiele auf meinen code üertrage.
wenn ich es mit remove ausführe, kommt es zu einigen fehlerausgaben.

1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)": template-Argument für "const std::basic_string<_Elem,_Traits,_Alloc> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\string(90): Siehe Deklaration von 'std::operator =='
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(927): Bei der Kompilierung der  Klassen-template der void std::list<_Ty>::remove(const _Ty &)-Memberfunktion
1>        with
1>        [
1>            _Ty=Node
1>        ]
1>        c:\users\eroda\documents\visual studio 2008\projects\pathcalculator\pathcalculator\pathfinder.cpp(15): Siehe Verweis auf die Instanziierung der gerade kompilierten Klassen-template "std::list<_Ty>".
1>        with
1>        [
1>            _Ty=Node
1>        ]
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)": template-Argument für "const _Elem *" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\string(80): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)": template-Argument für "const std::basic_string<_Elem,_Traits,_Alloc> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\string(70): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::istreambuf_iterator<_Elem,_Traits> &,const std::istreambuf_iterator<_Elem,_Traits> &)": template-Argument für "const std::istreambuf_iterator<_Elem,_Traits> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\streambuf(548): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)": template-Argument für "const std::list<_Ty,_Ax> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(1293): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::istream_iterator<_Ty,_Elem,_Traits,_Diff> &,const std::istream_iterator<_Ty,_Elem,_Traits,_Diff> &)": template-Argument für "const std::istream_iterator<_Ty,_Elem,_Traits,_Diff> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\iterator(266): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::allocator<_Ty> &,const std::allocator<_Other> &) throw()": template-Argument für "const std::allocator<_Ty> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\xmemory(173): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)": template-Argument für "const std::reverse_iterator<_RanIt> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\xutility(2220): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)": template-Argument für "const std::_Revranit<_RanIt,_Base> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\xutility(2024): Siehe Deklaration von 'std::operator =='
1>c:\program files (x86)\microsoft visual studio 9.0\vc\include\list(937) : error C2784: "bool std::operator ==(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)": template-Argument für "const std::pair<_Ty1,_Ty2> &" konnte nicht von "Node" hergeleitet werden.
1>        c:\program files (x86)\microsoft visual studio 9.0\vc\include\utility(68): Siehe Deklaration von 'std::operator =='

hier nun mal die gesamte funktion, vllt hilft das ja etwas

Node PathNodes::GetMinF(void)
{
	Node nTempNode;
//	list<Node>::iterator it = openList.begin();
	int iMinF=100;//it->F;
	for(iList=openList.begin(); iList!=openList.end(); ++iList)
	{
		if((iList->F < iMinF) && (iList->F > 0))
		{
			iMinF=iList->F;
			nTempNode.F=iList->F;
			nTempNode.G=iList->G;
			nTempNode.H=iList->H;
			nTempNode.ID=iList->ID;
			nTempNode.iIndex=iList->iIndex;
			nTempNode.iSourcePoint=iList->iSourcePoint;
			nTempNode.x=iList->x;
			nTempNode.y=iList->y;
		}
	}
	// eintrag mit kleinstem "F"-Wert in die geschlossene list verschieben
	closedList.push_back(nTempNode);
	openList.remove(nTempNode);
	return nTempNode;
}

hab danach mal weiter mit remove_if gesucht und versucht. das klappt zwar, aber ich find diese lösung doch etwas unschön/zumindest wie ichs gemacht habe):

int tmpID;

bool currNode (Node temp) 
{
	return temp.ID==tmpID; 
}

Node PathNodes::GetMinF(void)
{
	Node nTempNode, f;
	list<Node>::iterator it = openList.begin();
	int iMinF=100;//it->F;
	for(iList=openList.begin(); iList!=openList.end(); ++iList)
	{
		if((iList->F < iMinF) && (iList->F > 0))
		{
			iMinF=iList->F;
			nTempNode.F=iList->F;
			nTempNode.G=iList->G;
			nTempNode.H=iList->H;
			nTempNode.ID=iList->ID;
			nTempNode.iIndex=iList->iIndex;
			nTempNode.iSourcePoint=iList->iSourcePoint;
			nTempNode.x=iList->x;
			nTempNode.y=iList->y;
		}
	}
	tmpID=nTempNode.ID;
	// eintrag mit kleinstem "F"-Wert in die geschlossene list verschieben
	closedList.push_back(nTempNode);
	openList.remove_if(currNode());
	return nTempNode;
}

l'abra d'or

Du musst dir mal den Code genauer anschauen. Da sind zwei Beispiele für einen Parameter für remove_if.

freie Funktion. Du übergibst einen Funktionszeiger an remove_if. Das ist in dem Beispiel "single_digit"
Funktor - Funktions-Objekt. Das ist eine Klasse mit überladenem operator()(). Hierfür muss ein Objekt (Instanz einer Klasse) an remove_if übergeben werden. In dem Beispiel ist das "is_odd".

Du verwendest jetzt eine freie Funktion + ein globales Objekt. Globale Objekte sind (fast immer) böse - so auch hier. Du kannst doch bequem einen Funktor verwenden.

class cmp_node_by_id {
  int id_;
public:
  cmp_node_by_id(int id) 
   : id_(id)
  {}
  bool operator()(const Node& node) {
    return node.ID == id_;
  }
};

// Verwendung:
listToRemove.remove_if( cmp_node_by_id(25) );

Wenn die id IMMER das einzige Unterscheidungskriterium deiner Node ist, kannst du aber auch gleich einen passenden operator==() für deine Node-Klasse anbieten und statt remove_if + Funktor/Funktion std::list::remove() verwenden.