使用 std::min_element() 时保存函数计算

假设给你一个 2D 点向量，并期望找到最少的点欧几里得范数 http://en.wikipedia.org/wiki/Norm_%28mathematics%29#Euclidean_norm.

点提供为std::vector<point_t> points与以下typedef std::pair<double, double> point_t。范数可以使用以下公式计算

double norm(point_t p)
{
    return pow(p.first, 2) + pow(p.second, 2);
}

我自己编写循环我会执行以下操作：

auto leastPoint = points.cend();
auto leastNorm = std::numeric_limits<double>::max();
for (auto iter = points.cbegin(), end = points.cend(); iter != end; ++iter)
{
    double const currentNorm = norm(*iter);
    if (currentNorm < leastNorm)
    {
        leastNorm = currentNorm;
        leastPoint = iter;
    }
}

但是人们应该使用 STL 算法而不是编写自己的循环，所以我很想这样做：

auto const leastPoint = std::min_element(points.cbegin(), points.cend(),
    [](point_t const lhs, point_t const rhs){ return norm(lhs) < norm(rhs); });

但有一个警告：如果n = points.size()那么第一个实现需要n的评价norm()，但是第二次实现需要2n-2评价。 （至少如果这个可能的实施 http://en.cppreference.com/w/cpp/algorithm/min_element用来）

所以我的问题是是否存在任何 STL 算法可以让我找到那个点，但只需要n的评价norm()?

Notes:

• 我知道 big-Oh 复杂度是相同的，但后者仍然会导致两倍的评估
• 创建一个单独的向量并用距离填充它似乎有点矫枉过正，只是为了启用 STL 算法 - 对此有不同的看法吗？
• 编辑：我实际上需要一个该向量元素的迭代器来删除该点。

你可以使用std::accumulate（在里面algorithm标题）：

累计收到：

• range
• initial value
• binary operator（可选，如果没有通过，operator+会被称为）

The initial value以及其中的每一个元素range将被馈送到operator，该运算符将返回该类型的结果initial value这将被输入到下一个调用中operator与范围的下一个元素等等。

示例代码（使用 C++11 测试 GCC 4.9.0）：

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

typedef std::pair<double, double> point_t;

struct norm_t {
    point_t p;
    double norm;
};

double norm(const point_t& p) {
    return std::pow(p.first, 2) + std::pow(p.second, 2);
}

norm_t min_norm(const norm_t& x, const point_t& y) {
    double ny = norm(y);
    if (ny < x.norm)
        return {y, ny};
    return x;
}

int main() {
    std::vector<point_t> v{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10}};

    norm_t first_norm{v[0], norm(v[0])};
    auto min_norm_point =
        std::accumulate(v.begin(), v.end(), first_norm, min_norm);

    std::cout << "(" << min_norm_point.p.first << "," << min_norm_point.p.second
              << "): " << min_norm_point.norm << '\n';
}

你可以缓存最低标准 in the functor为了避免额外的计算（请注意：我正在使用有关实施的信息std::min_element http://en.cppreference.com/w/cpp/algorithm/min_element）。第二个元素是发现的最小的第一个是迭代元素。

struct minimum_norm {
    minimum_norm() : cached_norm(-1) {}
    bool operator()(const point_t& first, const point_t& second) {
        if (cached_norm == -1)
            cached_norm = norm(second);
        double norm_first = norm(first);
        if (norm_first < cached_norm) {
            cached_norm = norm_first;
            return true;
        }
        return false;
    }
private:
    double cached_norm;
};

int main()
{
    std::vector<point_t> v{{3, 4}, {5, 6}, {1, 2}, {7, 8}, {9, 10}};

    auto result = std::min_element(std::begin(v), std::end(v), minimum_norm());
    std::cout << "min element at: " << std::distance(std::begin(v), result) << std::endl;
}