这是从代码审查到我的任务.我想根据一种特殊的比较谓词从一个集合中选择一个最小值.喜欢这个：
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;
}
这里我找到基于谓词的最小元素.该谓词计算两个值的缩小以浮动,然后比较这些浮点数.工作正常,看起来整齐.
你能看到问题吗？是的,对于一组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,接受范围和缩小功能.听起来很合理,但我不知道是否有任何现成的解决方案.
解决方法
您可以使用boost :: range
library.
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复制实现时,它的工作原理如下.也许你可以在真实的机器上尝试一下？实例是here.
小编：我在VS2015测试,它的工作原理与std :: min_element.
