PrevNext
Rare

(Optional) Sorted Sets with Custom Comparators

Authors: Benjamin Qi, Siyong Huang

Incorporating custom comparators into standard library containers.

Resources
fushar

Covers all of this material.

CPP

reference


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

Warning!

The code in this module assumes that all values of w are distinct. To properly handle cases with equal w, substitute std::multiset in place of std::set.

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.

#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

#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

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.

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

Pro Tip

One functor can be used for multiple objects.

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

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.

#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:

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.

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext