How to define less than (<) operator or std::less struct for Eigen::Vector3f?

Question

I want to create a map of indices to vertices:

using IndicesToVertices = std::map<Eigen::Vector3f, uint32_t>;

But operator< is not defined for Eigen::Vector3f. I don't want to mess with the class itself, so I cannot declare a friend operator< for it, which seems recommended for custom "owned" types.

I have tried to derive a type from it, which only added the operator< as its member, but encountered problems, when the derived type needed to interact with other Eigen classes (e.g. Eigen::AngleAxisf() - when multiplying it by Eigen::Vector3f and adding the result to Eigen::Vector3f). Eigen::Vector3f is a template specialization and these other types as well. There seem to be some complex things happening, which prevent easy derivation from these types, with hope that it will work with other - not derived types.

Then I have looked at other possibilities, like specializing a template for std::less (Using std::map with Eigen 3)

namespace std {
template<>
    struct std::less<Vec3>
    {
        bool operator() (const Vec3& a, const Vec3& b) const
        {
           return std::lexicographical_compare(a.begin(), a.end(), b.begin(),  b.end());
        }
    };
}

This is not recommended "here and there" (e.g Specialization of 'template<class _Tp> struct std::less' in different namespace) and - more importantly for me - doesn't compile, throwing strange errors, which I don't understand, like: https://learn.microsoft.com/en-us/cpp/error-messages/compiler-errors-2/compiler-error-c3848?view=msvc-160

I may be left with declaring IndicesToVertices with custom comparator function, which specializes std::map, . Is this the best way? If so, how to do it properly?

It would be nice if the answer included reasoning about the possible issues due to to fact, that it is not safe to compare floats, which happens under the hood in std::lexicographical_compare or other implementations. Then, when trying to remap indices for a subset of vertices form the map - is it possible, that "bad things" can happen?

the function doesn't have to be called < or less to be used in a map... Yes, do use a custom comparator. Rename your `less` to mycomparator, and use that as template parameter for map. You may want to add `const` to the operator. — Marc Glisse, Jul 09 '21 at 18:56
Occams Razor, kind-of: You ruled out various approaches so the one that remains is the solution. — Ulrich Eckhardt, Jul 09 '21 at 19:00

Yakk - Adam Nevraumont · Accepted Answer · 2021-07-09T21:02:03.563

It is generally a really bad idea to use floating point values (or aggregates) as keys into a map.

That is a fundamental design issue. I mean, if there is a NaN, everything explodes. And two seemingly identical derivations of a floating point value can compare unequal.

But it isn't hard to write a comparison operator.

struct LexographicLess {
  template<class T>
  bool operator()(T const& lhs, T const& rhs) const {
    return std::lexographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
  }
};

then simply do:

std::map<Eigen::Vector3f, uint32_t, LexographicLess>;

we can fix the "NaN" issue:

template<class L=std::less<>>
struct LexographicLess {
  template<class T>
  bool operator()(T const& lhs, T const& rhs) const {
    return std::lexographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), L{});
  }
};

which lets us pass in a "sub-less", which we can harden against NaN issues.

Doing this right will depend on the framework of your problem. Does your space have to support locations that vary from layout of gates on a integrated circuit all the way to locations light years away? If not, you could reconsider using floating point values.

Second, spacial mapping using a one-dimensional ordered map like std::map is often a bad idea. Learn what a Quad and Octtree are, which organize things in 2 or 3 dimensions so that nearby things are nearby in the data structure.

The question "what are the values of this function near this coordinate" is far more sensible to ask of a continuum approximation (like 3 dimensional floats) than "what is the value stored for this exact point", which is near nonsense on a continuum, and doesn't work well in a floating point continuum approximation.

But that is far, far out of scope.

Actually this IS within the scope of my interests. I am trying to have unique vertices in a STL model for a 3d printer slicer. And operate on some subsets of the whole model. There, at GCode level, we are at sub-mm precision. So some values may be quite close to each other. Your remark about Quad and Octtre may be very enligtening! Thank You Yakk :) — forestgril, Jul 09 '21 at 19:18
@forestgril I said "integrated circuit" and "light years" and I mean it. A 32 bit value can handle μm precision on objects 1 km in size as a fixed point value. A 64 bit fixed point value can handle nm precision on objects larger than the Earth-Moon system. I doubt your printer needs that much precision, or is printing out values larger than that. But that is a side issue. — Yakk - Adam Nevraumont, Jul 09 '21 at 19:22
I know, I am using floats, which give me circa 5-6 precision digits. Prints are usually withing that range: from 1 m to 0.001 mm - this already is 6 digits - at the limit of precision. But the issues that worry me most at the moment is something else. That some detailed 3d model surfaces (polyhedrons) may contain almost/degenerate vertices (e.g at tips of high curvatures etc). Then when I map these, the mapping will depend on floating point endings of the numbers. When I search again for a certain vertex, I may find it with a different index due to this. — forestgril, Jul 09 '21 at 19:32
BTW, it should be "std::lexicographical_compare" and without <0 at the return point. — forestgril, Jul 09 '21 at 20:30

How to define less than (<) operator or std::less struct for Eigen::Vector3f?

1 Answers1