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

Question

I'm implementing a cache to save function calls.

Let's say I have 2 doubleparameters to my function call.

Those must be the key of some LRU cache or - to make it simpler - a C++ std::map.

So I created a template class with the array inside (variable number of values)

template <int n>
  class DoubleArray
  {
    public:   
    double array[n];
   };

When trying to use that as a key of my std::map, the compiler complained because it needed a operator< for those.

.....\include\c++\7.3.1\bits\stl_function.h:386:20: note:
'const DoubleArray<2>' is not derived from 'const std::map<_Key, _Tp, _Compare,
_Alloc>'
       { return __x < __y; }
                ~~~~^~~~~

So I implemented a comparison operator (well, I though that hashing could do the trick but it doesn't seem so...) and it compiled:

#include <map>

template <int n>
  class DoubleArray
  {
    public:   
    double array[n];
    bool operator<(const DoubleArray &other) const
    {      
      return (array[0] < other.array[0]) || (array[0] == other.array[0] && array[1] < other.array[1]);
    }

  };

int main()
{
   std::map<DoubleArray<2>,double> my_cache;
   DoubleArray<2> params;
   // clumsy way to initialize the array...
   params.array[0] = 12;
   params.array[1] = 2;
   // put a value in cache
   my_cache[params] = 23;
}

Note that the comparison operator is really clumsy. What if I have 6 parameters (which is my real case).

How to create a generic comparison operator (maybe using template recursion) ?

In case this is a XY problem, is there a simpler way to create a n-value key map with double types?

(note that I'm fully aware that using double values as keys looks bad, but my goal is to cache values on function calls where the parameters are exactly the same, those are not intended to be stored or such)

Any reason you are not using [`std::array`](https://en.cppreference.com/w/cpp/container/array)? It has all of the relational operators defined for you. — NathanOliver, Dec 05 '18 at 17:24
`n-value key map with double types` -- Using `doubles` in any way as key values is dodgy. Doubles are not exact, and neither will be your keys. Your program may run differently using the exact same data if the code is built using different options, or run on a different version of the compiler, etc. — PaulMcKenzie, Dec 05 '18 at 17:31
@PaulMcKenzie double _are_ exact for those who understand them. — YSC, Dec 05 '18 at 17:34
@YSC Yes, but just to let the OP know some of the consequences of using `double` as a key. — PaulMcKenzie, Dec 05 '18 at 17:36
@PaulMcKenzie this looks like memoising calls to a `double function(double, double)`, in which case exact matches are much more plausible — Caleth, Dec 05 '18 at 17:36
Yes, but again, if the OP sees that a certain calculation is not being cached, it could be the `double` that is produced as the key isn't matching exactly with what is currently in the map. — PaulMcKenzie, Dec 05 '18 at 17:38
@OP *where the parameters are exactly the same* -- Floating point will surprise you. Values that seem to be the same sometimes are internally different. Basically look out for that odd value that never seems to be cached. — PaulMcKenzie, Dec 05 '18 at 17:43
@PaulMcKenzie I am well aware of that. I should have picked `int` for my example. — Jean-François Fabre, Dec 05 '18 at 17:45

score 8 · Answer 1 · answered Dec 05 '18 at 17:29

8

You are looking for std::lexicographical_compare

bool operator<(const DoubleArray &other) const
{      
    return std::lexicographical_compare(array, array + n, other.array, other.array + n);
}

Alternatively, you can just define an alias to std::array, which already has all the comparison operators defined

template<int n>
using DoubleArray = std::array<double, n>;

answered Dec 05 '18 at 17:29

Caleth

52,200
2
44
75

I was here to urge OP to use `std::array`. +1 – YSC Dec 05 '18 at 17:33

score 4 · Accepted Answer · answered Dec 05 '18 at 17:34

You can sidestep the issue by using std::array. Using an alias declaration your code could be simplified to

template <std::size_t N>
using DoubleArray = std::array<double, N>;

int main()
{
   std::map<DoubleArray<2>,double> my_cache;
   my_cache[{12, 2}] = 23;
}

K. Kiryu · Answer 3 · 2018-12-06T09:43:43.037

How to create a generic comparison operator (maybe using template recursion) ?

You can try this method:

#include <utility>     // std::index_sequence
#include <tuple>       // std::tie

template <int N>
struct DoubleArray
{
private:
    template <size_t ... Is>
    bool opHelper(const DoubleArray& rhs, std::index_sequence<Is...>) const
    {
        return std::tie(arr[Is]...) < std::tie(rhs.arr[Is]...);
    }

public:
    double arr[N];

    bool operator<(const DoubleArray& rhs) const
    {
        return opHelper(rhs, std::make_index_sequence<N>{});
    }
};

score 2 · Answer 4 · answered Dec 05 '18 at 17:43

Don't reinvent the wheel, use std::array. It already has an overloaded operator<. Always consider using and combining what the standard library and other well known libraries offers before writing your own custom solution: Use libraries whenever possible.

You may then declare your map like this:

std::map<std::array<double, 2>, double> my_cache;

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

4 Answers4

Linked