c++ - 对惰性计算决胜元素的 vector 进行排序

Question

我想按主要字段对结构 vector 进行排序，并使用次要字段作为决胜局。正常的方式是这样的:

struct element {
  int primary;
  int secondary;
};

bool comparator(const element& e1, const element& e2) {
  if (e1.primary != e2.primary) {
    return e1.primary < e2.primary;
  }
  return e1.secondary < e2.secondary;
}

但二级数据的计算成本很高。因为只有当主值相等时才需要它，所以我想懒惰地计算它。

似乎我唯一可以进行这种懒惰评估的地方就是比较器本身。像这样的东西:

bool comparator(const element& e1, const element& e2) {
  if (e1.primary != e2.primary) {
    return e1.primary < e2.primary;
  }

  return e1.computeSecondary() < e2.computeSecondary();
}

虽然这将避免在主要值不同的情况下评估次要值，但每次与另一个元素进行比较时，最终都会重新计算同一元素的次要值。我要排序的数据是长尾数据，例如 30% 的值等于 1，20% 等于 2，5% 等于 3，较低的 % 表示较高的值。因此，在相当多的情况下，次要元素将被计算，并且不存储计算值可能会导致它们被重新计算太多次。

因此，我希望每个元素最多评估一次次要值。但是比较器采用 const ref 参数，因此它不能修改元素的次要值。如何实现？

Answer 1

简而言之，可能的选择是。

1. 声明secondary可变的。
2. 使用const_cast在comparator .
3. 使用const_cast在computeSecondary .
4. 创建一个简单的 Lazy保存一个值或一个 thunk 的模板类，当被要求时，如果尚未评估并报告结果(或立即报告结果，如果已知)，则在内部强制执行一个值，不会花费很长时间;并声明secondary自类型 Lazy<int> .
5. 或者更确切地说，不要重新发明轮子并使用std::future这实际上是非常惰性的模板(在一种情况下)。
6. 或者其他任何事情，人们可以创造更多的方法。