Writing a custom comparator for a C++ map which has a custom defined key

Question

I'm trying to write a custom comparator for a C++ map which has a custom defined key.

struct key { int year; int no; };
map<key, detail, compare> details_map;

if the year values are equal, it must compare the no values.

I'm trying to figure out a way to write a comparator that can compare both values. So far, I am only able to write a comparator which compares one value.

struct Compare{bool operator()(const key &lhs,const key &rhs)const{return lhs.year<rhs.year;}}

Can someone please explain how a comparator works in a map?

Also, is it possible to write the comparator as a function?

Use the conditional operators to compare more than one values, like you'd do in a normal function. — CinCout, Oct 04 '18 at 05:45
A corresponding Java question is https://stackoverflow.com/questions/4805606/how-to-sort-by-two-fields-in-java — Raedwald, Oct 04 '18 at 06:25
in c++ it is different than in Java. In c++ comparator is effectively "operator less", while in Java it is 3-way comparison. Analog in C++ is "operator spaceship", but it is only since c++ 20 and still std::map expects sort of "operator less" as Compare template argument. — ivan.ukr, Jul 20 '21 at 19:00

Remy Lebeau · Accepted Answer · 2021-07-20T18:36:51.793

8

Inside your operator(), simply compare the no values if the year values are equal:

struct Compare {
    bool operator()(const key &lhs, const key &rhs) const {
        if (lhs.year == rhs.year) {
            return lhs.no < rhs.no;
        }
        return lhs.year < rhs.year;
    }
};

And yes, a comparator can be implemented as a standalone function instead:

bool Compare (const key &lhs, const key &rhs) {
    if (lhs.year == rhs.year) {
        return lhs.no < rhs.no;
    }
    return lhs.year < rhs.year;
}

Alternatively, you can have your comparator use std::tie() to compare your key fields. See @Jarod42's answer.

Though, it would make more sense to implement operator< for your key type instead:

struct key {
    int year;
    int no;

    bool operator<(const key &rhs) const {
        if (year == rhs.year) {
            return no < rhs.no;
        }
        return year < rhs.year;
    }
};

Or

struct key {
    int year;
    int no;
};

bool operator<(const key &lhs, const key &rhs) {
    if (lhs.year == rhs.year) {
        return lhs.no < rhs.no;
    }
    return lhs.year < rhs.year;
}

Then you don't need a separate comparator:

map<key, detail> details_map;

edited Jul 20 '21 at 18:36

answered Oct 04 '18 at 05:50

Remy Lebeau

555,201
31
458
770

@ÖöTiib actually, I was thinking of `std::tie()`, I just couldn't remember it until I saw Jarod's answer – Remy Lebeau Oct 04 '18 at 08:40
From your solution, can we search for a key in the map using this 1 line of code " if( details_map.find( key_1 ) != details_map.end() ) " ? Or do we need to write any new function to compare the keys in this case ? -- Thank you. – Job_September_2020 Jul 20 '21 at 17:42
1

@Job_September_2020 Yes, with a proper comparator implemented (using any of the techniques shown), `find()` will work. – Remy Lebeau Jul 20 '21 at 18:36
Thanks. The find() method works when I write the comparator operator< as you suggested. However, I wonder why find() works if I do not write the comparator operator== or operator!= and I only need to write the operator< ? Is it because the compiler is smart enough so that from the operator<, it can deduce and construct the operator== and operator!= on its own ? - Thanks. – Job_September_2020 Jul 21 '21 at 05:39
@Job_September_2020 "*I wonder why find() works if I do not write the comparator operator== or operator!= and I only need to write the operator*" - because `std::map` simply does not use those other operators, it performs comparisons only in terms of `operator<`. "*Is it because the compiler is smart enough so that from the operator<, it can deduce and construct the operator== and operator!= on its own?*" - no. The compiler has nothing to do with this. This is strictly an implementation detail of how `std::map` is designed to work – Remy Lebeau Jul 21 '21 at 06:22

score 4 · Answer 2 · answered Oct 04 '18 at 08:22

std::tie allows simple lexicographical comparison:

struct Compare {
    bool operator()(const key& lhs, const key& rhs) const {
        return std::tie(lhs.year, lhs.no) < std::tie(rhs.year, rhs.no);
    }
};

Method/function as_tuple might be interesting to avoid some repetitions:

struct key { int year; int no; };

auto as_tuple(const key& k) { return std::tie(k.year, k.no); }

struct Compare {
    bool operator()(const key& lhs, const key& rhs) const {
        return as_tuple(lhs) < as_tuple(rhs);
    }
};

Writing a custom comparator for a C++ map which has a custom defined key

2 Answers2

Linked