Поиск минимального элемента на основе преобразованного значения

Вы можете использовать boost::range библиотеку.

auto reductionLambda = [](const Complex& a) { return calcReduction(a); };
auto it = boost::range::min_element(values | boost::adaptors::transformed( 
                             std::ref(reductionLambda));

Сами диапазоны также должны прийти к стандарту C++ с C++17.

Изменить

Как мы выяснили в комментариях, это также приведет к двойному преобразованию.

Итак, вот кое-что веселое:

#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/assign.hpp>
#include <algorithm>
#include <iostream>
#include <vector>
#include <functional>


template <class Iterator, class UnaryFunction>
class memoizing_transform_iterator
  : public boost::iterator_adaptor<
        memoizing_transform_iterator<Iterator, UnaryFunction> // Derived
      , Iterator                                              // Base
      , std::decay_t<decltype(std::declval<UnaryFunction>()(std::declval<typename Iterator::value_type>()))> // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
    >
{
 public:
    memoizing_transform_iterator() {}

    explicit memoizing_transform_iterator(Iterator iter, UnaryFunction f)
      : memoizing_transform_iterator::iterator_adaptor_(iter), fun(f) {}

    static int total;
 private:
    friend class boost::iterator_core_access;
    void increment() { ++this->base_reference(); memoized = false; }

    using MemoType = std::decay_t<decltype(std::declval<UnaryFunction>()(std::declval<typename Iterator::value_type>()))>;      

    MemoType& dereference() const 
    {
        if (!memoized) {
            ++total;
            memoized = true;
            memo = fun(*this->base());
        }
        return memo;
    }

    UnaryFunction fun;
    mutable bool memoized = false;
    mutable MemoType memo;
};


template <class Iterator, class UnaryFunction>
auto make_memoizing_transform_iterator(Iterator i, UnaryFunction&& f)
{
    return memoizing_transform_iterator<Iterator, UnaryFunction>(i, f);
}



template<class I, class U>
int memoizing_transform_iterator<I, U>::total = 0;


// THIS IS COPIED FROM LIBSTDC++
template<typename _ForwardIterator>
   _ForwardIterator
     min_el(_ForwardIterator __first, _ForwardIterator __last)
     {
       if (__first == __last)
     return __first;
       _ForwardIterator __result = __first;
       while (++__first != __last)
     if (*__first < *__result)
       __result = __first;
       return __result;
     }


int main(int argc, const char* argv[])
{
    using namespace boost::assign;

    std::vector<int> input;
    input += 2,3,4,1,5,6,7,8,9,10;


    auto transformLambda = [](const int& a) { return a*2; };


    auto begin_it = make_memoizing_transform_iterator(input.begin(), std::ref(transformLambda));
    auto end_it = make_memoizing_transform_iterator(input.end(), std::ref(transformLambda));
    std::cout << *min_el(begin_it, end_it).base() << "\n";

    std::cout <<begin_it.total;

    return 0;
}

По сути, я реализовал итератор, который запоминает результат вызова функтора преобразования. Странная часть, однако, заключается в том, что, по крайней мере, в онлайн-компиляторах итераторы копируются до того, как их разыменованные значения сравниваются (таким образом нарушая цель запоминания). Однако, когда я просто скопировал реализацию из libstdc++, она работает, как и ожидалось. Возможно, вы могли бы попробовать это на реальной машине? Живой пример находится здесь.

Небольшое редактирование: я тестировал на VS2015, и он работает, как и ожидалось, с std::min_element.

Не хватает только мета-итератора.

Метаитератор берет итератор и создает итератор, содержащий его копию. Он передает все операции содержащемуся итератору, за исключением случаев, когда разыменование вместо этого возвращает копию содержащегося итератора.

При всей осторожности код, используемый для этого, также работает для создания итератора над size_t или int или подобным торсор-нравится.

template<class It, class R>
struct reduced_t {
  It it;
  R r;
  friend bool operator<( reduced_t const& lhs, reduced_t const& rhs ) {
    return lhs.r < rhs.r;
  }
};
template<class It, class F>
reduced_t<It, std::result_of_t<F(typename std::iterator_traits<It>::reference)>>
reducer( It it, F&& f ) {
  return {it, std::forward<F>(f)(*it)};
}

template<class It, class F>
It reduce( It begin, It end, F&& f ) {
  if (begin==end)
    return begin;

  return std::accumulate(
    meta_iterator(std::next(begin)), meta_iterator(end),
    reducer(begin, f),
    [&](
      auto&& reduced, // reduced_t<blah...> in C++11
      It i
    ) {
      auto r2 = reducer( i, f );
      return (std::min)(reduced, r2);
    }
  ).it;
};

f(*it) вызывается ровно один раз для каждого итератора.

Я бы не назвал это... очевидным. Хитрость заключается в том, что мы используем accumulate и мета-итераторы для реализации min_element, тогда мы можем заставить accumulate работать с преобразованными элементами (которые вызываются один раз и возвращаются).

Вы можете переписать его в стиле программирования на основе стека, используя примитивы, но существует множество примитивов, которые нужно написать. Может быть, опубликовать ranges-v3.

На данный момент я представляю себе какую-нибудь мощную библиотеку композиционного программирования. Если бы я это сделал, мы могли бы сделать следующее:

reducer( X, f ) можно переписать graph( deref |then| f )(X), используя order_by( get_n_t<1> ) для упорядочивания.

Вызов accumulate может читаться как accumulate( skip_first(range), g(begin(range)), get_least( order_by( get_n_t<1> ) ) ).

Не уверен, что это яснее.

Вот решение с использованием (уже работает с библиотекой range-v3), реализация автором грядущего Ranges TS)

