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

Question

假设给你一个 2D 点 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+)

初始值和范围的每个元素将被输入运算符，该运算符将返回以下类型的结果: 初始值将被输入到下一次调用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';
}

您可以将最小范数缓存在仿函数中以避免额外的计算(请注意:我正在使用有关 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;
}