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

Question

假设给定一个二维点 vector ，并期望找到具有最少 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评价。 (至少如果使用 this possible implementation)

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

注意事项:

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

Answer 1

您可以使用 std::accumulate(在 algorithm header 中):

累积接收:

• 范围
• 初始值
• 二元运算符(可选，不传则调用operator+)

初始值和range的每个元素将被送入运算符，运算符将返回类型为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';
}

您可以将 minimum norm 缓存在 functor 中以避免额外的计算(请注意:我正在使用有关 std::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;
}