STL map mit eigenem Vergleichsoperator

Hallo,

ich habe folgendes Problem, ich möchte ein struct

struct my_struct_t {
 int a;
 int b;
};

als Index-Element einer map benuzten.

std::map<my_struct_t, double> my_map;

Der Compiler lehnt dies jedoch ab, weil kein Comparator für my_struct_t vorhanden ist. Leider darf ich keinen operator< in den struct einfügen, da dies aus einer automatisch generierten Library stammt.

Bei der map kann man ja anscheinend einen Comparator übergeben. Meine Versuche einen entsprechenden Comperator für my_struct zu schreiben scheiterten bisher allerdings und vernünftige Beispiel konnte ich im Internet bis jetzt auch noch nicht finden. Kann mir jemand helfen? Danke schon mal im voraus.

Gruß Chris

niemand

Beispiel Code:

struct Test {
   int a;
   int b;
};

class StructCompare {
public:
   operator()( const Test& a, const Test& b) { return a.a < b.a; };
};

void test() {
   typedef map<Test, double, StructCompare> TestMap;
   TestMap x;
   Test t;
   t.a = 1;
   t.b = 2;
   x.insert( make_pair( t, 0.1));
   t.a = 2;
   x.insert( make_pair( t, 0.2));
   t.a = 0;
   x.insert( make_pair( t, 0.3));

   for( TestMap::iterator it = x.begin(); it != x.end(); ++it) {
      cout << it->first.a << " " << it->second << endl;
   }
}

finix

struct StructCompare
{
  bool operator()( const Test& a, const Test& b) const { return a.a < b.a; };
};

Werner Salomon

finix schrieb:

struct StructCompare
{
  bool operator()( const Test& a, const Test& b) const { return a.a < b.a; };
};

niemand schrieb:

class StructCompare {
public:
   operator()( const Test& a, const Test& b) { return a.a < b.a; };
};

Irgendwie habt ihr beide den zweiten Member 'b' vergessen , oder? Chris hat nicht gesagt, dass sich alle Objekte der struct 'my_struct_t' ausschließlich im Member 'a' unterscheiden. Ich unterstelle mal, dass zwei Objekte 'my_struct_t' auch dann ungleich sein sollen, wenn der Member 'a' zwar jeweils der gleiche ist, aber sie sich in 'b' unterscheiden. Korrekt wäre dann

struct StructCompare
{
    bool operator()( const my_struct_t& x1, const my_struct_t& x2 ) const
    {
        if( x1.a < x2.a )
            return true;   // 'a' habe Priorität, also kleiner
        if( x2.a < x1.a )
            return false;  // x1.a ist definitiv größer, also false
        return x1.b < x2.b;    // bei Gleichheit entscheidet 'b'
    }
};

Eleganter - vielleicht nicht performanter - geht es auch mit dem pair-Trick.

struct StructCompare
{
    bool operator()( const my_struct_t& x1, const my_struct_t& x2 ) const
    {
        return std::make_pair( x1.a, x1.b ) < std::make_pair( x2.a, x2.b );
    }
};

.. intern passiert dasselbe wie oben.

ChrisMeise schrieb:

Leider darf ich keinen operator< in den struct einfügen, da dies aus einer automatisch generierten Library stammt.

musst Du auch nicht. Du kannst einen operator< auch als freie Funktion schreiben. Da alle Member public sind, ist das kein Problem.

bool operator<( const my_struct_t& x1, const my_struct_t& x2 )
{
    return std::make_pair( x1.a, x1.b ) < std::make_pair( x2.a, x2.b );
}   // oder die erste Implementierung (s.o.)

Jetzt sollte der Ausdruck

std::map< my_struct_t, double >

übersetzen. Welche der beiden Lösungen - also Funktor oder freie Funktion - man verwenden sollte, hängt davon ab, ob 'my_struct_t' so etwas wie eine natürliche Ordnung hat. Wenn ja, kann man die freie Funktion wählen. Falls die Ordnung qausi 'künstlich' und nur für den Zugriff in der map ist, ist der Funktor besser, da so der (evt. ungewollte!) Missbrauch des operator< ausgeschlossen ist.

Gruß
Werner

niemand

Die Funktion war (genau wie der struct vermutlich) nur als Beispiel gedacht. Zumindest hatte ich meinen Code nur als Beispiel gedacht, wie man einen entsprechenden Vergleich ohne erzeugen eines operator< erstellen kann.

finix

Werner Salomon schrieb:

Irgendwie habt ihr beide den zweiten Member 'b' vergessen , oder?

Ging mir nur darum die Klasse zu 'reparieren', sprich bool & const einzufügen.
Auch nicht unelegant, klappt dafür auch für mehr als zwei Attributen:

struct StructCompare
{
  bool operator()( const my_struct_t& lhs, const my_struct_t& rhs ) const
  {
    if (lhs.a != rhs.a) return lhs.a < rhs.a;
    return lhs.b < rhs.b;
  }
};

Danke allerseits, die Antworten haben mir weitergehofen.