Wie kann ich einen eigenen Komparator für eine Karte erstellen?

83
typedef map<string, string> myMap;

Beim Einfügen eines neuen Paares in myMapwird der Schlüssel stringzum Vergleichen durch einen eigenen Zeichenfolgenkomparator verwendet. Ist es möglich, diesen Komparator zu überschreiben? Zum Beispiel möchte ich den Schlüssel stringnach seiner Länge vergleichen, nicht nach dem Alphabet. Oder gibt es eine andere Möglichkeit, die Karte zu sortieren?

Xitrum
quelle

Antworten:

140

std::mapEs werden bis zu vier Argumente vom Typ Vorlage verwendet, wobei das dritte ein Komparator ist. Z.B:

struct cmpByStringLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

// ...
std::map<std::string, std::string, cmpByStringLength> myMap;

Alternativ können Sie auch einen Komparator an den mapKonstruktor s übergeben .

Beachten Sie jedoch, dass beim Vergleich nach Länge nur eine Zeichenfolge jeder Länge in der Karte als Schlüssel verwendet werden kann.

Georg Fritzsche
quelle
4
Beachten Sie, dass wir Multimap verwenden können, wenn wir doppelte Schlüssel enthalten möchten
Xitrum
@GeorgFritzsche Gibt es eine Chance, dass Sie ein Beispiel für die Übergabe des Komparators an den Konstruktor angeben?
Bpeikes
1
@bpeikes: Es sieht nicht allzu anders aus:std::map<std::string, std::string> myMap(cmpByStringLength());
Georg Fritzsche
Ich hatte ein Problem mit einer std :: map <int, int>, einige mit aufsteigender Reihenfolge und andere durch abnehmende Reihenfolge. Ich wollte nicht std :: map <int, int, std :: größer> und std :: map <int, int, std :: less> verwenden, da ich dann keine Karten verwenden konnte, die in verschiedenen Reihenfolgen sortiert waren als Parameter für eine einzelne Funktion, es sei denn, ich habe alles zu einer Vorlage gemacht. Ich stellte fest, dass ich Folgendes tun musste: typedef std :: map <int, int, (bool) * (int, int)> mymap; Dann konnte ich Funktionen übergeben. Ich habe Folgendes versucht, aber es würde nicht funktionieren: typedef std :: map <int, int> mymap; mymap map1 (std :: less); mymap map2 (std :: größer);
Bpeikes
2
@GeorgFritzsche: Das funktioniert nicht, um den Komparator an den Konstruktor zu übergeben, da das Konstruktorargument eine Instanz des Komparatortyps sein muss und cmpByStringLengthkeine Instanz von ist std::less<std::string>. Für eine allgemeine Karte, für die ein beliebiger Komparator im Konstruktor festgelegt werden kann, benötigen Sie etwastd::map<std::string, std::string, std::function<bool(const std::string &, const std::string &)>> myMap(cmpByStringLength);
Chris Dodd,
19

Seit C ++ 11 können Sie auch einen Lambda-Ausdruck verwenden, anstatt eine Komparatorstruktur zu definieren:

auto comp = [](const string& a, const string& b) { return a.length() < b.length(); };
map<string, string, decltype(comp)> my_map(comp);

my_map["1"]      = "a";
my_map["three"]  = "b";
my_map["two"]    = "c";
my_map["fouuur"] = "d";

for(auto const &kv : my_map)
    cout << kv.first << endl;

Ausgabe:

1
zwei
drei
fouuur

Ich möchte die letzte Anmerkung von Georgs Antwort wiederholen: Wenn Sie nach Länge vergleichen, können Sie nur eine Zeichenfolge jeder Länge in der Karte als Schlüssel haben.

Code auf Ideone

hupen
quelle
12

Ja, der dritte Vorlagenparameter auf mapgibt den Komparator an, bei dem es sich um ein binäres Prädikat handelt. Beispiel:

struct ByLength : public std::binary_function<string, string, bool>
{
    bool operator()(const string& lhs, const string& rhs) const
    {
        return lhs.length() < rhs.length();
    }
};

int main()
{
    typedef map<string, string, ByLength> lenmap;
    lenmap mymap;

    mymap["one"] = "one";
    mymap["a"] = "a";
    mymap["fewbahr"] = "foobar";

    for( lenmap::const_iterator it = mymap.begin(), end = mymap.end(); it != end; ++it )
        cout << it->first << "\n";
}
John Dibling
quelle
11
Warum leiten sich die ab std::binary_function? Wird es gebraucht?
Devolus
12
std::binary_functionwird in c ++ 17 entfernt, daher könnte diese Antwort möglicherweise aktualisiert werden.
Dan Olson
1

Geben Sie den Typ des Zeigers auf Ihre Vergleichsfunktion als dritten Typ in der Karte an und geben Sie den Funktionszeiger für den Kartenkonstruktor an:
map<keyType, valueType, typeOfPointerToFunction> mapName(pointerToComparisonFunction);

Schauen Sie sich das folgende Beispiel an, um eine Vergleichsfunktion für a bereitzustellen map, mit vectorIterator als Schlüssel und intals Wert.

#include "headers.h"

bool int_vector_iter_comp(const vector<int>::iterator iter1, const vector<int>::iterator iter2) {
    return *iter1 < *iter2;
}

int main() {
    // Without providing custom comparison function
    map<vector<int>::iterator, int> default_comparison;

    // Providing custom comparison function
    // Basic version
    map<vector<int>::iterator, int,
        bool (*)(const vector<int>::iterator iter1, const vector<int>::iterator iter2)>
        basic(int_vector_iter_comp);

    // use decltype
    map<vector<int>::iterator, int, decltype(int_vector_iter_comp)*> with_decltype(&int_vector_iter_comp);

    // Use type alias or using
    typedef bool my_predicate(const vector<int>::iterator iter1, const vector<int>::iterator iter2);
    map<vector<int>::iterator, int, my_predicate*> with_typedef(&int_vector_iter_comp);

    using my_predicate_pointer_type = bool (*)(const vector<int>::iterator iter1, const vector<int>::iterator iter2);
    map<vector<int>::iterator, int, my_predicate_pointer_type> with_using(&int_vector_iter_comp);


    // Testing 
    vector<int> v = {1, 2, 3};

    default_comparison.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    default_comparison.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    default_comparison.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    default_comparison.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << default_comparison.size() << endl;
    for (auto& p : default_comparison) {
        cout << *(p.first) << ": " << p.second << endl;
    }

    basic.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    basic.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    basic.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    basic.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << basic.size() << endl;
    for (auto& p : basic) {
        cout << *(p.first) << ": " << p.second << endl;
    }

    with_decltype.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    with_decltype.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    with_decltype.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    with_decltype.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << with_decltype.size() << endl;
    for (auto& p : with_decltype) {
        cout << *(p.first) << ": " << p.second << endl;
    }

    with_typedef.insert(pair<vector<int>::iterator, int>({v.end(), 0}));
    with_typedef.insert(pair<vector<int>::iterator, int>({v.begin(), 0}));
    with_typedef.insert(pair<vector<int>::iterator, int>({v.begin(), 1}));
    with_typedef.insert(pair<vector<int>::iterator, int>({v.begin() + 1, 1}));

    cout << "size: " << with_typedef.size() << endl;
    for (auto& p : with_typedef) {
        cout << *(p.first) << ": " << p.second << endl;
    }
}
yyFred
quelle