c++ - 用于查找 f(Xi) 最小值的索引的标准或增强算法

Question

我的问题如下：给定一个容器 X = {x ₁ , x ₂ , ...,x _n } 和一个 function ，找到f(x _i ) 达到最小值f的索引。i

当然，我可以从头开始实现它，但我有一种我发明了自行车的感觉，所以我正在寻找使用标准或增强算法的更短代码。我能得到的最好的是

template <typename Val>
Val f(Val)
{
.........
}

template <typename It>
It find_minimum(It begin, It end)
{
return std::min_element(begin, end, 
   [](typename It::value_type val1, typename It::value_type val2)
  {
  return f(val1) < f(val2);
  });
}

但它存在f被评估 2N-1 次的问题。

Answer 1

就用这个算法（伪代码，没时间让模板正确）

It element= X.first()
Val min = f(element)
It min_el = element
while(element= element.next())
{
    Val temp = f(element);
    if( min > temp)
    {
        min_el = element;
        min = temp;
    }
}
return min_el

Answer 2

我能找到的简短答案使用 std::min_element 和 boost::transform_iterator：

return std::min_element(
  boost::make_transform_iterator(begin, f), 
  boost::make_transform_iterator(end, f)).base();

但是，它可能需要 2N-1 次函数调用，具体取决于 std::min_element 实现。

Answer 3

如果你知道 std::min_element 的实现，你可以使用带有状态的lambda

auto minElt = std::min_element(data.begin(), data.end(), [f](const int& a, const int& b)->bool
                               {
                                   static int minValCash = f(b);
                                   int v2 = f(a);
                                   bool result = v2 < minValCash;
                                   if(!result)
                                    std::swap(v2, minValCash);
                                   return result;
                               });

Answer 4

如何使用一个额外的步骤来计算和存储 all f(x)，然后寻找最小值？

另一种想法：迭代所有可能的 x 值并仅存储先前的最小值？