Jak mogę stworzyć własny komparator dla mapy?

87
typedef map<string, string> myMap;

Podczas wstawiania nowej pary do myMap, użyje klucza stringdo porównania przez własny komparator ciągów. Czy można zastąpić ten komparator? Na przykład chciałbym porównać klucz na stringpodstawie jego długości, a nie alfabetu. Czy jest jakiś inny sposób sortowania mapy?

Xitrum
źródło

Odpowiedzi:

142

std::mapprzyjmuje do czterech argumentów typu szablonu, trzeci to komparator. Na przykład:

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;

Alternatywnie możesz również przekazać komparator do mapkonstruktora s .

Zauważ jednak, że porównując według długości, możesz mieć na mapie tylko jeden ciąg o każdej długości jako klucz.

Georg Fritzsche
źródło
4
zauważ, że możemy użyć multimapy, jeśli chcemy zawierać zduplikowany klucz
Xitrum
@GeorgFritzsche jest szansa, że ​​podasz przykład przekazywania komparatora do konstruktora?
bpeikes
1
@bpeikes: Nie wygląda to inaczej:std::map<std::string, std::string> myMap(cmpByStringLength());
Georg Fritzsche
Miałem problem ze std :: map <int, int>, niektóre z rosnącym porządkiem, a inne z malejącym porządkiem. Nie chciałem używać std :: map <int, int, std :: Greater> i std :: map <int, int, std :: less> ponieważ wtedy nie mogłem używać map, które były posortowane w innej kolejności jako parametry pojedynczej funkcji, chyba że zrobiłem wszystko szablonem. Okazało się, że muszę wykonać następujące czynności: typedef std :: map <int, int, (bool) * (int, int)> mymap; Wtedy byłem w stanie przekazać funkcje. Próbowałem wykonać następujące czynności, ale to nie zadziałało: typedef std :: map <int, int> mymap; mymap map1 (std :: less); mymap map2 (std :: większy);
bpeikes
2
@GeorgFritzsche: To nie zadziała w przypadku przekazywania komparatora do konstruktora, ponieważ argument konstruktora musi być instancją typu komparatora i cmpByStringLengthnie jest instancją std::less<std::string>. Aby uzyskać ogólną mapę, która może mieć dowolny komparator ustawiony w konstruktorze, potrzebujesz czegoś takiegostd::map<std::string, std::string, std::function<bool(const std::string &, const std::string &)>> myMap(cmpByStringLength);
Chris Dodd
22

Od C ++ 11 zamiast definiowania struktury komparatora można również użyć wyrażenia lambda :

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;

Wynik:

1
dwa
trzy
fouuur

Chciałbym powtórzyć ostatnią nutę odpowiedzi Georga: Porównując według długości, możesz mieć na mapie tylko jeden ciąg każdej długości jako klucz.

Koduj w Ideone

dźwięk klaksonu
źródło
12

Tak, trzeci parametr szablonu na mapokreśla komparator, który jest predykatem binarnym. Przykład:

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
źródło
11
Dlaczego pochodzą z std::binary_function? Czy to potrzebne?
Devolus
12
std::binary_functionzostała usunięta w c ++ 17, więc ta odpowiedź prawdopodobnie przydałaby się aktualizacja.
Dan Olson
1

Określ typ wskaźnika do funkcji porównania jako trzeci typ na mapie i podaj wskaźnik funkcji do konstruktora mapy:
map<keyType, valueType, typeOfPointerToFunction> mapName(pointerToComparisonFunction);

Spójrz na poniższy przykład, w którym przedstawiono funkcję porównania do a map, z vectoriteratorem jako kluczem i intwartością.

#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
źródło