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

127 Views Asked by At

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?

0

There are 0 best solutions below