根据转换后的值查找最小元素

Question

以下是代码审查中发现的任务.我想根据特殊类型的比较谓词从集合中选择最小值.像这样:

struct Complex { ... };

float calcReduction(Complex elem);

Complex findMinValueWithPredicates(const std::vector<Complex>& values)
{
  auto it = std::min_element(values.begin(), values.end(), 
                             [](const Complex& a, const Complex& b) { 
                               return calcReduction(a) < calcReduction(b); 
                             });

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

  return *it;
}

在这里,我找到了基于谓词的最小元素.此谓词计算两个值的减少,float然后比较这些浮点数.工作正常,看起来整洁.

你能看到问题吗？是的,对于一组N元素calcReduction()称为2N时间,而它只足以计算它N- 每个元素一次.

解决此问题的一种方法是编写显式计算:

Complex findMinValueExplicit(const std::vector<Complex>& values)
{
  float minReduction = std::numeric_limits<float>::max();
  Complex minValue;

  for (Complex value : values)
  {
    float reduction = calcReduction(value);
    if (reduction < minReduction)
    {
      minReduction = reduction;
      minValue = value;
    }
  }

  if (minReduction == std::numeric_limits<float>::max()) throw std::runtime_error("");

  return minValue;
}

它工作正常,我们只有N电话calcReduction().然而,与显式调用相比,它看起来过于冗长,并且意图并不那么明确min_element.因为当你打电话min_element时很容易猜到你会找到一个最小元素,你知道.

我现在唯一的想法就是创建我自己的算法,比如min_element_with_reduction接受范围和缩小功能.听起来很合理,但我想知道是否有任何现成的解决方案.

有关如何以明确的意图和一些现成解决方案解决此任务的任何想法？欢迎提升.C++ 17和范围很有趣.

Answer 1

你可以使用boost::range 库.

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

范围本身也应该使用C++ 17来标准C++.

编辑

正如我们在评论中指出的那样,这也会使转换成两次.

所以这里有趣:

#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.