C | STL Sort() Function Third Argument Complexity confusions-CodePudding

Suppose, we have a 2D vector<vector<int>> vec;

We need to sort this 2D vector. I tried with two methods below:

Method 1: Using a comparator function

static bool cmp(vector<int> a, vector<int> b) {
    return a[1] < b[1];
}
...
sort(vec.begin(),vec.end(),cmp);

Method 2: Using a lambda

sort(vec.begin(), vec.end(), [](const vector<int>& a, vector<int>& b) {
    return a[1] < b[1];
});

For a problem from leetcode, Method 1 caused a "Time Limit Exceeded" verdict, while Method 2 was accepted.

Can there be that much contrast between these two methods in terms of time complexity?

CodePudding user response：

vector<int> a makes a copy of the vector while const vector<int>& a just passes the address. Huge difference.

CodePudding user response：

Your comparator is taking its parameters by value, which means every vector object that sort() passes to cmp() will have to be copied in memory. That increases time complexity and memory usage, multiplied out by however many elements are actually in your vectors.

Your lambda, on the other hand, is taking its parameters by reference instead, which means every vector object that sort() passes to the lambda will have only its current memory address passed, no copies are made. So there is no increase in time complexity.

Simply update your comparator to take reference parameters, and then the two methods will have similar complexity:

static bool cmp(const vector<int> &a, const vector<int> &b) {
    return a[1] < b[1];
}