(Opcional) Conjuntos ordenados con comparadores personalizados

Recursos

Recursos
Fuente	Recurso	Notas
fushar	Comparison Functions in C++	Cubre todo este material.
CPP	Set	referencia

Introducción

¿Qué pasa si queremos usar un set de C++ con el struct Edge que se definió en Ordenamiento con comparadores personalizados?

Sobrecarga de operadores

Funciona como se espera, aunque hay que asegurarse de incluir el segundo const o se produce un error de compilación. Del enlace de arriba:

[El segundo const] significa que no se pueden modificar las variables miembro del objeto actual.


#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;
	set<Edge> v;
	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";
}

Comparador

Recursos
Fuente	Recurso	Notas
SO	Using custom std::set comparator

Con una función


#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() {
	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";
}

También se puede usar la siguiente sintaxis para declarar el set v usando una función:

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

Con expresiones lambda


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

También se puede usar la siguiente sintaxis para declarar el set v usando una lambda

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

aunque decltype(cmp) no es realmente equivalente a bool(*)(const Edge&,const Edge&). Ver Expresiones lambda para más detalles.

Functores

Probablemente menos confuso que el método de arriba.


#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; }
};
 
int main() {
	int M = 4;
	set<Edge, cmp> v;
	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";
}

También podemos usar cmp como una función normal agregando () después.


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

Functores predefinidos

Sobrecargar el operador menor que (<) genera automáticamente el functor less<Edge>. De forma análoga, sobrecargar (>) genera automáticamente el functor greater<Edge>. Podemos usar esto para guardar un set en orden inverso.


#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;
	set<Edge, greater<Edge>> v;
	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";
}
 
/* Output:
2 3 10
1 2 9
1 3 7
2 4 3
*/

Otros contenedores

Los siguientes son todos válidos:


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

Usar un comparador personalizado para colas de prioridad es especialmente común. Recordemos que una cola de prioridad de C++ extrae por defecto su elemento más grande, mientras que el código de arriba hace que extraiga el elemento más chico.

Problemas

Ver el módulo de Línea de barrido para una tarea que usa un set con un comparador personalizado.