Multimap sortieren

[fujitsufan]

Hallo,
ist es möglich eine Multimap zu sortieren?
Ich kenne dies von einer Vektortabelle.
Das mache ich so:
Header.........

typedefstruct tY2Key
{
    double dPosY;
    int iKey;
} tY2Key;
 
vector <tY2Key> vList;
 
struct GreaterY2KeyPos : public std::binary_function<tY2Key, tY2Key, bool>
{
    bool operator()( consttY2Key &s1, consttY2Key &s2 ) const
    {
         returns1.dPosY > s2.dPosY;
     }
};

CPP......

sort(vList.begin(), vList.end(), GreaterY2KeyPos());

Meine Multimap sieht so aus..............

typedefstruct
{
    int idGroupBox; //ID BroupBox 9 + Uhrzeit
    int idTextCtrl; //ID EditBox 1 + Uhrzeit
    int idTakeOffCtrl; //ID Abzugstellung 2 + Uhrzeit
    int idDistance; //ID Abstand Zentrum - Text 3 + Uhrzeit
    int idDogging; //ID Basispunkt Text 4 + Uhrzeit
    int iBTurn0; //ID Text nicht wenden 5 + Uhrzeit
    int iBTurn1; //ID Text nicht wenden 6 + Uhrzeit
    string strDescr; //Bezeichner
} tKeySwitchCtrls;
 
tKeySwitchCtrls sKeySwitchCtrls;
typedef map <string, tKeySwitchCtrls, less<string> > tmKeySwitchCtrls;
tmKeySwitchCtrls mKeySwitchCtrls;

.......und möchte diese nach Gegebenheiten des Bezeichners (.first) der Multimap sortieren.

Der Bezeichner wird nach Uhrzeiten definiert.

mKeySwitchCtrls["10Uhr"] = sKeySwitchCtrls;
mKeySwitchCtrls["12Uhr"] = sKeySwitchCtrls;
mKeySwitchCtrls["2Uhr"] = sKeySwitchCtrls;

Die Multimap Reihenfolge sollte in der Map nach "12Uhr", "2Uhr", usw, ...."10Uhr" sein.

Ich versuche es mit folgender Funktion:

Header..............

struct GreaterClock : public std::binary_function<???, ???, bool>
{
    booloperator()(const ???&s1, const ???&s2) const
    {
        return s1.first > s2.first // nur zur Demonstation; Binärer Wert aus String filtern und verlgeichen
    }
};

    sort(this->mKeySwitchCtrls.begin(), this->mKeySwitchCtrls.end(), GreaterClock());

Funktioniert dies überhaupt mit einer Multimap???

Vielen Dank!

fujitsufan

 

[Technipion]

Hallo fujitsufan,
ohje, wo gehe ich jetzt am besten als erstes drauf ein?
Fangen wir mit den einfacheren Sachen an: Ich glaube deine Punkt-Taste hängt .
Nun zu deiner Frage:

Hallo,
ist es möglich eine Multimap zu sortieren?

Eine Multimap ist genau wie eine normale Map immer sortiert. Das ist die Haupteigenschaft dieses Containers. Sowohl bei std::map, als auch bei std::multimap, fügst du Paare aus Schlüssel und Eigenschaft hinzu. Intern liegen diese Daten dann immer nach Schlüssel sortiert vor. Dafür muss die Schlüsselklasse den "kleiner als"-Operator unterstützen (damit das Vergleichsobjekt - engl. comparison object - die Schlüssel über "kleiner als" - engl. less<Key> - sortieren kann). Du musst also für deine Schlüsselklasse den Operator '<' implementieren (im Idealfall auch noch den '=='-Operator, dann kann der Compiler alle anderen Operatoren aus diesen beiden ableiten).
Nun zu deinem Code. Deine typdefinierte Struktur tKeySwitchCtrls könnte man auch in eine Klasse packen, aber das ist wohl eher eine Stilfrage. Wenn ich das richtig verstanden habe, möchtest du mehrere dieser Strukturen mit einer zugehörigen Uhrzeit anlegen, und diese Paare sollen nach Uhrzeit sortiert sein. Hier kommt die erste Frage: Kann die gleiche Uhrzeit (als Schlüssel) mehrfach vorkommen? Wenn ja, nimm eine std::multimap (daher der Name), falls nicht (falls alle Uhrzeiten eindeutig sind), bleib bei der std::map. Das less<string> kannst du dir übrigens auch sparen, das ist ein Default-Parameter :

typedef map <string, tKeySwitchCtrls, less<string>> tmKeySwitchCtrls;

