C++ | STL Sort() Function Third Argument Complexity confusions

Question

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?

Do you know the difference between passing a variable by value and passing a variable by reference? — NathanOliver, Jun 23 '22 at 16:44
C++ is not Java, Python, C#, or any other language you have been using (with the notable exception of `C` and maybe others). There is a huge difference in how C++ passes objects as opposed to those languages. C++ passes objects by value, meaning a copy will be made -- that entire vector-in-a-vector is copied to a temporary. If you want to pass a reference in C++, you must *explicitly* state you want to do this -- there is no "automatic pass by reference" in C++. — PaulMcKenzie, Jun 23 '22 at 16:45
Also, sites like LeetCode are not designed to learn the basics of C++. Sites such as that one ask basic random puzzle questions, and the assumption is that you know the language you will be using well-enough to not make the mistake(s) you made with this code. Learning how C++ passes variables should be basic C++ knowledge, and is covered in any good C++ book at very early stages of learning the language. — PaulMcKenzie, Jun 23 '22 at 16:49
And to add, you didn't mention "Method 3" -- sort a vector of indices instead of the 2D array. Much faster, and especially if those internal vectors contain many elements. [See this answer](https://stackoverflow.com/questions/46382252/sort-array-by-first-item-in-subarray-c/46382976#46382976). — PaulMcKenzie, Jun 23 '22 at 16:52
`return a[1] < b[1];` is also kind of worrying as `std::vector`s are `0` based. — Richard Critten, Jun 23 '22 at 16:55
*Can there be that much contrast between these two methods in terms of time complexity?* **Yes**. Pass by value can be expensive. Pass by const reference is very cheap, unless the type is one of the primitive types or a very small POD. — Eljay, Jun 23 '22 at 17:34

score 2 · Answer 1 · answered Jun 23 '22 at 16:44

2

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

answered Jun 23 '22 at 16:44

Goswin von Brederlow

11,875
2
24
42

score 2 · Answer 2 · answered Jun 23 '22 at 16:48

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];
}

C++ | STL Sort() Function Third Argument Complexity confusions

2 Answers2