Customize the behavior of std::set to filter data

std::set(and std::map, std::sort, etc), does not require the matcher (let's call it comp) to implement full preordering; in fact, neither does it require it to be preorder, nor does it require it to be total. What is required of comparators, when they implement <, is that they implement a strict weak ordering , that is, a weak strict ordering.

A couple of definitions before:

• Two elements are comparable if comp(a, b) == trueor comp(b, a) == true. Depending on the properties it has comp, it will implement <, <=, ==, etc.

• Two elements are equal if they occupy the same position in the range (if it1 == it2, then *it1and *it2are the same element). Being equivalent is something else. To be equal is to be the same element.

If an STL algorithm expects you to compdefine an equivalence relation ( std::equal), then two elements are equivalent if they are comparable, and therefore , comp(*it, *it) == truesince two equal elements are assumed to be equal. Of course, different elements could also be equivalent, that's for you to decide comp, but it is expected that compat least be reflexive, since an equivalence relation is.

Similarly, if it is expected to compimplement <, then one element is less than another if they are comparable in only one direction. Therefore, comp(*it, *it) == false, since it <must filter us equivalent elements.

And std::setyou need me to compimplement <.

A preorder requires that every element be comparable with itself (we don't want that), while a strict order requires that no element be comparable with itself (we want that). Furthermore, <it can never be a total order. A total order requires that for every pair of elements, comp(a, b) || comp(b, a), regardless of who they are aand b. Therefore, if a == b, then comp(a, a) == true, which also does not allow us to implement <. That is why it std::setdoes not exist for compit to be neither preorder nor total.

compmust be irreflexive (a preorder is reflexive), which explicitly prohibits any element from being comparable with itself, which further implies that the order cannot be total. That is why I think it is called a strict order , because it is strictly partial .

And what is this weak strict order ? Note that, since the order is partial (not being able to require that every pair be comparable), the comparator can form a "tree" instead of a line of order, where a parent has several children (all younger than it, but not comparable to each other). So we have to add an extra condition to get our line (that is, get a total order except self-comparisons).

The extra condition is that the property of being equivalent (that is, not being comparable: !comp(*it1, *it2) and !comp(*it2, *it1)), must be transitive. Suppose the following tree:

 a -> b -> c // a < b; b < c
           d //        b < d
      e -> f // a < e; e < f
           g //        e < g

b and e are equivalent, because they cannot be compared, y and c also, therefore, b and c must be equivalent, and therefore not comparable. Which means that e must also be a parent of c, to break transitivity. And also father of d. And b, father of f, and of g. In this way, if two elements are equivalent, every element less than one must be less than the other, collapsing the tree as follows:

a -> b -> c
     e    d
          e
          f

where each level of the original tree is now like a single node of equivalent elements, and we already have an order line. Therefore, although the definition seems "strange" or relaxed, the required comparator is the < usual relation.

In short, you need your comparator to form a line of rectangles, because that is exactly what is required set, and nothing less. You must invent an order relationship so that all your rectangles form an ordered line, even if they collide, except that when one is included in the other, they are equivalent, so that the STL takes it as a repeated element.

Therefore, you need to first determine if two squares are equivalent (if one is included in the other, so that set doesn't remove them), and if they are, return false. If they are not, you should order them, for example, according to the lower left corner.

However, there are other solutions. It all depends on how you are going to use your structure. Do you need to search for them frequently, or do you need to always have them sorted, for example to delete squares as they come and go? If it is yes, then use a std::set, but be careful in what order you put the elements, and that of each group of contained squares, the first one that arrives is the largest. Or if the insert fails, delete and reinsert the new one if it's bigger:

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

If you don't need to have the rectangles continuously sorted, and only want to collapse them once, simply pass a std::sortto the structure you use as final storage (for example, std::vector), and then a std::uniqueto delete repeated elements.

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

NOTE: Internally, std::setit uses a tree internally, because it uses a red-black tree, a structure that allows you to implement full binary search trees efficiently, and not because your matcher forms a tree (hence perhaps you thought it compwas a preorder, mistaking it for partial order).

NOTE2: I don't know if any of this will work. It's too late and I haven't compiled it :)

NOTE3: std::unordered_set it is also an option, but I have not recommended it because I at least don't know how to use them properly. Or rather, I don't know how to create a hash function properly. Perhaps pass the four attributes of the rectangle to string, and return the hashone of the concatenated string, but perhaps it is a very inefficient solution.

In a std::set it is determined that one element is equal to another using the operator<() when this returns false in both directions of comparison. That is, if you have two rectangles a and b, they will be equal if operator<(a, b) and operator<(b, a) are false.

In your initial case the comparison is false for all the rectangles between them, except precisely between the first two between which an order can be established given the comparison function.

Have you thought about using std::unordered_set redefining the compare function? In this case it would make more sense since you do not establish an order between rectangles but you want to know which ones have "equivalents".