Aber fällt dir da nicht etwas auf? Als Vergleichsobjekt gibst du den "kleiner als"-Operator von std::string an. Ist das Absicht oder ein Versehen? Der '<'-Operator bei std::string führt einen lexikographischen Vergleich der Strings durch, d.h. sie werden so geordnet wie sie in einem Wörterbuch stehen würden.
Das ist aber vermutlich nicht die Art von Sortierung, die du dir vorgestellt hast. Ich vermute, du möchtest die Elemente in der Map in chronologischer Reihenfolge sortieren. Glücklicherweise bringt der C++-Standard ein mächtiges Werkzeug mit, wenn es um Rechnen mit Zeit geht: std::chrono. Du kannst natürlich auch statt der Strings einfach Integer nehmen, um die Anzahl der Stunden zu speichern, aber ich würde dir std::chrono ans Herz legen. Hier ist ein Minimalbeispiel um dir den Umgang damit zu Demonstrieren:

Spoiler: Minimalbeispiel

#include <iostream>
#include <map>          // for std::multimap
#include <chrono>       // for std::chrono::duration


int main()
{
    std::multimap<decltype(std::chrono::hours(0)), int> mKeySwitchCtrls;
    // decltype(std::chrono::hours(0)) = std::chrono::duration

    /*
    // Der []-Operator ist für std::multimap nicht definiert, da die Schlüssel nicht eindeutig sind!
    mKeySwitchCtrls[std::chrono::hours(10)] = 1;
    mKeySwitchCtrls[std::chrono::hours(12)] = 2;
    mKeySwitchCtrls[std::chrono::hours(2) ] = 3;
    */

    // Füge die Beispieluhrzeiten von dir hinzu:
    mKeySwitchCtrls.insert( std::make_pair(std::chrono::hours(10), 1) );
    mKeySwitchCtrls.insert( std::make_pair(std::chrono::hours(12), 2) );
    mKeySwitchCtrls.insert( std::make_pair(std::chrono::hours(2) , 3) );

    // Prüfen wir die Reihenfolge mit einer Ausgabe:
    for (const auto& mmPair : mKeySwitchCtrls) {

        std::cout << "Key: " << mmPair.first.count()
                     // mmPair.first.count() = std::chrono::hours.count()
                  << "\t|\tValue: " << mmPair.second << std::endl;
    }

    return 0;
}

Ich habe hier allerdings der Einfachheit halber nur int als Elemente verwendet, und nicht dein tKeySwitchCtrls. Es gibt im Internet zahlreiche Hilfestellungen wenn es um den Umgang mit std::chrono geht, und ggf. kannst du auch einfach wieder hier nachfragen.

Ich persönlich würde dir auf jeden Fall raten es so zu machen, std::chrono kümmert sich dann um die chronologische Sortierung (Achtung Wortspiel ). Sonst musst du dir überlegen, wie du eine eigene Vergleichsfunktion für deine "Uhrzeit-Strings" schreibst...

Ach ja: Wie du an der Ausgabe des Programms sehen können wirst, brauchst du die (Multi-)Map wirklich nicht mehr zu sortieren. Sie ist per Definition immer sortiert.

Falls was unklar war, frag einfach nach .

Grüße Technipion

 

[fujitsufan]

Hallo Technipion,

vielen Dank dafür, dass Du Dich so umfangreich dem Thema annimmst.

Strings vergleiche ich natürlich nicht mit dem > bzw. < Operator.
Das hatte ich auch im Kommentar vermerkt.
Da ziehe ich den Dezimalwert aus dem String und vergleiche diesen miteinander.
Das ist nicht mein Problem.

Mein Problem sind die Übergabeparameter, die mit ??? angegeben sind, was schreib ich da rein.

tKeySwitchCtrls oder tmKeySwitchCtrls ? Beides funktioniert nicht.

• struct GreaterClock : public std::binary_function<???, ???, bool>
• {
• booloperator()(const ???&s1, const ???&s2) const
• {
• return s1.first > s2.first // nur zur Demonstration; Binärer Wert aus String filtern und vergleichen
• }
• };

Ich hoffe Du verstehst was ich meine.

Vielen Dank!

fujitsufan

 

[Technipion]

Hallo fujitsufan,
jetzt habe ich die Frage glaube ich verstanden .

Die kurze Antwort: std::string.

