(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.

Copy
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int a, b, w;
	bool operator<(const Edge &y) const { return w < y.w; }
};

int main() {
	int M = 4;

Comparator

With a Function

Copy
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int a, b, w;
};

bool cmp(const Edge &x, const Edge &y) { return x.w < y.w; }

int main() {

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

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

With Lambda Expressions

Copy
auto cmp = [](const Edge &x, const Edge &y) { return x.w < y.w; };

int main() {
	int M = 4;
	set<Edge, bool (*)(const Edge &, const Edge &)> v(cmp);
	for (int i = 0; i < M; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		v.insert({a, b, w});
	}
	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.

Copy
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int a, b, w;
};

struct cmp {
	bool operator()(const Edge &x, const Edge &y) const { return x.w < y.w; }
};

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

Copy
int main() {
	int M = 4;
	vector<Edge> v;
	for (int i = 0; i < M; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		v.push_back({a, b, w});
	}
	sort(begin(v), end(v), cmp());
	for (Edge e : v) cout << e.a << " " << e.b << " " << e.w << "\n";
}

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.

Copy
#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int a, b, w;
	bool operator>(const Edge &y) const { return w > y.w; }
};

int main() {
	int M = 4;

Other Containers

The following are all valid:

Copy
set<int, greater<int>> a;
map<int, string, greater<int>> b;
priority_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.