C++：選擇類w.r.t的向量上的argmax。任意表達式

Question

我描述我的問題，所以我就舉一個例子煩惱：我保持

class A{ 
    float a, b, c, d; 
} 

現在：

我有了一對夫婦在它的變量，例如類描述包含許多這些類的vector<A>。我經常需要做的是找到這個向量內的對象，以滿足其中一個參數是其他參數最大的w.r.t。即代碼看起來是這樣的：

int maxi=-1; 
float maxa=-1000; 
for(int i=0;i<vec.size();i++){ 
    res= vec[i].a; 
    if(res > maxa) { 
    maxa= res; 
    maxi=i; 
    } 
} 
return vec[maxi]; 

不過，有時我需要找到類最大a，有時最大b，有時最大0.8*a + 0.2*b類，有時我想最大a*VAR + b，其中VAR是一些變量被分配在前面等等。換句話說，我需要評估每個班級的表達，並採取max。我發現自己複製粘貼到處，只改變定義爲res的單行。

有沒有一些很好的方法來避免C++中的這種瘋狂？處理這個問題的最好方法是什麼？

謝謝！

Answer 1

template <typename F> 
struct CompareBy 
{ 
    bool operator()(const typename F::argument_type& x, 
        const typename F::argument_type& y) 
    { return f(x) < f(y); } 

    CompareBy(const F& f) : f(f) {} 

private: 
    F f; 
}; 


template <typename T, typename U> 
struct Member : std::unary_function<U, T> 
{ 
    Member(T U::*ptr) : ptr(ptr) {} 
    const T& operator()(const U& x) { return x.*ptr; } 

private: 
    T U::*ptr; 
}; 

template <typename F> 
CompareBy<F> by(const F& f) { return CompareBy<F>(f); } 

template <typename T, typename U> 
Member<T, U> mem_ptr(T U::*ptr) { return Member<T, U>(ptr); } 

您需要包括<functional>這個工作。現在使用，從頭部<algorithm>

std::max_element(v.begin(), v.end(), by(mem_ptr(&A::a))); 

或

double combination(A x) { return 0.2 * x.a + 0.8 * x.b; } 

和

std::max_element(v.begin(), v.end(), by(std::fun_ptr(combination))); 

甚至

struct combination : std::unary_function<A, double> 
{ 
    combination(double x, double y) : x(x), y(y) {} 
    double operator()(const A& u) { return x * u.a + y * u.b; } 

private: 
    double x, y; 
}; 

與

std::max_element(v.begin(), v.end(), by(combination(0.2, 0.8))); 

以便與a成員比較或通過a和b成員的線性組合進行比較。我將比較器分成兩部分，因爲mem_ptr這個東西非常有用，值得重用。 std::max_element的返回值是一個迭代器到最大值。您可以取消引用它以獲取最大元素，或者可以使用std::distance(v.begin(), i)來查找相應的索引（首先包括<iterator>）。

查看http://codepad.org/XQTx0vql的完整代碼。

Answer 2

您可以使用the std::max_element algorithm和自定義比較器。

如果您的編譯器支持lambda表達式，那麼編寫比較器很容易。

如果沒有，您可以編寫自定義比較函子。對於只是比較單個成員的簡單情況，你可以寫一個通用的「成員比較」函數對象，這將是這個樣子：

template <typename MemberPointer> 
struct member_comparator 
{ 
    MemberPointer p_; 

    member_comparator(MemberPointer p) : p_(p) { } 

    template <typename T> 
    bool operator()(const T& lhs, const T& rhs) const 
    { 
     return lhs.*p_ < rhs.*p_; 
    } 
}; 

template <typename MemberPointer> 
member_comparator<MemberPointer> make_member_comparator(MemberPointer p) 
{ 
    return member_comparator<MemberPointer>(p); 
} 

用作：

// returns an iterator to the element that has the maximum 'd' member: 
std::max_element(v.begin(), v.end(), make_member_comparator(&A::d)); 

Answer 3

這是什麼仿函數和STL是由爲：

// A class whose objects perform custom comparisons 
class my_comparator 
{ 
public: 
    explicit my_comparator(float c1, float c2) : c1(c1), c2(c2) {} 
    // std::max_element calls this on pairs of elements 
    bool operator() (const A &x, const A &y) const 
    { 
     return (x.a*c1 + x.b*c2) < (y.a*c1 + y.b*c2); 
    } 
private: 
    const float c1, c2; 
}; 


