C++: “invalid comparator” assert

Question

Here is the code:

struct Payment
{
    Payment(time_t time, float money) : mTime(time), mMoney(money) {}
    bool operator==(const Payment& p) const // exact comparison
    {
        return mTime == p.mTime && mMoney == p.mMoney;
    }
    time_t  mTime;
    float   mMoney;
};

std::vector<Payment>    payments;

auto sortP = [](const Payment& p1, const Payment& p2) { return p1.mTime < p2.mTime || p1.mMoney <= p2.mMoney; };
std::sort(payments.begin(), payments.end(), sortP);

std::sort (not always, but sometimes, when mTime of two elements close to each other) raises invalid comparator assert in Visual Studio 2015. What's wrong with the code?

`|| p1.mMoney <= p2.mMoney` should be `|| ((p1.mTime == p2.mTime) && (p1.mMoney < p2.mMoney))` Otherwise comparison will be wrong for case when `p1.mTime` is greater than `p2.mTime` while `p1.mMoney` is less than `p2.Money`. — user7860670, Aug 30 '17 at 17:52
Comparing two floats is not a good idea, floats are not represented exactly, they are approximations. You need to compare that the difference is less than some delta. by the same reasoning putting money in a float is not a good idea. — AndersK, Aug 30 '17 at 17:55
@VTT: You are right, this is the solution. Make it an answer, I'll accept. — deko, Aug 30 '17 at 17:58
In general you cannot use `<=` for strict weak ordering, as it requires false for equal elements. — Slava, Aug 30 '17 at 18:00
@AndersK. in this case delta is not required, unless OP uses that criteria to find element. For actual sorting it can make it slower. — Slava, Aug 30 '17 at 18:03
@Slava It's not just speed. Comparison with delta is not a valid strict weak ordering. — T.C., Aug 30 '17 at 19:11
@AndersK. first of all it will work, maybe not the way somebody would expect it, second strict weak ordering, which is used by `std::sort()` does not use `==` — Slava, Aug 30 '17 at 19:29
@Stava it is an error to compare floats with each other since floats are not exactly represented, my comment is directed to his comparison function, not whether it fits in this particular fringe case. — AndersK, Aug 30 '17 at 19:38

R Sahu · Answer 1 · 2022-11-10T05:59:21.720

7

The problem is with the implementation of sortP. It does not satisfy the strictly weak ordering criteria. Read the details at https://www.boost.org/sgi/stl/StrictWeakOrdering.html.

I suggest the following change:

auto sortP = [](const Payment& p1, const Payment& p2)
{
   // Order by mTime if they are not equal.
   if ( p1.mTime != p2.mTime)
   {
     return p1.mTime < p2.mTime;
   }

   // Otherwise, order by pMoney
   return ( p1.mMoney < p2.mMoney); // Use < not <=
};

You can use std::tie to make the implementation simpler.

auto sortP = [](const Payment& p1, const Payment& p2)
{
   return std::tie(p1.mTime, p1.mMoney) < std::tie(p2.mTime, p2.mMoney);
};

edited Nov 10 '22 at 05:59

answered Aug 30 '17 at 18:01

R Sahu

204,454
14
159
270

3

Using `std::tie` is simpler – Slava Aug 30 '17 at 18:01
@Slava, of course. Thanks for the hint. – R Sahu Aug 30 '17 at 18:04
The link in your answer is broken. – CourageousPotato Nov 03 '22 at 05:16
1

@CourageousPotato, Thanks for pointing out the broken link. Removed the old link and added a new link. – R Sahu Nov 10 '22 at 06:00

score 1 · Accepted Answer · edited May 17 '20 at 16:41

1

|| p1.mMoney <= p2.mMoney should be || ((p1.mTime == p2.mTime) && (p1.mMoney < p2.mMoney)) Otherwise comparison will be wrong for case when p1.mTime is greater than p2.mTime while p1.mMoney is less than p2.Money. A good practice to ensure that such multi-field comparator satisfy strict weak ordering requirement is to write tests for all possible lt/gt combinations of fields.

edited May 17 '20 at 16:41

R Sahu

204,454
14
159
270

answered Aug 30 '17 at 18:03

user7860670

35,849
4
58
84

5

Good practice is to use `std::tie` – Slava Aug 30 '17 at 18:04

score 1 · Answer 3 · answered Aug 30 '17 at 18:05

1

Using c++11 your comparator lambda should look like:

#include <tuple>
...
auto sortP = [](const Payment& p1, const Payment& p2) 
{ 
     return std::tie(p1.mTime, p1.mMoney) < std::tie(p2.mTime, p2.mMoney);
};

answered Aug 30 '17 at 18:05

ikleschenkov

972
5
11

C++: “invalid comparator” assert

3 Answers3