寻找最佳匹配的算法，可能返回空值。

Question

我有一些可能暂时无法使用并且带有错误的输入。

struct sensorVal
{
    bool available;
    double error;
    double val;
    bool betterThan(const sensorVal* that) const;
}

我正在寻找一种算法，能够找到最佳的可用输入。我目前的最佳尝试是使用以下方式的min_element：

bool sensorVal::betterThan(const sensorVal& that) const
{
    if (available)
    {
        if (that.available)
            return (error < that.error);
        return true;
    }
    return false;
}

bool betterThan(const sensorVal& lhs, const sensorVal& rhs)
{
    return lhs.betterThan(rhs);
}

std::vector<sensorVal>::const_iterator 
find_best(const std::vector<sensorVal>& inputs)
{
    std::vector<sensorVal>::const_iterator best;

    best = min_element(inputs.begin(), inputs.end(), betterThan);

    if (best->available)
        return best;

    return inputs.end();
}

这段代码在所有输入都被标记为不可用时会出现问题。在这种情况下，最佳匹配应该设置为inputs.begin()，然后我需要测试它是否可用。

我希望将最佳匹配设为inputs.end()，我的代码已经考虑到了这一点。

是否存在可以找到最佳匹配并返回没有合适成员的现有算法？或者有没有一种重新表述我的测试的方法，使最佳匹配设置为inputs.end()。

谢谢

- DanS

---

这是一个情况，其中具有高阶函数（尤其是filter）将非常方便。然而，我在STL中找不到类似的东西。像remove-if这样的东西可能会有用。 - abeln

看起来你已经有可用的代码，只需要再检查一次。这真的是个问题吗？ - btilly

@btilly 是的，我有一个可行的方案。我想知道是否已经有现成的算法能够满足我的需求。 - DanS

Answer 1

也许你只是想让它看起来更好一些？

best = min_element(inputs.begin(), inputs.end(), betterThan);
return best->available ? best : inputs.end();

- dchhetri

Answer 2

你可以使用std::accumulate，但我认为你已经有的解决方案更好。

struct best {
  std::vector<sensorVal>::const_iterator end;

  explicit best(std::vector<sensorVal>::const_iterator end) : end(end){}

  std::vector<sensorVal>::const_iterator operator()(std::vector<sensorVal>::const_iterator l, std::vector<sensorVal>::const_iterator r) {
    return (r->available() && (l == end() || r->error < l->error)) ? r : l
  }

};

std::vector<sensorVal>::const_iterator 
find_best(const std::vector<sensorVal>& inputs)
{
  return std::accumulate(inputs.begin(), inputs.end(), inputs.end(), best(inputs.end());
}

- JoeG

---

谢谢。将函数对象构造函数声明为显式的，这被认为是良好的编程实践吗？ - DanS

除非你有非常充分的理由，否则将单参数构造函数显式声明为const是一种良好的实践方法，但在这个例子中并不重要。 - JoeG

Answer 3

也许你可以使用 std::partition() 将向量分为可用和不可用的输入，然后使用 min_element 在可用子集中找到最佳值。

- Jay