如何在双精度数组上定义比较运算符（小于）？

Question

我正在实现一个缓存以保存函数调用。

假设我有两个 `double` 参数传递给我的函数调用。

这些参数必须是某个 LRU 缓存的键，或者 - 为了简化 - 一个 C++ 的 `std::map`。

因此，我创建了一个带有数组的模板类 (值的数量可变)。

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

当我试图将其用作std::map的键时，编译器报错，因为它需要这些内容的operator<。

.....\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; }
                ~~~~^~~~~

我实现了一个比较操作符（当时认为哈希可以解决问题，但似乎不行...），它已经编译成功：

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

请注意，比较运算符非常笨拙。如果我有6个参数（这是我的实际情况），该怎么办？

如何创建一个通用的比较运算符（可能使用模板递归）？

如果这是XY问题，是否有一种更简单的方法来创建一个带有double类型的n值键映射？

（请注意，我完全意识到使用double值作为键看起来很糟糕，但我的目标是在函数调用上缓存值，其中参数完全相同，这些值不打算被存储或类似）

- Jean-François Fabre

---

为什么你没有使用std::array？它已经为你定义了所有的关系运算符。 - NathanOliver

n-value key map with double types -- 在任何情况下使用doubles作为键值都是不可靠的。双精度浮点数并不是精确的，因此你的键也不会是精确的。如果代码使用不同的选项构建或在不同版本的编译器上运行，则即使使用相同的数据，你的程序也可能会以不同的方式运行。 - PaulMcKenzie

@PaulMcKenzie 这看起来像是对 double function(double, double) 进行记忆化调用，这种情况下精确匹配更加可信。 - Caleth

是的，但是如果 OP 发现某个计算结果没有被缓存，可能是由于生成的 double 作为键与当前映射中的内容不完全匹配。 - PaulMcKenzie

@OP 参数完全相同 -- 浮点数会让你惊讶。有时候看起来相同的值在内部是不同的。基本上要注意那些似乎永远无法缓存的奇怪值。 - PaulMcKenzie

Answer 1

您正在寻找std::lexicographical_compare函数。

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

或者，您可以仅定义别名到std::array，它已经定义了所有比较运算符。

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

- Caleth

---

我在这里敦促 OP 使用 std::array。+1 - YSC

Answer 2

您可以通过使用 std::array 来避免这个问题。使用别名声明，您的代码可以简化为：

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

- NathanOliver

Answer 3

如何创建一个通用的比较运算符（可能使用模板递归）？

您可以尝试以下方法：

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

- K. Kiryu

Answer 4

不要重复造轮子，使用std::array。它已经有了重载运算符<。在编写自己的自定义解决方案之前，请始终考虑使用和组合标准库和其他知名库所提供的内容：尽可能使用库。然后，您可以像这样声明您的映射：

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

- Julien Villemure-Fréchette