Wie definiert man einen Schlüssel in einer Map?



  • Hallo zusammen!

    Ich möchte eine Map anlegen, mit einem Schlüssel(key_type), der aus einer Adresse und einer Sequenznummer besteht. Beides soll in den Schlüssel, damit ich später einfach pfrüfen kann ob eine Nachricht, die ich anhand des Keys unterscheiden will bereits in der Map ist oder nicht.
    So hatte ich mir den Schlüssel vorgestellt:

    class key_type{
    private:
    nsaddr_t sourceaddress;
    int sequenznummer;

    public:
    key_type(nsaddr_t saddress,int seq ) {
    sourceaddress = saddress;
    sequenznummer = seq;
    }
    friend bool operator < (const key_type& op1, const key_type& op2);
    };

    Der Compiler meldet mir einen Fehler bei dem bool operator, was nicht verwunderlich ist, denn die Zeile war geraten.

    Später wollte ich zu einem Schlüssel die Zeit hinzufügen:
    void LBM::addmessage(nsaddr_t sourceaddress, int sequenznummer){
    key_type index(sourceaddress,sequenznummer);
    messagemap[index]=CURRENT_TIME;
    };

    Meine Fragen:
    -Kann man einen Schlüssel aus zwei unterschiedlichen Typen wie oben definieren?
    -Wofür braucht man in einer Map unbedingt eine Ordnung?
    -wie erzeuge ich die Ordnung mit dem bool operator?

    Vielen Dank schon mal
    Moe31



  • -Kann man einen Schlüssel aus zwei unterschiedlichen Typen wie oben definieren?

    Ja ! Du musst halt nur definieren, weas groesser ist und was nich .... geht einfach und auch umstaendlich ....

    -Wofür braucht man in einer Map unbedingt eine Ordnung?
    Die map ist assiozativ ... und auf schnellen zugriff auf den key optimiert ...
    Die suche nach dem key ist also nicht sequentiell (was zu lange dauern wuerde, deine geschwindigekit waere dann linear abhaengig von der groesse des containers ) sonder mittels nen B-Baum (oder C-Baum oder Hashtable, je nach impl) ... die funktionieren so, das deine Map knoten anlegt, wo wegweisser in 2 verschiede richtungen anzeigt ... also groesser / kleiner als ....
    du hangelst dann nicht von element zu element, sondern von knoten zu knoten ala -> groesser als 50 ? nein -> groeser als 25 ? nein -> greosser als 13 ? nein -> ......
    damit findest dein Key schneller, und dafuer brauch er den lesser operator ...

    dein key muss den operator < nur unterstutzen ....
    also implementiere :

    class MyKeyClass
    {
    // was man sonst so braucht hier .... 
    public:
        bool operator < (const MyKeyClass & rx); 
    }
    

    oder als nichtmemberfunktion ....

    bool operator < (const MyKeyClass & rx1,const MyKeyClass & rx2);
    

    Alternativ kannst der Map auch ne externe Lesser Funktion uebergeben, dass sie nicht den < operator aufruft .... die Lesser Funktion musst als Template Paraemeter angeben.
    Falls du den operator fuer deine Klasse unschoen findest, solltest du es so machen ... siehe doku zu map / set

    wenn du nen key aus 2 werten zusammensetzt, die beide fuer sich schon den < operator unterstuetzen, kannst dir das leben auch einfacher machen :

    schau dir std::pair an ... der vergleicht dann zuerst first, und dann second fuers ergebnis

    also:

    typedef std::pair<nsaddr_t,int> MyKeyType; 
    typedef std::map<MyKeyType,WasWeissIchTyp> MyMapT;
    

    erzeugen kannst die dann so: MyKeyType mykey(adrr,iSeq) ; // wenn addr nsaddr_t, ind iSeq nen int ist ....
    berbeiten kannst die mit first und second ....

    einfuegen koenntest dann mit solchen konstrukten :

    MyMapT myMap; 
    
    myMap.insert(MyMapT::value_type(MyKeyType(adrr,iSeq),WasWeissIchObj));
    

    Prinzip verstanden ?

    Ciao ...



  • RHBaum schrieb:

    Die map ist assiozativ ... und auf schnellen zugriff auf den key optimiert ...
    Die suche nach dem key ist also nicht sequentiell (was zu lange dauern wuerde, deine geschwindigekit waere dann linear abhaengig von der groesse des containers ) sonder mittels nen B-Baum (oder C-Baum oder Hashtable, je nach impl) ... die funktionieren so, das deine Map knoten anlegt, wo wegweisser in 2 verschiede richtungen anzeigt ... also groesser / kleiner als ....

    Mit einem Hashtable??? Nein, niemals. Hashtable laesst keine effective implementierung der Funktionen: lower_bound & upper_bound.



  • Außerdem braucht die Hashmap eine Hashfunktion und keinen Vergleichsoperator.



  • Hallo,
    soweit so gut. 😉 Ich habe mich für die Variante mit pair entschieden.
    Leider bekomme ich beim erzeugen der Map folgene Fehlermeldung

    error: no match for 'operator=' in 'this->LBM::messagemap =
    (operator new(12), ((true, (<anonymous>->std::map<_Key, _Tp, _Compare,
    _Alloc>::map [with _Key = std::pair<nsaddr_t, int>, _Tp = double, _Compare =
    std::less<std::pair<nsaddr_t, int> >, _Alloc =
    std::allocator<std::pair<const std::pair<nsaddr_t, int>, double> >](),
    (<anonymous> <unknown operator> false))), <anonymous>))'
    /usr/include/c++/3.3/bits/stl_map.h:213: error: candidates are: std::map<_Key,
    _Tp, _Compare, _Alloc>& std::map<_Key, _Tp, _Compare,
    _Alloc>::operator=(const std::map<_Key, _Tp, _Compare, _Alloc>&) [with _Key
    = std::pair<nsaddr_t, int>, _Tp = double, _Compare =
    std::less<std::pair<nsaddr_t, int> >, _Alloc =
    std::allocator<std::pair<const std::pair<nsaddr_t, int>, double> >]
    make: *** [lbm/lbm.o] Error 1[code]

    erzeugen wollte ich die Map so:
    messagemap = new MessageMapT;[cpp]
    Und was jetzt?



  • Hast du auch einen Copy-Ctor sowie den op= definiert? Weil hier kommt wieder die "Regel der großen Drei" zum Zuge.

    http://fara.cs.uni-potsdam.de/~kaufmann/?page=GenCppFaqs&faq=BigThree


Log in to reply