Search code examples
c++c++11stlcomparatorstl-algorithm

C++ custom comparator not working MWE


I know there has been few posts about this already, so feel free to remove my post, but this code:

#include <bits/stdc++.h>
#define tol 1e-9
using namespace std;

int n;
vector<pair<double,double>> vec;

struct comparator {
    bool operator () ( pair<double,double> &a, pair<double,double> &b ) {
        if ( fabs(a.first-b.first) < tol )
            return a.second < b.second;
        return a.first > b.first;
    }
};

int main() {
    int i,j,k,ts,cs= 0,m,sz;
    for ( ; 1 == scanf("%d",&n); ) {
        for ( vec.clear(), vec.reserve(n), i = 0; i < n; ++i )
            scanf("%lf %lf",&vec[i].second,&vec[i].first);
        sort(vec.begin(),vec.end(),comparator());
        for ( i = 0; i < n; ++i )
            printf("%lf %lf\n",vec[i].first,vec[i].second);
    }
    return 0;
}

is not working for this example:

2
120 60
60 90

I compile this as g++ -std=c++11 -o a mwe.cpp, and mine is g++ version 5.4


Solution

  • You confused resize() with reserve().

    When you write

    for ( vec.clear(), vec.reserve(n), i = 0; i < n; ++i )
    

    you reserve size n for vector vec, that is you're instructing vec to reserve memory size for a future expansion to n elements. But, at the moment, the size of vec remain zero.

    So, when you write

    scanf("%lf %lf",&vec[i].second,&vec[i].first); 
    

    you're writing in uninitialized objects.

    Very, very bad.

    Technically speaking: you're in UB (Undefined Behavior).

    Practically speaking: all can happens.

    When you write

    sort(vec.begin(),vec.end(),comparator());
    

    you're sorting a vector vec of zero size, where vec.begin() is equal to vec.end().

    In other words: std::sort() do absolutely nothing.

    Solution: avoid clear() (as pointed by Caleth, it's superfluous if you after resize() and reset all element) and use resize() instead of reserve()

    // -------vvvvvv
    for ( vec.resize(n), i = 0; i < n; ++i )
    

    Off Topic suggestions:

    • avoid not-standard includes as bits/stdc++.h
    • avoid old C I/O and use the new C++ one; so no std::scanf() and std::printf() and use std::cin and std::cout.