C++ Invalider List-Iterator bei std::tr1::unordered_set

badday

Commander
Registriert
Sep. 2007
Beiträge
3.023
Moin zusammen,

ich habe folgendes Szenario:

Ich habe einen container, genauer gesagt
Code:
std::tr1::unordered_set<point_s, hash_func> con;

Wobei point_s und hash_func folgendermaßen definiert sind:

Code:
class  point_s
{
	public:
		point_s(int _x, int _y): x(_x), y(_y) {}
		unsigned short x, y;
		inline bool operator<(const point_s &b) const
		{
			return (x<b.x || (x==b.x && y<b.y));
		}

		inline bool operator==(const point_s &b) const
		{				
			return (x==b.x && y==b.y);
		}
};

struct hash_func
{
	std::tr1::hash<int> int_hash;
	std::size_t operator() (const point_s &s) const
	{
		return int_hash(s.x)+int_hash(s.y);
	}
};


Nun habe ich in einer anderen Funktion, in der ich das set als konstante Referenz übergebe folgendes:
Code:
if(con.find(point_s(x, y))!=con.end())

Diese Anweisung führt aber zu einem Problem, denn, so die Debug-Nachricht, die list-iterators seien nicht kompatibel.

Im Debugger sehe ich des weiteren, dass "_Vec" folgendermaßen aussieht:
_Vec [9]({x=40 y=30 },{x=40 y=30 },{x=??? y=??? },{x=??? y=??? },{x=30 y=20 },{x=30 y=20 },{x=30 y=20 },{x=52685 y=52685 },{x=52685 y=52685 }) std::vector<std::list<point_s,std::allocator<point_s> >::_Iterator<1>,std::allocator<std::list<point_s,std::allocator<point_s> >::_Iterator<1> > >

Ich mache nur insert bzw. erase-Aufrufe.


Hat jemand eine Idee, wo das Problem liegen könnte?



Vielen Dank & Gruß,

badday
 
Nah das ist mal ein knackiges Problem. Auch nach ernsthafter Suche kann ich in deinem Code keine Fehler erkennen. Zu der _Vec-Definition, was ist das? Ist das unordered_set etwa als ein Vector von Listen implementiert?

Interessant wäre vielleicht noch WIE du das Entfernen via erase() machst. Kannst du den Code mitposten? Manchmal kann man sich einen Container oder zumindest einen Iterator zerschießen, indem man erase() falsch anwendet .... obwohl Visual C++ 2010 da bei aktiviertem Iterator-Debugging eigentlich schon früher die Alarmglocken schlagen würde (oder verwendest du einen anderen Compiler?).
 
Puh...

Welche Plattform und welcher Compiler (+Version)? Und woher kommt TR1? Schon mitgeliefert?

Das set sieht definitiv kaputt aus, da es mehrfache Einträge enthält.

Ich hab gerade mal kurz gegrübelt... bist du ganz ganz ganz sicher, dass operator< eine Äquivalenzrelation darstellt?
operator== ist für die Funktion des Sets unnötig, Gleichheit wird über (!(a<b) && (!b<a)) sichergestellt. operator< solltest du als freie Funktion im selben Header und im selben Namespace anbieten.

Bist du sicher, dass das set nicht schon vorher zerschossen ist? Eingefügte Points vielleicht doch verändert? Dran gedacht, dass erase Iteratoren invalidieren kann?

Edit:
Ist eine Äquivalenz-Relation. Du könntest auch einfach ein typedef auf pair<int,int> machen.
Hast du das Ordnungsprädikat eigentlich mal angegeben? Sonst einfach less<point_s> mal übergeben.
 
Zuletzt bearbeitet:
Zu der _Vec-Definition, was ist das? Ist das unordered_set etwa als ein Vector von Listen implementiert?
Offenbar ist das bei MS so definiert.

Interessant wäre vielleicht noch WIE du das Entfernen via erase() machst. Kannst du den Code mitposten?
Das mache ich nur z. B. so:
Code:
con.erase(point_s(x, y));

obwohl Visual C++ 2010 da bei aktiviertem Iterator-Debugging eigentlich schon früher die Alarmglocken schlagen würde (oder verwendest du einen anderen Compiler?).
Ich werdende den Visual C++ 2008er-Compiler (SP 1).

Welche Plattform und welcher Compiler (+Version)?
Neben dem oben genannten unter Windows habe ich das ganze auch sowohl auf Fedora als auch unter Ubuntu (64-bit) getestet (gcc in der Version 4.4.3 bzw. 4.5.1 jeweils mit der option -std=c++0x). Dort tritt eine segmentation fault auf beim operator< von point_s, da der 2. Parameter nicht valide ist.

