How to define a comparison operator less than on vector-of-vector of doubles

Question

My question is basically the same as [1], but the challenge is to compare a nested vector<vector<double>>.

As a background to the problem I'm facing: I have an n-way index based on std::set where items are sorted by time primarily, and secondarily by geometry. That is, equal polygons should have the same index, but the actual order of them does actually not matter. What matters though is that the less-comparator must in this context be stable, in the sense that an item must be considered equal when it's neither less than nor greater than.

This vector<vector<double>> therefore represents polygons with optional holes (first vector is the outer ring, any subsequent vectors are holes).

[1] how to define a comparison operator (less than) on array of doubles?

Edit: This question is NOT about asking how to implement a less-than operator, but as the title suggests, about how to compare given vectors of vectors of double with another by using a less-than comparison… This is a whole lot more challenging…

The problem could be solved in different ways, but I specifically look for a solution which allows to use the object (geometry) as part of a set with multiple tied index properties.

Is your question how to create an `operator<` for `vector>`, or how to express the logic you mentioned? — Ranoiaetep, Nov 20 '22 at 01:51
The short answer is : I would NOT create an `operator<()` for a `vector>`, since the way you want to do it is almost certainly specific to one application (and you'll be in trouble if your application needs to do such a comparison in two distinct ways in two different sections of code). I would wrap the `vector>` as a `private` member of a class, and implement an `operator<()` for that class. The class can be named in a way that makes sense (e.g. so it is obvious why you want to check if one is less than another in your particular way). — Peter, Nov 20 '22 at 04:20
To add on @Peter's comment, if your goal was to make the object work with `` or `std::set`, think about if this is the definitive way to compare them, or if it is just how you want to order them. If it is the latter, then you should also consider passing a free function/lambda instead of defining the comparison operator for them. — Ranoiaetep, Nov 20 '22 at 05:27
Actually the comparator is already part of the (derived) geometry class. This question is not about architecture but the algorithm required to compare mentioned vectors. The actual application is quite more complex than described, I didn’t want to make it unnecessary complicated to follow. Items with same properties form a group within that set (5 properties in total), first sort is by e.g. time. The goal is as mentioned to index equal items into groups, for performance reasons a second lookup should be avoided (the < is required by the set). — benjist, Nov 21 '22 at 03:44
Please reopen, mentioned questions are not related and not helpful. — benjist, Nov 21 '22 at 12:35
It would be a good idea to not only describe your logic, but to also show some example input and output. — Ranoiaetep, Nov 22 '22 at 00:50

Caleth · Answer 1 · 2022-11-22T10:21:50.773

You could really do with some more types

struct Point
{
    double x;
    double y;
    double z; // ???
};

struct BasicPolygon
{
    std::vector<Point> shape;
};

struct Polygon
{
    BasicPolygon shell;
    std::vector<BasicPolygon> holes;
};

Start by =defaulting operator<=> for these types, and checking that cases we want to be equal are treated as equal.

At this point a polygon is equal to another if every point matches, in the same order. If you require that polygons differing only in the start vertex are treated as equal, things will be harder. If that's the case, I'd actually recommend a step where you canonicalize all your polygons to start at the lowest point.

void BasicPolygon::canonicalize()
{
    auto it = std::min_element(shape.begin(), shape.end());
    std::rotate(shape.begin(), it, shape.end());
}

void Polygon::canonicalize()
{
    shell.canonicalize();
    std::for_each(holes.begin(), holes.end(), std::mem_fn(&BasicPolygon::canonicalize));
}

If you can't mutate the geometry, you can find the canonical start point each time you compare, and do a sequence of std::lexicographic_compares. N.b. this is a different total order than canonicalizing first, because of the size check.

bool operator<(const BasicPolygon & lhs, const BasicPolygon & rhs)
{
    if (lhs.size() < rhs.size()) return true;
    if (rhs.size() < lhs.size()) return false;

    auto l_first = std::min_element(lhs.shape.begin(), lhs.shape.end());
    auto r_first = std::min_element(rhs.shape.begin(), rhs.shape.end());
    const auto l_last = l_first;
    const auto r_last = r_first;

    auto l_rem = std::distance(l_first, lhs.shape.end());
    auto r_rem = std::distance(r_first, rhs.shape.end());

    if (l_rem < r_rem)
    {
        if (std::lexicographic_compare(l_first, lhs.shape.end(), r_first, r_first + l_rem)) return true;
        if (std::lexicographic_compare(r_first, r_first + l_rem, l_first, lhs.shape.end()) return false;

        r_first += l_rem;
        r_rem -= l_rem;
        l_first = lhs.shape.begin();

        if (std::lexicographic_compare(l_first, l_first + r_rem, r_first, rhs.shape.end()) return true;
        if (std::lexicographic_compare(r_first, rhs.shape.end(), l_first, l_first + r_rem)) return false;

        l_first += r_rem;
        r_first = rhs.shape.begin();

        if (std::lexicographic_compare(l_first, l_last, r_first, r_last)) return true;
        if (std::lexicographic_compare(r_first, r_last, l_first, l_last) return false;
    } else {
        if (std::lexicographic_compare(l_first, l_first + r_rem, r_first, rhs.shape.end()) return true;
        if (std::lexicographic_compare(r_first, rhs.shape.end(), l_first, l_first + r_rem)) return false;

        l_first += r_rem;
        l_rem -= r_rem;
        r_first = rhs.shape.begin();

        if (std::lexicographic_compare(l_first, lhs.shape.end(), r_first, r_first + l_rem)) return true;
        if (std::lexicographic_compare(r_first, r_first + l_rem, l_first, lhs.shape.end()) return false;

        r_first += l_rem;
        l_first = lhs.shape.begin();

        if (std::lexicographic_compare(l_first, l_last, r_first, r_last)) return true;
        if (std::lexicographic_compare(r_first, r_last, l_first, l_last) return false;
    }
    return false;
}

score -2 · Answer 2 · answered Nov 20 '22 at 02:58

-2

All you need to do is to create a free function operator< that takes two vector<vector<double>> as const&:

bool operator< (const vector<vector<double>& l, const vector<vector<double>& r)
{
    // your comparison logic here...
}

answered Nov 20 '22 at 02:58

Ranoiaetep

5,872
1
14
39

1

I know how to implement the operator… that’s done already. The actual comparison logic for given problem is required, handling handling the comparison between an arbitrary number of vects with arbitrary number of double with another. – benjist Nov 21 '22 at 03:48
@benjist That's why I specifically asked you whether your question was how to create the operator. – Ranoiaetep Nov 22 '22 at 00:50

How to define a comparison operator less than on vector-of-vector of doubles

2 Answers2