// Returns the "max" element in vec 
*std::max_element(vec.begin(), vec.end(), my_comparator(0.8,0.2)); 

Answer 4

您可以使用std::max_element STL算法每次提供自定義比較謂詞。

用的C++ 0x，你甚至可以使用lambda函數爲其最大簡潔：

auto maxElement=*std::max_element(vector.begin(), vector.end(), [](const A& Left, const A& Right) { 
    return (0.8*Left.a + 0.2*Left.b)<(0.8*Right.a + 0.2*Right.b); 
}); 

Answer 5

是表達總是線性的？你可以傳入四個係數的數組。如果你需要支持任意表達式，你需要一個函子，但如果它只是四個域的仿射組合，那麼就沒有必要這麼複雜。

Answer 6

使用max_element/min_element自定義函子的樣品

#include <algorithm> 
#include <iostream> 
#include <vector> 

using namespace std; 

struct A{ 
    float a, b, c, d; 
}; 


struct CompareA { 
    bool operator()(A const & Left, A const & Right) const { 
    return Left.a < Right.a; 
    } 
}; 


int main() { 
    vector<A> vec; 
    vec.resize(3); 
    vec[0].a = 1; 
    vec[1].a = 2; 
    vec[2].a = 1.5; 

    vector<A>::iterator it = std::max_element(vec.begin(), vec.end(), CompareA()); 
    cout << "Largest A: " << it->a << endl; 
    it = std::min_element(vec.begin(), vec.end(), CompareA()); 
    cout << "Smallest A: " << it->a << endl; 
} 

Answer 7

我知道這個線程是舊的，但我覺得它非常有用在C++中實現強大的argmax函數。

但是，據我所見，上面給出的所有示例都依賴於std :: max_element，它在元素之間進行比較（使用函子或通過調用運算符<）。如果每個元素的計算都很昂貴，這可能會很慢。它適用於排序數字和處理簡單的類，但如果函子更復雜呢？也許計算一個國際象棋位置的啓發式值或其他產生巨大樹木的東西等。

作爲線程啓動程序提到的真正的argmax只會計算一次argmax，然後將其保存爲與其他值進行比較。

編輯：好吧，我惱火，並有太多的空閒時間，所以我創建了一個< C++ 11和一個C++ 11版本的R值的引用，第一個C++ 11版：

#include <iostream> 
#include <algorithm> 
#include <iterator> 
#include <vector> 

template<typename IteratorT, typename HeuristicFunctorT> 
IteratorT argmax(IteratorT && it, const IteratorT & end, const HeuristicFunctorT & functor) { 
    IteratorT best(it++); 
    typename HeuristicFunctorT::result_type best_value(functor(*best)); 

    for(; it != end; ++it) { 
     typename HeuristicFunctorT::result_type value(functor(*it)); 

     if (value > best_value) { 
      best_value = value; 
      best = it; 
     } 
    } 

    return best; 
} 

template<typename IteratorT, typename HeuristicFunctorT> 
inline IteratorT argmax(const IteratorT & begin, const IteratorT & end, const HeuristicFunctorT & functor) { 
    return argmax(IteratorT(begin), end, functor); 
} 

class IntPairFunctor : public std::unary_function< std::pair<int, int>, int > { 
public: 
    int operator() (const std::pair<int, int> & v) const { 
     return v.first + v.second; 
    } 
}; 

std::pair<int, int> rand_pair() { 
    return std::make_pair(rand(), rand()); 
} 

int main(int argc, const char **argv) { 
    srand(time(NULL)); 

    std::vector< std::pair<int, int> > ints; 

    std::generate_n(std::back_insert_iterator< std::vector< std::pair<int, int> > >(ints), 1000, rand_pair); 

    std::vector< std::pair<int, int> >::iterator m (argmax(ints.begin(), ints.end(), IntPairFunctor())); 

    std::cout << std::endl << "argmax: " << *m << std::endl; 
} 

非C++ 11的版本要簡單得多，只有模板：

template<typename IteratorT, typename HeuristicFunctorT> 
IteratorT argmax(IteratorT it, const IteratorT & end, const HeuristicFunctorT & functor) { 
IteratorT best(it++); 
typename HeuristicFunctorT::result_type best_value(functor(*best)); 

for(; it != end; ++it) { 
    typename HeuristicFunctorT::result_type value(functor(*it)); 

    if (value > best_value) { 
     best_value = value; 
     best = it; 
    } 
} 

return best; 
} 

注意，無論是版本需要任何模板參數，唯一的要求是啓發式實現unary_function類