(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
Resources | |||||
---|---|---|---|---|---|
SO |
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!