map with struct as key works incorrectly

Question

I'm trying to use user-defined struct as a key in std::map. In order to do that, I define comparison operator inside the struct. Then I add two instances of the class into map.

#include <map>
#include <iostream>

struct Fraction {
    int num, den; // numerator and denumenator

    explicit Fraction() : num(1), den(1) {}
    explicit Fraction(int num_, int den_) : num(num_), den(den_) {}

    bool operator<(const Fraction& rhs) const {
        return num * rhs.den < den * rhs.num;
    }

};

int main() {
    std::map<Fraction, int> mymap;
    
    mymap[Fraction(100, 100)] = 1;
    mymap[Fraction(200, 200)] = 2;
    
    std::cout << mymap.at(Fraction(100, 100)) << std::endl;
    std::cout << mymap.at(Fraction(200, 200)) << std::endl;
}

I expect to get

1
2

but the result is

2
2

Why?

[Operator< and strict weak ordering](https://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering) — Jason, May 26 '23 at 09:45
In order to precise the very relevant @Jason comment: both ```Fraction``` represent the same value as it is enforced by the ```operator <``` — Oersted, May 26 '23 at 09:48
`100/100` and `200/200` are the same fraction, so the behavior looks correct to me? — HolyBlackCat, May 26 '23 at 09:48
Thanks everyone for answering the question. I added additional check in operator< in order to distinguish the two cases (which I need). — user43283, May 26 '23 at 10:01
I'd recommend passing an object for comparison instead of just modifying the `<` operator. Given `Fraction f1(1, 1); Fraction f2(2, 2);` you'd expect both `f1 < f2` and `f2 < f1` to yield false; the only scenario where you don't want this is when using this for the map, so use a custom type like `struct MapFractionLess { constexpr bool operator()(Fraction const& f1, Fraction const& f2) const { auto p1 = f1.num * f2.den; auto p2 = f1.den * f2.num; return (p1 == p2) ? (f1.den < f2.den) : (p1 < p2); } }; std::map ...` — fabian, May 26 '23 at 10:18
@user43283 *"added additional check"* Can you show the resulting operator? — HolyBlackCat, May 26 '23 at 10:22
@HolyBlackCat updated ``` inline bool operator<(const Fraction& rhs) const { if (num * rhs.den == den * rhs.num) { return std::tie(num, den) < std::tie(rhs.num, rhs.den); } return (num * rhs.den < den * rhs.num); } ``` — user43283, May 26 '23 at 10:50
@user43283 Please don't modify the question so that the answers you've gotten doesn't make sense. It's enough if you show that updated `operator<` here in the comments. Also note that I added a comment about updating `operator<` to my answer. — Ted Lyngmo, May 26 '23 at 10:52
Aha, so you not only want to distinguish those two fractions, but also to maintain a certain sort order (by the fraction values)? — HolyBlackCat, May 26 '23 at 11:01
I see. That should've been mentioned in the question. Because otherwise I was confused why you'd use this kind of comparator. — HolyBlackCat, May 26 '23 at 11:14

Ted Lyngmo · Accepted Answer · 2023-05-26T10:51:05.650

A map considers two Keys equal if neither a < b nor b < a is true.

mymap[Fraction(100, 100)] = 1;
mymap[Fraction(200, 200)] = 2;

The first fraction is 100/100 and the second is 200/200 and neither 100/100 < 200/200 nor 200/200 < 100/100 is true mathematically. You are not using integer division to do the comparison though, so lets check num * rhs.den < den * rhs.num; or 100*200 < 200*100 and the same applies there.

Neither 100*200 < 200*100 nor 200*100 < 100*200 is true - so they are considered equal.

This is why you in mymap[Fraction(200, 200)] = 2; overwrite the value stored by mymap[Fraction(100, 100)] = 1; and there is only one Key fraction in your map.

I noted that you said "I added additional check in operator< in order to distinguish the two cases" in the comments. This is probably a mistake since it will break the expectations users of your Fraction class will have. Consider this snippet:

Fraction a(100, 100);
Fraction b(200, 200);

if(a < b) {
    // should not happen
} else if(b < a) {
    // should not happen
} else {
    // the expected
}

If you've modified operator< to be able to use both a and b as Keys in your map, then one of the two "should not happen" cases will kick in.

Alternatives:

Use a std::multimap where multiple Keys considered equal can be stored. This will however change your mapping so that multiple 100/100 Keys can be stored, not only both 100/100 and 200/200.

Use a std::map with a custom comparator:

struct FractionCmp {
    bool operator()(const Fraction& lhs, const Fraction& rhs) const {
        if(lhs < rhs) return true;
        if(rhs < lhs) return false;
        // they are really equivalent, but:
        return lhs.num < rhs.num;
    }
};

std::map<Fraction, int, FractionCmp> mymap;

map with struct as key works incorrectly

1 Answers1