0

The following code crashes when I call std::sort on the bks (vector of vectors) of form [20000][3]. It seems the comparator compBks() is getting called on v1 of size 0 and v2 of size 3 after 20000 calls to compBks have been made, which could cause the crash.

But why is compBks being called with invalid v1?

Any reason?

class Solution {
public:
    struct compBks {
        bool operator() (vector<int> v1, vector<int> v2) {
            cout << v1.size() << " " << v2.size() << endl;
            if (v1[0] < v2[0]) return true;
            else if (v1[0] == v2[0]) 
                return v1[1] <= v2[1];
            return false;
        }
    };

    vector<int> corpFlightBookings(vector<vector<int>>& bks, int n) {
        vector<int> res(n, 0);
        sort(bks.begin(), bks.end(), compBks());
        return res;
    }
};

int main() {
   Solution s;
   vector<vector<int>> bks(20000, {1, 20000, 10000});
   s.corpFlightBookings(bks, 20000);
}

Crash is: runtime error: reference binding to null pointer of type 'value_type' (stl_vector.h)

Just before crash, compBks() prints v1.size as 0 and v2.size as 3.

Why would it v1 ever get size of 0 if std::sort is being called correctly for bks?

Joe Black
  • 625
  • 6
  • 19
  • Is this real code? Does the `Solution` class have a member function named `main`? – n. m. could be an AI Jul 07 '19 at 05:39
  • @n.m. fixed. real code. – Joe Black Jul 07 '19 at 05:41
  • 2
    Your comparator doesn't implement the required ordering relation. It reports that every element of your array is less than every other element. This is UB. You want to change that `<=` to `<`. – n. m. could be an AI Jul 07 '19 at 05:51
  • 1
    `<=` has no place in a strict weak order, which is required for any comparator for any standard library algorithm requiring ordering. Unrelated, those arguments should be by `const` reference, and the `operator()` itself should be `const` as well. But your root problem is the broken use of `<=`. Do what @n.m. said: change that to `<`. Fwiw, `std::vector` already supports `operator<`, and the default implementation may be sufficient . You may not need that custom comparator in the first place, so its worth the check. – WhozCraig Jul 07 '19 at 05:55
  • Another possible dupe: [SO: Why will std::sort crash if the comparison function is not as operator ](https://stackoverflow.com/q/18291620/7478597) – Scheff's Cat Jul 07 '19 at 05:57

0 Answers0