std::map mit compare-Funktion



  • Hallo.
    Ich habe nun angefangen mit mit std::map auseinanderzusetzen und das Ding gefällt mir bisher recht gut. Nun möchte ich als Key gerne ein char* verwenden, was durch eine compare-Funktion klappen sollte. Ich habe folgendes Beispiel gefunden: http://www.yolinux.com/TUTORIALS/CppStlMultiMap.html
    (Auszug:)

    struct cmp_str
     {
      bool operator()(char const *a, char const *b)
      {
        return std::strcmp(a, b) < 0;
      }
    };
    
    int main()
    {
      map<char *, int, cmp_str> Employees;
      // ...
    }
    

    Ich habe das nun auf meine Verwendung angepasst, mein Code sieht so aus:

    struct CmpStr
    {
       bool operator()(char const *a, char const *b)
       {
          return (strcmp(a, b) < 0);
       }
    };
    
    struct Module_s
    {
    	PyMethodDef m_pyMethods[20];
    	int m_iCounter;
    };
    
    std::map<char*, Module_s*, CmpStr> mapModules;
    

    Wenn ich dann compilen will, wird folgender Templatefehler von VC++ (2008) ausgespuckt:

    1>C:\Programme\Visual Studio\VC\include\xtree(1268) : error C3848: Ausdruck mit Typ 'const CmpStr' verliert beim Aufrufen von 'bool CmpStr::operator ()(const char *,const char *)' möglicherweise einige const-volatile-Qualifizierer
    1>        C:\Programme\Visual Studio\VC\include\xtree(1263): Bei der Kompilierung der  Klassen-template der std::_Tree_nod<_Traits>::_Node *std::_Tree<_Traits>::_Lbound(char *const &) const-Memberfunktion
    1>        with
    1>        [
    1>            _Traits=std::_Tmap_traits<char *,Module_s *,CmpStr,std::allocator<std::pair<char *const ,Module_s *>>,false>
    1>        ]
    1>        C:\Programme\Visual Studio\VC\include\map(78): Siehe Verweis auf die Instanziierung der gerade kompilierten Klassen-template "std::_Tree<_Traits>".
    1>        with
    1>        [
    1>            _Traits=std::_Tmap_traits<char *,Module_s *,CmpStr,std::allocator<std::pair<char *const ,Module_s *>>,false>
    1>        ]
    1>        d:\C++\...\Python.hpp(24): Siehe Verweis auf die Instanziierung der gerade kompilierten Klassen-template "std::map<_Kty,_Ty,_Pr>".
    1>        with
    1>        [
    1>            _Kty=char *,
    1>            _Ty=Module_s *,
    1>            _Pr=CmpStr
    1>        ]
    

    (Zeile 24 der Python.hpp entspricht hier der letzten Zeile meines Sourcecodes)

    Weiß jemand, was ich falsch mache? Ich finde einfach keinen Fehler.

    Edit: Mir fällt gerade auf, dass der Fehler nur erscheint, wenn ich folgenden Code nicht auskommentiere:

    // char *pszModule
    std::map<char*, Module_s*, CmpStr>::iterator it = mapModules.find(pszModule);
    

    Es wird also daran liegen, aber was zum Teufel ist da falsch?!

    Edit2: Ich habe auch gerade noch eine Verständnisfrage. Normalerweise sind 2 Strings doch gleich, wenn strcmp 0 returnt. Warum wird hier aber <0 benutzt?

    Gruß und Danke



  • Das liegt am operator() deines Function objects. std::map benutzt das Comparison Objekt, um zwei Value Objekte zu vergleichen. Da deine Value Objekte vom Typ Module_s* sind, das Comparison Objekt aber const char* erwartet kommt es zu Fehlermeldungen. std::map möchte gerne Äpfel vergleichen, aber du gibst ihr ein Function Objekt zum Vergleichen von Birnen. Da ist std::map natürlich sauer und will nicht mehr mitspielen.

    Der richtige Functor sieht dann so aus:

    struct CmpModule_s
    {
       bool operator()( const Module_s* obj1, const Module_s* obj2 )
       {
          // stelle Anhand irgendwelche Attribute fest, ob obj1 kleiner als obj2 ist
       }
    };
    

    PS:
    std::map erfordert sogenanntes strict weak ordering, da interessiert keine Gleichheit von Objekten. Ein Objekt muss immer kleiner oder grösser (im Sinne von "wird vor oder nach Referenzobjekt einsortiert") als das Referenzobjekt sein. Der operator() gibt ja einen bool zurück, und der kann nur einen von zwei Zuständen annehmen.


  • Administrator

    @DocShoe,
    Völliger Unsinn. std::map vergleicht doch nicht die Value Objekte sondern die Key Objekte. Und auch die Fehlermeldung sagt etwas völlig anderes aus.

    Das tatsächliche Problem liegt hier:

    struct CmpStr
    {
       bool operator()(char const *a, char const *b) const
    //                            Es fehlt ein const ^^^^^
       {
          return (strcmp(a, b) < 0);
       }
    };
    

    Grüssli



  • @ Dravere: Danke, das geht 🙂
    Kannst du mir dennoch erklären, warum man strcmp(x, y) < 0 und nicht == 0 benutzt?

    Gruß



  • Dravere schrieb:

    @DocShoe,
    Völliger Unsinn. std::map vergleicht doch nicht die Value Objekte sondern die Key Objekte. Und auch die Fehlermeldung sagt etwas völlig anderes aus.

    Das tatsächliche Problem liegt hier:

    struct CmpStr
    {
       bool operator()(char const *a, char const *b) const
    //                            Es fehlt ein const ^^^^^
       {
          return (strcmp(a, b) < 0);
       }
    };
    

    Grüssli

    ARGHS! Da bin ich völlig neben der Spur gelaufen (zumindest was den Funktor angeht) o.O.
    Das P.S. stimmt aber und erklärt auch, warum man <0 vergleicht statt ==0.


  • Administrator

    theliquidwave schrieb:

    Kannst du mir dennoch erklären, warum man strcmp(x, y) < 0 und nicht == 0 benutzt?

    Da stimmt das "PS" von DocShoe. Die Map muss wissen, wie es die Schlüssel ordnen kann, also welche Schlüssel kleiner sind und welche grösser. Die Gleichheit kann dann einfach durch verdrehen der Schlüssel festgestellt werden:

    int x = 4, y = 4;
    
    if(!(x < y) && !(y < x))
    {
      // Somit müssen die Schlüssel gleich sein.
    }
    

    Grüssli



  • Achso. Dann ergibt das ganze auch Sinn 🙂

    Gruß


Anmelden zum Antworten