std::set
(y std::map
, std::sort
, etc), no requiere que el comparador (llamémosle comp
) implemente un preorden total; de hecho, ni le exige ser preorden, ni le exige ser total. Lo que se le exige a los comparadores, cuando implementan <
, es que implementen un strict weak ordering, es decir, un órden estricto débil.
Un par de definiciones antes:
Dos elementos son comparables sii comp(a, b) == true
o comp(b, a) == true
. Dependiendo de las propiedades que tenga comp
, implementará <
, <=
, ==
, etc.
Dos elementos son iguales sii ocupan la misma posición en el rango (si it1 == it2
, entonces *it1
y *it2
son el mismo elemento). Ser equivalente es otra cosa. Ser igual es ser el mismo elemento.
Si un algoritmo de la STL espera que comp
defina una relación de equivalencia (std::equal
), entonces dos elementos son equivalentes sii son comparables, y por tanto, se espera que comp(*it, *it) == true
, ya que se asume que dos elementos iguales lo son. Por supuesto, elementos diferentes también podrían ser equivalentes, eso ya lo decide comp
, pero se espera que comp
, como mínimo, sea reflexivo, ya que una relación de equivalencia lo es.
Análogamente, si se espera que comp
implemente <
, entonces un elemento es menor a otro si son comparables solo en una dirección. Por tanto, comp(*it, *it) == false
, ya que <
debe filtrarnos elementos equivalentes.
Y std::set
necesita que comp
implemente <
.
Un preorden exige que todo elemento sea comparable consigo mismo (no lo queremos), mientras que un órden estricto exige que ningún elemento sea comparable consigo mismo (lo queremos). Además, <
nunca puede ser un órden total. Un órden total nos exige que para toda pareja de elementos, comp(a, b) || comp(b, a)
, sin importar quienes sean a
y b
. Por tanto, si a == b
, entonces comp(a, a) == true
, lo que tampoco nos permite implementar <
. Por eso std::set
no le existe a comp
que sea ni preorden, ni total.
comp
debe ser irreflexivo (un preorden es reflexivo), lo que prohibe explícitamente que cualquier elemento sea comparable consigo mismo, lo que implica además que el órden no puede ser total. Por eso creo que se le llama órden estricto, porque es estrictamente parcial.
¿Y qué es eso de órden estricto débil? Date cuenta que, al ser el orden parcial (al no poder exigir que toda pareja sea comparable), el comparador puede formar un "árbol" en vez de una línea de orden, donde un padre tenga varios hijos (todos menores que él, pero no comparables entre sí). Entonces hay que añadir una condición extra para conseguir nuestra línea (es decir, conseguir un órden total excepto autocomparaciones).
La condición extra es que, la propiedad de ser equivalente (es decir, de no ser comparable: !comp(*it1, *it2) and !comp(*it2, *it1)
), debe ser transitiva. Supón el siguiente arbolito:
a -> b -> c // a < b; b < c
d // b < d
e -> f // a < e; e < f
g // e < g
b y e son equivalentes, porque no se pueden comparar, y e y c también, por tanto, b y c deben ser equivalentes, y por tanto, no comparables. Lo que significa que e también debe ser padre de c, para romper la transitividad. Y también padre de d. Y b, padre de f, y de g. De esta manera, si dos elementos son equivalentes, todo elemento menor a uno, debe ser menor al otro, colapsando el árbol de la siguiente forma:
a -> b -> c
e d
e
f
donde cada nivel del árbol original es ahora como un único nodo de elementos equivalentes, y ya tenemos una línea de órden. Por eso, aunque la definición parezca "rara" o relajada, el comparador exigido es la relación < usual.
Es resumen, necesitas que tu comparador forme una línea de rectángulos, porque es exactamente lo que exige set
, y nada menos. Debes inventarte una relación de órden de modo que todos tus rectángulos formen una línea ordenada, incluso si colisionan, excepto que cuando uno está incluído en el otro, sean equivalentes, para que la STL lo tome como elemento repetido.
Por tanto, necesitas determinar, primero, si dos cuadrados son equivalentes (si uno está incluído en el otro, para que set no los elimine), y si lo son, devolver falso. Si no lo son, debes ordenarlos, por ejemplo, según la esquina inferior izquierda.
De todas formas, hay otras soluciones. Todo depende de cómo vayas a utilizar tu estructura. ¿Necesitas buscarlos frecuentemente, o necesitas tenerlos siempre ordenados, por ejemplo para borrar cuadrados a medida que aparecen y se van? Si es sí, entonces utiliza un std::set
, pero ten cuidado en qué orden metes los elementos, y que de cada grupo de cuadrados contenidos, el primero que llegue sea el más grande. O si la inserción falla, borra y reinsertas el nuevo si es más grande:
struct rectangle
{
rectangle(int x_, int y_, int w_, int h_) :
x{ x_ },
y{ y_ },
w{ w_ },
h{ h_ }
{}
bool contains(int x_, int y_) const
{
return (x_ >= x) &&
(x_ <= (x + w)) &&
(y_ >= y) &&
(y_ <= (y + h));
}
bool contains(rectangle const& r) const
{
return x <= r.x and x + w >= r.x + r.w and
y <= r.y and y + h <= r.y + r.h;
}
friend
bool operator<(rectangle const& r1, rectangle const& r2) const
{
return r1.x < r2.x and r1.y < r2.y;
}
int x{}, y{}, w{}, h{};
};
int main()
{
auto equiv_rect = [](rectangle const& r1, rectangle const& r2) {
return r1.contains(r2) or r2.contains(r1);
};
auto set_comp = [equiv_rect] (rectangle const& r1,
rectangle const& r2) {
return !equiv_rect(r1, r2) and r1 < r2;
};
// Asumimos que uno está contenido en el otro.
auto bigger = [](rectangulo const& r1, rectangulo const& r2) {
return r1.contains(r2);
};
std::set<rectangulo, decltype(set_comp)> rects;
while(your_cond()) {
rectangulo rect = next_rect();
do {
// Mientras haya alguien contenido en rect, o que contenga a
// rect, seguirá dando vueltas.
auto pair = rects.insert(rect);
if (!pair.second and bigger(rect, *pair.first))
rects.erase(pair.first);
else
break;
} while(1);
}
};
Si no necesitas tener los rectángulos continuamente ordenados, y solo quieres colapsarlos una vez, simplemente pásale un std::sort
a la estructura que utilices como almacenamiento final (por ejemplo, std::vector
), y luego un std::unique
para borrar elementos repetidos.
int main()
{
auto equiv_rect = [](rectangle const& r1, rectangle const& r2) {
return r1.contains(r2) or r2.contains(r1);
};
// Asumimos que uno está contenido en el otro.
auto bigger = [](rectangulo const& r1, rectangulo const& r2) {
return r1.contains(r2);
};
// Cuadrados equivalentes solo si son exáctamente iguales.
// Si no lo son, r1 < r2 or r2 < r1. Si uno está contenido en
// otro, el más grande va primero, para que `std::unique` no
// lo borre.
auto sort_comp = [equiv_rect] (rectangle const& r1,
rectangle const& r2) {
return (equiv_rect(r1, r2) and bigger(r1, r2)) or r1 < r2;
};
std::vector<rectangulo> rects;
// Rellena rects.
std::sort(rects.begin(), rects.end(), sort_comp);
rects.erase(std::unique(rects.begin(), rects.end(), equiv_rect),
rects.end());
// Usar `rects` a partir de ahora, que es muy eficiente para
// recorrer.
}
NOTA: Internamente, std::set
utiliza un árbol internamente, porque utiliza un árbol rojo-negro, una estructura que permite implementar árboles binarios de búsqueda completos eficientemente, y no porque tu comparador forme un árbol (de ahí quizás que pensaras que comp
fuera un preorden, confundiéndolo con órden parcial).
NOTA2: No sé si algo de esto funcionará. Es muy tarde y no lo he compilado :)
NOTA3: std::unordered_set
también es una opción, pero no lo he recomendado porque yo al menos no sé como utilizarlos adecuadamente. O mejor dicho, no sé como crear una función de hash adecuadamente. Quizás pasar los cuatro atributos del rectangulo a string, y devolver el hash
del string concatenado, pero quizás es una solución muy poco eficiente.