STL std::set find() mit Objektinstanzen

Halli hallo. Vielleicht besser in diesem Forum:

Ich habe ein schönes set, da kommen lauter kleine Instanzen von Vektoren eines Zustandsraums rein, also z.B. 10 integer Werte:

std::set<vector10d> attributeSet;

Die Vector-Klasse selbst ist sehr einfach, sie hat halt ein Array mit 10 Elementen UND vor allem natürlich einen spitzenmäßigen == Operator.

class vector10d {
...
int element[10];

inline const bool operator==( const vector10d &comp )
{
   return element[0] == comp.element[0] &&
   element[1] == comp.element[1] &&
   ... &&
   element[9] == comp.element[9];
};

Jaha. Und jetzt will ich, nachdem ich einen Haufen Vektoren in mein attributeSet reingetan habe später nach einem solchen suchen. Natürlich weiß ich, dass die Suche erfolgreich sein muss. Ist sie leider nicht, daher mein Posting. Einfach gesagt: find(...) funktioniert nicht. Es behauptet unnachgiebig, dass es mein gesuchtes Element nicht gibt.

vector10d att(1,2,3, ...);

if ((attributeSet.find(att) != attributeSet.end())
{
   //GEFUNDEN! JUHUUU!! <- nix is... :(
}

Dann hab ich was über find_if(...) gelesen und versucht es einzubauen, aber dollerweise gibts das nicht für ein std::set.

Was tun?

Nexus

zorro59 schrieb:

Was tun?

Code wiederverwenden. Zwei Sequenzen auf Gleichheit überprüfen kannst du mit dem STL-Algorithmus std::equal() . Wenn dein Compiler den TR1 (Technical Report 1) unterstützt, kannst du sogar std::tr1::array und dessen Gleichheitsoperator verwenden. Mit Boost wäre die Alternative boost::array .

Für dein std::set benötigst du allerdings einen operator< oder ein benutzerdefiniertes Sortierprädikat, das du uns unterschlagen hast. Die Memberfunktion std::set::find() findet anhand von Äquivalenz, nicht Gleichheit. D.h., zwei Elemente a und b sind äquivalent im Bezug auf das Sortierkriterium, falls gilt:

!(a < b) && !(b < a)

Im Weiteren solltest du operator== als freie Funktion ausserhalb der Klasse implementieren. Das const im Rückgabetyp const bool hat überhaupt keinen Effekt und sollte deshalb weggelassen werden.

krümelkacker

Zeige ein kurzes, kompilierbares Beispiel, was das Problem verdeutlicht. Wenn's nicht kompiliert bitte auch die Fehlermeldung. Danke.

Erstmal danke für die Antworten!

Puuh, dass alles als kompaktes Problem zu posten wird ein Gefrickel. Da muss ich die Klasse ja ganzschön beschneiden, ich hab da ja auch die ganzen "+", "-", ... Operatoren mit drinne...

Die operator< und operator> hab ich jetzt eingebaut, hilft aber nüscht. Die vergleichen jetzt komponentenweise, also erst ob die erste Komponenten kleiner/größer ist, wenn die gleich sind dann die zweite, etc., wie bei Zahlen. So kann definitiv sortiert werden.

Kompilieren tut er. Hätte der, bevor ich die < > definiert habe da nicht sagen müssen, dass er für das find() garnicht weiß, wie er die vergleichen soll? Er hat wahrscheinlich einfach die Pointer miteinander verglichen. Meine < > Operatoren verwendet er wohl nicht für den Äquivalenztest...

krümelkacker

zorro59 schrieb:

Kompilieren tut er. Hätte der, bevor ich die < > definiert habe da nicht sagen müssen, dass er für das find() garnicht weiß, wie er die vergleichen soll?

Eigentlich schon...

zorro59 schrieb:

Er hat wahrscheinlich einfach die Pointer miteinander verglichen. Meine < > Operatoren verwendet er wohl nicht für den Äquivalenztest...

...welche Pointer?

kleines, kompilierbares Beispiel zeigen!

zorro59 schrieb:

Kompilieren tut er. Hätte der, bevor ich die < > definiert habe da nicht sagen müssen, dass er für das find() garnicht weiß, wie er die vergleichen soll? Er hat wahrscheinlich einfach die Pointer miteinander verglichen. Meine < > Operatoren verwendet er wohl nicht für den Äquivalenztest...

Wenn du Pointer in das set packst, dann solltest du, wenn du willst, dass der Inhalt verglichen willst, als zweiten Template Parameter einen Funktor less übergeben, der die Pointer dereferenziert und dann vergleicht.

Ungetestet:

struct ptr_less {
   bool operator() (blah* p1, blah* p2) 
   {
      return *p1 < *p2;
   }
};

std::set<blah*, ptr_less> mein_set;

Progchild, du bist ein Held.

Vielen Dank, so funktioniert es! Lustigerweise sieht meine ptr_less so aus:

struct ptr_less {
	bool operator() (vector10d p1, vector10d p2)
	{
		return p1 < p2;
	}
};

Die Instanzen von vector10d, die ich in das set reinlege, erstelle ich nicht mit new sondern so:

vector10d myAttribute(5,4,4,2,7,9,0,7,8,1);

Entsprechend hab ich natürlich einen Konstruktor:

inline vector10d(int e1, int e2, ...)
{
  element[0] = e1;
  element[1] = e2;
  ...
}

Also sind dann irgendwie wiederum keine Pointer. find() geht aber erst nach deinem glorreichen Tip.

Wenn mir das jetzt nochmal einer erklären kann?

Eisflamme

Btw. hat das const im Rueckgabetyp doch einen Effekt, weil es folgende, unlogische Statements verhindert:

vector10d a(...);
vector10d b(...);
a == b = true;

Stand doch auch in "Effektiv C++ programmieren" als guter Stil, oder?

Waere es hier zudem nicht performanter einen gehashten Container zu nehmen? Bei jedem Vergleich 10 ints zu vergleichen erscheint mir nicht optimal.

hustbaer

Eisflamme schrieb:

Btw. hat das const im Rueckgabetyp doch einen Effekt, weil es folgende, unlogische Statements verhindert:
vector10d a(...);
vector10d b(...);
a == b = true;

Dieses unlogische Statement braucht man nicht zu verhindern, so lange der Rückgabetyp von operator == ein bool ist (oder sonst ein eingebauter Typ). Was ich mal aus äusserst üblich bezeichnen würde.

Die Zuweisund wäre nur bei einem UDT als Rückgabetyp möglich, da Aufrufe von Memberfunktionen (inklusive solche die als Operatoren "getarnt" sind) auf r-values erlaubt sind.

Bei eingebauten Typen sind Zuweisungen mit r-values als Ziel allerdings nicht erlaubt.

Probier's aus

struct foo {};

// hier brauchen wir kein const!
bool operator == (foo lhs, foo rhs)
{
	return true;
}

// ---------------------------------------------------

struct bar {};
struct baz
{
	baz& operator = (baz const&) { return *this; }
	baz& operator = (bool) { return *this; }
};

// hier macht es nen unterschied
baz /*const*/ operator == (bar lhs, bar rhs)
{
	return baz();
}

// ---------------------------------------------------

int main() 
{ 
// 	foo a;
// 	foo b;
// 	a == b = true;	// geht sowieso nicht

	bar c;
	bar d;
	c == d = baz(); // geht ohne das const oben
	c == d = true;  // -- "" --

	return 0;
}

// aber wer macht schon sowas...

Ich bin überhaupt der Meinung dass das Thema "= statt == verhindern" bei manchen etwas ausartet. Ich finde kaum etwas grässlicher als die - für mich vollkommen verqueren - Vergleiche ala if (0 == blah()) . *schüttel*

Eisflamme

Gut, wieder was gelernt.

bei (0 == blah()) stimme ich dir absolut zu.

krümelkacker

zorro59 schrieb:

Progchild, du bist ein Held.
Vielen Dank, so funktioniert es! Lustigerweise sieht meine ptr_less so aus:
struct ptr_less {
	bool operator() (vector10d p1, vector10d p2)
	{
		return p1 < p2;
	}
};
Die Instanzen von vector10d, die ich in das set reinlege, erstelle ich nicht mit new sondern so:
vector10d myAttribute(5,4,4,2,7,9,0,7,8,1);
Entsprechend hab ich natürlich einen Konstruktor:
inline vector10d(int e1, int e2, ...)
{
  element[0] = e1;
  element[1] = e2;
  ...
}

Das ergibt alles keinen Sinn! Wenn Du für vector10d, welches anscheinend ein Klassentyp ist, schon operator< definiert hast, brauchst Du keine eigene "Comparator"-Klasse! ProgChild ist davon ausgegangen, dass Du std::set<vector10d*> benutzt. Wir raten hier alle nur rum, weil Du keinen relevanten Code zeigst! Vielleicht hast Du deinen operator< auch im falschen Namensraum definiert, so dass std::set den nicht automatisch finden kann. Man weiß es nicht. Wir können nicht Gedankenlesen!

zorro59 schrieb:

Also sind dann irgendwie wiederum keine Pointer.

Da Du anscheinend nicht weißt, was Du tust, ist ein kurzes kompilierbares Codebeispiel umso wichtiger!

kk

Ihr habt Probleme. Ich habs mir einfach so gemerkt: man soll immer

const

benutzen, es sei denn das Resultat soll später noch verändert werden.

Aber nochmal danke für die Hilfe! Zu meiner letzten Frage. Objektinstanzen sind doch an sich schon immer eine Art Pointer, oder?

myObject.x1
myArray[1]

ist doch ähnlich. In beiden Fällen wird erstmal der Speichebereich des Objekts bzw. des Arrays (myObject, myArray) referenziert. Die Position der Elemente wird danach festgestellt (beim Array zählt er halt einen sizeof(...) Schritt hoch, beim Objekt sonst wie).

Oder verwechsel ich das mit irgendeinem Unsinn?

krümelkacker

zorro59 schrieb:

Zu meiner letzten Frage. Objektinstanzen sind doch an sich schon immer eine Art Pointer, oder?
myObject.x1
myArray[1]
ist doch ähnlich. In beiden Fällen wird erstmal der Speichebereich des Objekts bzw. des Arrays (myObject, myArray) referenziert. Die Position der Elemente wird danach festgestellt (beim Array zählt er halt einen sizeof(...) Schritt hoch, beim Objekt sonst wie).

Oder verwechsel ich das mit irgendeinem Unsinn?

Das, was Du sagst, ergibt genauso viel Sinn wie "Nachts ist es kälter als draußen". Zeige kleine, kompilierbare Codebeispiele. Sonst weiß keiner wovon Du redest. Und wenn man nicht weiß, wovon Du redest, kann man Dir auch nicht helfen. Und Hilfe hast Du bei Deinem gefährlichen Halbwissen wirklich nötig!

kk

zorro59 schrieb:

Aber nochmal danke für die Hilfe! Zu meiner letzten Frage. Objektinstanzen sind doch an sich schon immer eine Art Pointer, oder?

Nein. C++ ist kein Java.

Nexus

zorro59 schrieb:

Ihr habt Probleme. Ich habs mir einfach so gemerkt: man soll immer
const
benutzen, es sei denn das Resultat soll später noch verändert werden.

Die Regel ist zwar als Anfängerfaustregel okay, aber für eine generelle Richtlinie zu einfach. Ein paar Beispiele für schlecht eingesetztes const :

const int Function();

void Function(const int parameter);

class Person
{
    // ...
    const Date myBirthDate;
};

hustbaer schrieb:

Ich bin überhaupt der Meinung dass das Thema "= statt == verhindern" bei manchen etwas ausartet. Ich finde kaum etwas grässlicher als die - für mich vollkommen verqueren - Vergleiche ala if (0 == blah()) . *schüttel*

Schön, dass ich mit dieser Meinung nicht allein dastehe!