Die lange Antwort:
Deine (Multi-)Map nutzt wie ich bereits erwähnt habe ein sogenanntes Vergleichsobjekt (engl. comparison object) um die Wertepaare in ihrem Inneren in einer bestimmten Reihenfolge zu sortieren. Der Standard sieht hier durch seinen Defaultwert vor, dass das Vergleichsobjekt less<Key> verwendet wird. Das ist ein Template-Funktionsobjekt, das einfach nur den '<'-Operator benutzt um zwei Elemente der Schlüsselklasse zu vergleichen. Daher mein erster Vorschlag, ob du nicht etwas Eigenes benutzen möchtest und dann den "kleiner als"-Operator überlädst. Wenn du eine Standardklasse wie std::string verwenden möchtest, solltest du natürlich nicht den Operator ändern. Stattdessen kannst du der std::map ein anderes Funktionsobjekt übergeben, das dann intern zum Auswerten der Reihenfolge benutzt wird. Wichtig ist an dieser Stelle dass du verstehst, was dieses Funktionsobjekt eigentlich tut: Die std::map wird es über den operator () aufrufen, und zwei KEYs als Argumente einsetzen. Der Rückgabewert true oder false entscheidet dann über die Reihenfolge dieser beiden Keys. Führt diese Map diese Vergleiche mit allen Key-Paaren durch, ist der Container gemäß deines Funktionsobjekts sortiert. Deine Funktion muss also "empfänglich" für den Aufruf operator () (const std::string, const std::string) sein, damit der Aufruf in der Map funktioniert.
Wenn du in deiner Funktion tKeySwitchCtrls oder tmKeySwitchCtrls als Parametertypen benutzt, findet der Compiler keine passende Funktionssignatur die zum Aufruf in std::map passt, daher bricht er an dieser Stelle die Übersetzung ab.
Also kurz und knapp: Sowohl std::map, als auch std::multimap, verwenden das Funktionsobjekt zum Vergleich zweier Schlüssel, das Funktionsobjekt muss diesen Aufruf also unterstützen.

Aber jetzt genug geschwafelt, ich weiß du willst Code sehen .

#include <iostream>
#include <map>          // for std::multimap
#include <string>       // for std::string
#include <sstream>      // for std::stringstream


typedef struct
{
    int idGroupBox; //ID BroupBox 9 + Uhrzeit
    int idTextCtrl; //ID EditBox 1 + Uhrzeit
    int idTakeOffCtrl; //ID Abzugstellung 2 + Uhrzeit
    int idDistance; //ID Abstand Zentrum - Text 3 + Uhrzeit
    int idDogging; //ID Basispunkt Text 4 + Uhrzeit
    int iBTurn0; //ID Text nicht wenden 5 + Uhrzeit
    int iBTurn1; //ID Text nicht wenden 6 + Uhrzeit
    std::string strDescr; //Bezeichner
} tKeySwitchCtrls;

// lexikographisch sortiert:
typedef std::map <std::string, tKeySwitchCtrls, std::less<std::string>> tmKeySwitchCtrls;


// Funktionsobjekt zum Vergleich der Elemente = Comparison object
struct chronoCompString {
    bool operator() (const std::string& x, const std::string& y) {
        int ix, iy;
        std::stringstream ss(x);
        ss >> ix;
        ss.str(y);
        ss >> iy;
        return ix < iy;
        // wäre das Leben schön wenn man std::stoi benutzen könnte...
        // ... aber mein MinGW unterstützt das noch nicht -.-
    }
};

// chronologisch sortiert:
typedef std::map <std::string, tKeySwitchCtrls, chronoCompString> tmKeySwitchCtrls_rev;


int main()
{
    tKeySwitchCtrls sKeySwitchCtrls;

    tmKeySwitchCtrls mKeySwitchCtrls;
    tmKeySwitchCtrls_rev mKeySwitchCtrls_rev;

    // Denk dran, das geht nur bei std::map
    mKeySwitchCtrls["10Uhr"] = sKeySwitchCtrls;
    mKeySwitchCtrls["12Uhr"] = sKeySwitchCtrls;
    mKeySwitchCtrls["2Uhr"] = sKeySwitchCtrls;

    mKeySwitchCtrls_rev["10Uhr"] = sKeySwitchCtrls;
    mKeySwitchCtrls_rev["12Uhr"] = sKeySwitchCtrls;
    mKeySwitchCtrls_rev["2Uhr"] = sKeySwitchCtrls;

    /// Ausgabe zum Testen:

    std::cout << "std::map mit less<string>:" << std::endl;

    for (const auto& mPair : mKeySwitchCtrls) {

        std::cout << "Key: " << mPair.first << std::endl;
    }

    std::cout << "\n\nstd::map mit chronoCompString:" << std::endl;

    for (const auto& mPair : mKeySwitchCtrls_rev) {

        std::cout << "Key: " << mPair.first << std::endl;
    }

    return 0;
}

Ich denke der Code ist relativ selbsterklärend. Falls du noch Fragen hast, kannst du aber natürlich einfach nachfragen.
Wie du übrigens an der Ausgabe sehen wirst, ist die Standard-Variante mit less<string> lexikographisch sortiert (also für dich in der falschen Reihenfolge) und die Variante mit unserem Closure chronologisch, also genau wie gewünscht .

Grüße Technipion