In USACO Guide Silver, Under ‘Sorting & Searching’, section ‘Custom Comparators and Coordinate Compression’, I am unable to understand the Sorting by Multiple Criteria subsection.
The content in the subsections is captured by the screenshot below:
I am confused how the ‘bool operator<’ functions works.
In the explanation at the top of the section, it states that the comparator function needs to “compare the weights if the weights are not equal, and otherwise compare first vertices.” I believe the line:
if (width == y.width) { return width - y.width; }
does not achieve this purpose.
I have tested the code on Programiz(with some modification for the code to work; please tell me if my edits caused the error.)
Here is my code:
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct Edge {
int a, b, width;
Edge(int i, int j, int k) {
a = i;
b = j;
width = k;
}
bool operator<(const Edge &y) {
if (width == y.width) { return width - y.width; }
return a - y.a;
}
};
int main()
{
vector<Edge> edges;
Edge edge1(1, 2, 10);
edges.push_back(edge1);
Edge edge2(5, 2, 10);
edges.push_back(edge2);
Edge edge3(6, 2, 10);
edges.push_back(edge3);
Edge edge4(3, 2, 10);
edges.push_back(edge4);
Edge edge5(2, 2, 10);
edges.push_back(edge5);
sort(edges.begin(), edges.end());
for (Edge i : edges) {
cout << i.a << ' ' << i.b << ' ' << i.width << endl;
}
return 0;
}
And here is the output:
1 2 10
5 2 10
6 2 10
3 2 10
2 2 10
=== Code Execution Successful ===
I have set the weights and second vertices as identical, but the first vertices as varying. However I do not believe the vector is sorted(in fact not modifying the order at all, which I am quite certain after playing around with the values) according to the descriptions(I believe this is because the comparator function always returns 0 when the weights are equal).
Therefore I am now confused over the Guide’s meanings. Did I misinterpret the description or code, or have I implemented it wrong?
Any help is very much appreciated 
,
Eric Liu