How can I create my own comparator for a map?

Question

typedef map<string, string> myMap;

When inserting a new pair to myMap, it will use the key string to compare by its own string comparator. Is it possible to override that comparator? For example, I'd like to compare the key string by its length, not by the alphabet. Or is there any other way to sort the map?

score 181 · Accepted Answer · answered Apr 20 '11 at 16:09

181

std::map takes up to four template type arguments, the third one being a comparator. E.g.:

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;

Alternatively you could also pass a comparator to maps constructor.

Note however that when comparing by length you can only have one string of each length in the map as a key.

answered Apr 20 '11 at 16:09

Georg Fritzsche

97,545
26
194
236

6

note that we can use multimap if we want to contain duplicated key – Xitrum Apr 20 '11 at 16:46
@GeorgFritzsche any chance you you provide an example of passing comparitor to constructor? – bpeikes Jun 17 '14 at 21:31
1

@bpeikes: It doesn't look too different: `std::map myMap(cmpByStringLength());` – Georg Fritzsche Jun 18 '14 at 14:29
I had a problem with a std::map, some with increasing order and others by decreasing order. I didn't want to use std::map and std::map because then I couldn't use maps which were sorted in different orders as parameters to a single function unless I made everything a template. I found that I had to do the following: typedef std::map mymap; Then I was able to pass in functions. I tried the following, but it wouldn't work: typedef std::map mymap; mymap map1(std::less); mymap map2(std::greater); – bpeikes Jun 18 '14 at 18:27
That would be `std::map m(std::less());` - note the parantheses. You definitely don't need function pointers. If you run into problems, best ask a new question about that. – Georg Fritzsche Jun 18 '14 at 21:03
2

@GeorgFritzsche: That won't work for passing the comparator to the constructor, as the constructor argument must be an instance of the comparator type, and `cmpByStringLength` is not an instance of `std::less`. For a general map that can have any comparator set in the constructor, you need something like `std::map> myMap(cmpByStringLength);` – Chris Dodd Oct 14 '15 at 18:54
if using map this way, will the order of length of strings be maintained if we are inserting string dynamically? – shane Apr 15 '16 at 13:51
I think in C++20, you can use lambda function as well as functor. – Kemin Zhou Oct 20 '20 at 04:34

honk · Answer 2 · 2018-02-07T14:58:49.370

Since C++11, you can also use a lambda expression instead of defining a comparator struct:

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;

Output:

1
two
three
fouuur

I'd like to repeat the final note of Georg's answer: When comparing by length you can only have one string of each length in the map as a key.

Code on Ideone

score 14 · Answer 3 · answered Apr 20 '11 at 16:11

14

Yes, the 3rd template parameter on map specifies the comparator, which is a binary predicate. Example:

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";
}

answered Apr 20 '11 at 16:11

John Dibling

99,718
31
186
324

11

Why the derive from `std::binary_function`? Is it needed? – Devolus Sep 01 '16 at 11:27
12

`std::binary_function` is removed in c++17 so this answer could probably use updating. – Dan Olson Nov 23 '17 at 00:13

score 3 · Answer 4 · answered Jul 19 '19 at 03:14

Specify the type of the pointer to your comparison function as the 3rd type into the map, and provide the function pointer to the map constructor:
map<keyType, valueType, typeOfPointerToFunction> mapName(pointerToComparisonFunction);

Take a look at the example below for providing a comparison function to a map, with vector iterator as key and int as value.

#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;
    }
}

this `decltype(int_vector_iter_comp)*` is brilliant ! thank you!! — Kobi, Jan 30 '22 at 02:48

How can I create my own comparator for a map?

4 Answers4

Linked

Related