operator< solltest du als freie Funktion im selben Header und im selben Namespace anbieten.
OK, habe ihn folgendermaßen definiert:
Code:
bool operator< (const point_s &s1, const point_s &s2)
{
	return (s1.x<s2.x || (s1.x==s2.x && s1.y<s2.y));
}

Bist du sicher, dass das set nicht schon vorher zerschossen ist?
Eigentlich schon, aber offenbar ist der Fehler ja nicht so offensichtlich.
Eingefügte Points vielleicht doch verändert?
Nein, das kann ich ausschließen.
Dran gedacht, dass erase Iteratoren invalidieren kann?
Ja, das sollte ich auch ausschließen können.

Hast du das Ordnungsprädikat eigentlich mal angegeben? Sonst einfach less<point_s> mal übergeben.
Habe ich nun auch probiert. Hat aber keinen Unterschied gemacht.

Ist eine Äquivalenz-Relation. Du könntest auch einfach ein typedef auf pair<int,int> machen.
Ja, aber sollte das einen Unterschied machen?


Langsam bin ich wirklich ratlos... :confused_alt:


Dennoch schonmal danke für eure Antworten!


Gruß,

badday
 
Evtl hab ich ja gerad ein Brett vorm Kopf und ich hab das auch nur überflogen, aber ich hätte die Frage
bist du ganz ganz ganz sicher, dass operator< eine Äquivalenzrelation darstellt?
eindeutig mit Nein beantwortet.
http://de.wikipedia.org/wiki/Äquivalenzrelation

Wieso muss der Vergleichsoperator überhaupt eine sein? Macht eigtl. keinen Sinn finde ich.
Reflexivität ist doch niemals gegeben: (1, 1) < (1, 1) soll ja wahrscheinlich auch nicht true liefern, was es als Äquivalenzrelation tun müsste.

Äquivalenzrelation sind doch eine Art Verallgemeinerung von Gleichheit(=, <=>) und eben nicht Un-Gleichheit(<, >, <=, >=, ...)
 
Ja, du hast recht, kuddlmuddl, es wird natürlich equal_to verwendet.
 
es wird natürlich equal_to verwendet
wo denn? Ich versteh deine Antwort nicht^^

Ich geb nochmal nen Rateversuch ab - ich würde hier ein Problem vermuten zB wegen Überlauf oÄ:
Code:
struct hash_func
{
	std::tr1::hash<int> int_hash;
	std::size_t operator() (const point_s &s) const
	{
		return int_hash(s.x)+int_hash(s.y);
	}
};
(oder darf der hash ruhig mal kollidieren?)

Wäre nicht
Code:
return int_hash(s.x + s.y * $MAX_HOEHE);
eher, was du willst? So wird jeder Koordinate/jedem Punkt eine eindeutige Zahl zugeordnet. Da könnte man sich direkt Fragen, ob du die Hashberechnung nicht komplett abschaffst und direkt nur
Code:
return s.x + s.y * $MAX_HOEHE;
verwendest als hash_key. Besser als Eindeutig (injektiv) gehts nicht als hash_funktion, oder? Diesen Idealfall kann man natürlich nur haben, solange weniger Felder/Pixel/Punkte existieren als int an Zahlen bietet.

edit:
Die Idee auf int_hash zu verzichten als Minimalbeispiel: In Softwareentwicklung1 an der Uni HH müssen die Studis ein TicTacToe 3x3 Feld als 1D-Array abbilden und ne Berechnungsfunktion für den Array-Index schreiben. Da muss man halt auf y*3+x kommen.
 
Zuletzt bearbeitet:
wo denn? Ich versteh deine Antwort nicht^^
Als Vergleichsprädikat.

Zu deinem anderen Vorschlag:
Ich kann das natürlich auch einfach auf 1D mappen, etwa so:
Code:
return MAX_X*s.y+s.x;

Allerdings besteht das Problem weiterhin.

EDIT: sehe gerade, ist ja etwa der selbe Code, den du gepostet hast ;)
 
Zuletzt bearbeitet:
Das ist auch nicht Unfallfrei..

zB Feld 3x5 dh MAX_X = 2

(2, 1)
2 * 1 + 2 = 5

(1, 2)
2 * 2 + 1 = 5

MAX muss sich auf die Var beziehen, mit der du Multiplizierst:

Also entweder
return MAX_X*s.x+s.y;

oder
return MAX_Y*s.y+s.x;
 
Zuletzt bearbeitet:
Hallo,

ich würde folgende Sachen mal ausprobieren:

(1) Schauen, ob es mit std::set<point_s> funktioniert.
(2) Falls nicht bereits in Verwendung boost::unordered_set<> ausprobieren.

Ich konnte das Problem bislang nicht nachvollziehen. Hier eine Demo-Source für boost:
Code:
#include <iostream>

#include <boost/unordered_set.hpp>

using namespace std;

struct  point_s
{
	unsigned short x_, y_;

	point_s(int x, int y): x_(x), y_(y) {}

	bool operator==(point_s const& other) const
	{
		return x_ == other.x_ && y_ == other.y_;
	}

	friend std::size_t hash_value(point_s const& s)
	{
		std::size_t seed = 0;
		boost::hash_combine(seed, s.x_);
		boost::hash_combine(seed, s.y_);

		return seed;
	}		
};

typedef boost::unordered_set<point_s> uset_t;
int main() {
	uset_t con;
	for(int x=0; x < 10; ++x) {
		for(int y=0; y < 10; ++y) {
			con.insert(point_s(x,y));
		}
	}
	con.erase(point_s(9, 4));
	if(con.find(point_s(4,6)) != con.end())
		cout << "enthalten\n";


}
 
Vielen Dank für die Mühe, convexus.

Ich werde zunächst mal alles weiträumig entrümpeln, sollte es dann immer noch nicht gehen, werde ich mich nach Alternativen umsehen.

Danke an alle soweit, ihr habt mir schonmal sehr geholfen.



Gruß,

badday
 
OT:
eindeutig mit Nein beantwortet.
http://de.wikipedia.org/wiki/Äquivalenzrelation

Wieso muss der Vergleichsoperator überhaupt eine sein? Macht eigtl. keinen Sinn finde ich.
Damit ist gemeint, ob man aus dem Vergleichsoperator die erwähnte Äquivalenz-Prüfung (!(a<b)&&!(b<a)) bauen kann oder nicht, da das die intern verwendete Gleichheitsfunktions oder eben korrekter Äquivalenzfunktion von sets ist. Ist ein beliebter und selten offensichtlicher Fehler, ob das wirklich geht oder nicht und zerschießt einem gerne die sets, wenn es nicht geht nicht.
Im Falle von baddays Operator geht es, wie 7H3 N4C3R auch in seinem Edit schrieb.

Zum selber lesen: Effective STL - Item 19: Understand the difference between equality and equivalence.

EDIT: Nur um nochmal darauf hin zu weisen, dass ist für unordert_set offtopic, weil wie badday schon erwähnte die eben equal_to benutzt.
 
Zuletzt bearbeitet:
Mh aber wäre das hier nicht ein Beispiel für ne Kollision?
Feld mit Größe 5x6 dh MAX_X := 4, MAX_Y := 5
hash(x, y) := MAX_X * y + x

dann hat für (0, 2) und (4, 1) hash den selben Wert:
4 * 2 + 0 = 8
und
4 * 1 + 4 = 8
 
kuddlmuddl schrieb:
Evtl hab ich ja gerad ein Brett vorm Kopf und ich hab das auch nur überflogen, aber ich hätte die Frage

eindeutig mit Nein beantwortet.
http://de.wikipedia.org/wiki/Äquivalenzrelation

Wieso muss der Vergleichsoperator überhaupt eine sein? Macht eigtl. keinen Sinn finde ich.
Reflexivität ist doch niemals gegeben: (1, 1) < (1, 1) soll ja wahrscheinlich auch nicht true liefern, was es als Äquivalenzrelation tun müsste.

Äquivalenzrelation sind doch eine Art Verallgemeinerung von Gleichheit(=, <=>) und eben nicht Un-Gleichheit(<, >, <=, >=, ...)

Hi,

folgendes sagt der Standard:

ISO 14882:2003 - 23.1.2 (lib.associative.reqmts) (Punkt 3) schrieb:
The phrase ‘‘equivalence of keys’’ means the equivalence relation imposed by the comparison and not the operator== on keys. That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false.

Das kann nur wahr sein, wenn man das Comparison-Objekt über operator< (bzw. auch operator>) implementiert.

Ob durch die Hash-Funktion zwei verschiedene Keys im selben Bucket landen ist in sofern egal, als dass das Bucket dann linear durchsucht wird, was wieder auf die Performance geht. Für die Funktionsweise des Containers ist es kein Problem - solange die Hashfunktion äquivalente Keys (im Sinne obiger Definitiv) auch immer ins selbe Bucket packt.

Mal unter Linux kompiliert und Valgrind drauf geworfen? Scheint mir so, als wenn das nicht das Problem ist.
 
Zurück
Oben