[STL Map] Sortierung

Hi,

ich verwende mehrere Maps. Irgendwo meckert die STL library dass sie keinen Vergleichsoperator less findet der zwei Klassentypen von mir nimmt.

Ich vermute das kommt daher, dass bei einer Map der key kein Standardobjekt ist, sondern eine Klasse von mir. Sehe ich das richtig?

Leider meckert der Compiler nur an der Lib, nicht an meinem Code, daher weiss ich nciht welche Map Probleme macht. Ich vermute sowas:

typedef std::map<MeineKlasse, MeineKlasse> M;

Jetzt die Frage was ich tun kann:

1. Eigene Sortierung der map angeben? Wie geht das, ich finde kaum Dokumente
2. Kann ich in MeineKlasse den < Operator definieren? Kommt die Lib damit klar?

Danke
DKT

CStoll

Eine map benötigt irgendeine Möglichkeit, zwei Elemente zu vergleichen - auf diesem Vergleich basiert die gesamte Struktur der map (typisch ist ein balancierter binärer Suchbaum). Wenn deine Klasse keinen Vergleichs-Operator hat, bekommst du deshalb Probleme.

(und da ist es klar, daß die Probleme irgendwo im Inneren des STL-Codes gemeldet werden - dort, wo der operator< vermisst wird)

Zur Lösung hast du zwei Alternativen:

du spendierst der Klasse einen op<:

class MeineKlasse
{
  int number;
public:
  ...
  bool operator<(const MeineKlasse& other) const
  {
    //vergleiche *this und other miteinander
    return number<other.number;
  }
};
//Anmerkung: op< kann auch als globale Funktion angelegt werden

map<MeineKlasse,MeineKlasse> M;

du definierst einen Funktor, der die Objekte vergleicht:

class MeineKlasse
{
  int number;
public:
  int get_val() { return number; } // oder friend-Zugriff für compare
};

struct compare : public binary_function<MeineKlasse,MeineKlasse,bool>
{
  bool operator()(const MeineKlasse&l,const MeineKlasse&r) const
  { return l.get_val()<r.get_val(); }
};

map<MeineKlasse,MeineKlasse,compare/*Vergleichsfunktion*/> M;

Wow, danke CStoll für die gute schnelle Antwort.
Damit sind meine Vermutungen bestätigt.

Danke
DKT

MFK

CStoll schrieb:

struct compare : public binary_function<MeineKlasse,MeineKlasse,bool>
{
  bool operator()(const MeineKlasse&l,const MeineKlasse&r) const
  { return l.get_val()<r.get_val(); }
};

Was ich mich dabei schon mehrfach gefragt habe: Hat es irgendeinen Vorteil, von binary_function zu erben? Ohne geht doch auch, oder?

LordJaxom

...man hat die typedefs first_argument_type, second_argument_type und result_type geerbt, die ein Template potentiell benutzen könnte. Erbst Du nicht von binary_function, bekommst Du in so einem Fall (wenngleich mir der noch nicht untergekommen ist) halt nen Error, und musst die typedefs selbst anbringen.

CStoll

LordJaxom schrieb:

Erbst Du nicht von binary_function, bekommst Du in so einem Fall (wenngleich mir der noch nicht untergekommen ist) halt nen Error, und musst die typedefs selbst anbringen.

Alleinstehend wirst du damit keine Probleme bekommen - interessant wird es erst, wenn du den Funktor in einem Kontext benötigst, wo diese typedefs verwendet werden (z.B. mit std::bind2nd() oder std::not2() - die werten die Argument- und Ergebnistypen ihres Arguments aus, um ihre eigenen Typen festzulegen.

(und ehe ich später diese typedefs einfügen muß, habe ich mir angewöhnt, Funktoren gleich von unary_function bzw. binary_function abzuleiten)

MFK

Danke für die Info. Da ich <functional> bisher kaum benutzt habe, ist mir das noch nicht untergekommen.