(Optional) C++ Sets with Custom Comparators

What if we want to use a C++ set with the Edge struct that was defined in Sorting with Custom Comparators?

Operator Overloading

Works as expected, although you should make sure to include the second const or you'll get a compilation error. From the link above:

[The second const] means you cannot modify member variables of the current object.

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge {
5    int a,b,w;
6    bool operator<(const Edge& y) const { return w < y.w; }
7};
8
9int main() {
10    int M = 4;

Comparator

With a Function

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge {
5    int a,b,w;
6};
7
8bool cmp(const Edge& x, const Edge& y) { return x.w < y.w; }
9
10int main() {

You can also use the following syntax to declare set v using a function:

set<Edge,decltype(&cmp)> v(cmp);

With Lambda Expressions

1auto cmp = [](const Edge& x, const Edge& y) { return x.w < y.w; };
2
3int main() {
4    int M = 4;
5    set<Edge,bool(*)(const Edge&,const Edge&)> v(cmp);
6    for (int i = 0; i < M; ++i) {
7        int a,b,w; cin >> a >> b >> w;
8        v.insert({a,b,w});
9    }
10    for (Edge e: v) cout << e.a << " " << e.b << " " << e.w << "\n";

You can also use the following syntax to declare set v using a lambda

set<Edge,decltype(cmp)> v(cmp);

even though decltype(cmp) is not actually equivalent to bool(*)(const Edge&,const Edge&). See Lambda Expressions for details.

Functors

Probably less confusing than the method above.

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge {
5    int a,b,w;
6};
7
8struct cmp {
9    bool operator()(const Edge& x, const Edge& y) { return x.w < y.w; }
10};

We can also use cmp like a normal function by adding () after it.

1int main() {
2    int M = 4;
3    vector<Edge> v;
4    for (int i = 0; i < M; ++i) {
5        int a,b,w; cin >> a >> b >> w;
6        v.push_back({a,b,w});
7    }
8    sort(begin(v),end(v),cmp());
9    for (Edge e: v) cout << e.a << " " << e.b << " " << e.w << "\n";
10}

Built-In Functors

Overloading the less than operator (<) automatically generates the functor less<Edge>. Similarly, overloading (>) automatically generates the functor greater<Edge>. We can use this to store a set in reverse order.

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge {
5    int a,b,w;
6    bool operator>(const Edge& y) const { return w > y.w; }
7};
8
9int main() {
10    int M = 4;

Other Containers

The following are all valid:

1set<int,greater<int>> a;
2map<int,string,greater<int>> b;
3priority_queue<int,vector<int>,greater<int>> c;

Using a custom comparator for priority queues is especially common. Recall that a C++ priority queue will pop its largest element by default, while the above code will cause one to pop its smallest element instead.

Problems

Check the Sweep Line module for a task that uses a set with a custom comparator.