Strict Weak Ordering Problem (Less than and Less than equal operator)

Question

I am trying to solve this problem from HackerRank where I have overloaded the less than(<) and less than equal(<=) operator to compare the objects based on some custom conditions. My Code is below:

#include <bits/stdc++.h>
using namespace std;

class Expenditure
{
public:
    int value;
    int seq;

    Expenditure(int v, int s)
    {
        value = v;
        seq = s;
    }

    bool operator < (const Expenditure &other) const
    {
        if(this->value == other.value)
        {
            return this->seq < other.seq;
        }

        return this->value < other.value;
    }

    bool operator <= (const Expenditure &other) const
    {
        if(this->value == other.value)
        {
            return this->seq <= other.seq;
        }

        return this->value <= other.value;
    }
};

int main()
{
    int n, k, num, notice_count = 0;
    float median_value;
    cin>>n>>k;

    set<Expenditure>window;
    vector<int>arr;

    Expenditure median(-1, -1);

    for(int i = 0; i < n; i++)
    {
        cin>>num;
        arr.push_back(num);

        Expenditure newEntry(num, i);
        window.insert(newEntry);

        if(i == 0)
        {
            median = newEntry;
            median_value = median.value;
        }

        // Insert all the elements of the window first and calculate the median
        if(i < k)
        {
            if((window.size() % 2 == 0) && newEntry < median)
            {
                median = *(--window.lower_bound(median));
            } else if(window.size() % 2 != 0 && median < newEntry)
            {
                median = *(window.upper_bound(median));
            }
        } else
        {
            if(newEntry.value >= 2.0 * median_value)
            {
                notice_count++;
            }

            Expenditure removed(arr[k-i], k-i);
            window.erase(removed);

            // Update the median
            if(median < newEntry && removed <= median)
            {
                median = *(window.upper_bound(median));
            } else if(newEntry < median && median <= removed)
            {
                median = *(--window.lower_bound(median));
            }
        }

        // Update the median value based on window size even or odd
        if(i >= k - 1)
        {
            if(window.size() % 2 == 0)
            {
                median_value = (median.value + (*(window.upper_bound(median))).value)/2.0;
            } else
            {
                median_value = median.value;
            }
        }
    }

    cout<<notice_count<<endl;
}

I am getting segmentation fault but in my local computer, it is working fine. Then, I searched and saw that this may happen due to the violation of strict weak ordering. I have two operator overloading and can't get my head around of this violation.

Can anyone explain me in details, and how to avoid it and still use the overloaded operator?

You should define `==`, and then define `<=` in terms of `==`, and `<`. — cigien, May 31 '20 at 20:48
See this [answer](https://stackoverflow.com/a/4421719/8372853) it should help. — cigien, May 31 '20 at 21:00
It's only necessary to `overload<` because `a <= b` is equivalent to `!(b < a)`. That said I don't see the problem with your `operator<` or `operator<=`. Probably your bug is just something else. Dereferencing an invalid iterator would be the obvious possibility. — john, May 31 '20 at 21:09
Found the bug. Actually, the weak ordering was fine. Thanks @john for pointing out. The problem was with below line "Expenditure removed(arr[k-i], k-i);". This should be Expenditure removed(arr[i-k], i-k); — Setu Kumar Basak, Jun 01 '20 at 11:54

Strict Weak Ordering Problem (Less than and Less than equal operator)

0 Answers0