Saving function evaluations while using std::min_element()

Question

Suppose you are given a vector of 2D points and are expected to find the point with the least Euclidean norm.

The points are provided as std::vector<point_t> points whith the following typedef std::pair<double, double> point_t. The norm can be calculated using

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

Writing the loop myself I would do the following:

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;
    }
}

But one should use STL algorithms instead of wirting one's own loops, so I'm tempted to to the following:

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

But there is a caveat: if n = points.size() then the first implementation needs n evaluations of norm(), but the second implementation needs 2n-2 evaluations. (at least if this possible implementation is used)

So my question is if there exists any STL algorithm with which I can find that point but with only n evaluations of norm()?

Notes:

• I am aware that big-Oh complexity is the same, but still the latter will lead to twice as many evaluations
• Creating a separate vector and populating it with the distances seems a bit overkill just to enable the usage of an STL algorithm - different opinions on that?
• edit: I actually need an iterator to that vector element to erase that point.

Answer 1

You could use std::accumulate (in the algorithm header):

Accumulate receive:

• range
• initial value
• binary operator (optional, if not passed, operator+ would be called)

The initial value and every element of the range would be feed into the operator, the operator would return a result of the type of the initial value that would be feed into the next call to operator with the next element of the range and so on.

Example Code (Tested GCC 4.9.0 with C++11):

#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';
}

You could cache the minimum norm in the functor for avoid extra calculation (be aware: I'm using info about the implementation of std::min_element). The second element is the smallest found and the first is the iteration 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;
}

Answer 2

This is the sort of problem that boost::transform_iterator from the boost iterator library is designed to solve. There are limitations with the decorated iterator approach however and the C++ standards committee Ranges working group is looking into adding ranges to the standard which would potentially allow for a more functional approach of piping e.g. a transform to a min_element without needing temporary storage.

Eric Niebler has some interesting posts on ranges at his blog.

Unfortunately transform_iterator doesn't quite solve your problem given the way min_element is typically implemented - both iterators are dereferenced for each comparison so your function will still end up getting called more often than necessary. You could use the boost iterator_adaptor to implement something like a 'caching_transform_iterator' which avoids recomputing on each dereference but it would probably be overkill for something like norm(). It might be a useful technique if you had a more expensive computation though.

Answer 3

EDIT: Nevermind this, I misread the question.

I think you are mistaken in your assumption that min_element will perform 2N-2 comparisons

Per the c++ reference of min_element you can see that the algorithm performs essentially N comparison, which is the minimum for an unsorted array.

Here is a copy for the (very) unlikely case that www.cplusplus.com ever fails.

template <class ForwardIterator>
  ForwardIterator min_element ( ForwardIterator first, ForwardIterator last )
{
  if (first==last) return last;
  ForwardIterator smallest = first;

  while (++first!=last)
    if (*first<*smallest)    // or: if (comp(*first,*smallest)) for version (2)
      smallest=first;
  return smallest;
}