#include <range/v3/all.hpp>
#include <iostream>
#include <limits>

using namespace ranges::v3;

int main()
{
    auto const expensive = [](auto x) { static int n; std::cout << n++ << " "; return x; };
    auto const v = view::closed_iota(1,10) | view::transform(expensive); 

    auto const m1 = *min_element(v);
    std::cout << "\n" << m1 << "\n";

    auto const inf = std::numeric_limits<int>::max();    
    auto const min = [](auto x, auto y) { return std::min(x, y); };

    auto const m2 = accumulate(v, inf, min);
    std::cout << "\n" << m2 << "\n";    
}

Жить на Coliru с выводом :

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
1
19 20 21 22 23 24 25 26 27 28 
1

Как видите, при использовании min_element требуется 2N сравнений, а при использовании accumulate только N.

Если вы возьмете minElem в качестве лямбда-параметра, вы можете использовать min_element

Complex findMinValueWithPredicates(const std::vector<Complex>& values)
{
  float minElem = std::numeric_limits<float>::max();
  auto it = std::min_element(values.begin(), values.end(),
                             [&minElem](const Complex& a, const Complex& b) {
                               float tmp = calcReduction(a);
                               if (tmp < minElem) {
                                  minElem = tmp;
                                  return true;
                               }
                               return false;
                             });

  if (it == values.end()) throw std::runtime_error("");

  return *it;
}

Изменить: почему это работает, когда b не используется? 25.4.7.21 мин_элемент

21 Возвращает: первый итератор i в диапазоне [first,last), такой, что для каждого итератора j в диапазоне [first,last) выполняются следующие соответствующие условия: !(*j ‹ *i) или comp(*j, * и) == ложь. Возвращает последний, если первый == последний.

потому что b должно было называться smallestYet (код с сайта cplusplus.com)

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

Что привело меня к новой любимой цитате:

«В компьютерных науках есть только 10 сложных задач: недействительность кеша, присвоение имен и ошибки, связанные с ошибками на единицу».

• один прокомментировал, что мы можем ошибаться, поскольку мы не используем b.
• Я беспокоился, что кешированный minElem может быть неправильным.
• И я понял, что имя b должно было быть более значимым, так как это «разыменованный итератор до наименьшего элемента» или smallestYet.
• Наконец, не все понимают двоичный код, если он не пишется с «b» в конце.

Вот еще один вариант, но он по-прежнему является вашим вторым решением. Честно говоря, не очень понятно, но кому-то может понравиться. (Я использую std::pair<float, Complex> для сохранения результата сокращения и значения, которое было уменьшено.)

std::pair<float, Complex> result{std::numeric_limits<float>::max(), {}};
auto output_function = [&result](std::pair<float, Complex> candidate) {
    if (candidate.first < result.first)
        result = candidate;
};
std::transform(values.begin(), values.end(), 
               boost::make_function_output_iterator(output_function),
               [](Complex x) { return std::make_pair(calcReduction(x), x); });

P.S. Если ваш calcReduction стоит дорого, думали ли вы о кэшировании результатов в Complex объектах? Это приведет к немного более сложной реализации, но вы сможете использовать простой std::min_element, который сделает ваши намерения ясными.