C++で他のすべての組み合わせの最大値に合計する2つのベクトル配列の組み合わせを見つける

Question

1つの要素が1つのベクトル配列から取得され、他の要素が2番目のベクトル配列から取得される最大合計のペアを見つけるには：hereこれは、出力配列のサイズが制限を超え、中止が呼び出されると、v1とv2のサイズが両方とも100000になったときに失敗します。

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <iterator> 
typedef int T; 
struct Fctor 
{ 
    typedef std::vector<T>::iterator Iterator; 
    Iterator it1, it2, begin, end; 
    Fctor(Iterator begin1, Iterator end1, Iterator begin2) 
    { 
     begin = begin1; 
     end = end1; 
     it1 = begin1; 
     it2 = begin2; 
    } 
    T operator()() 
    { 
     // T result = f(*it1, *it2); 
     T result = (*it1) * (*it2); 
     if(++it1 != end) return result; 
     it1 = begin; 
     ++it2; 
     return result; 
    } 
}; 

int main() 
{ 
    std::vector<T> v1; v1.push_back(1); v1.push_back(2); 
    std::vector<T> v2; v2.push_back(3); v2.push_back(4); v2.push_back(5); 
    std::vector<T> result(v1.size() * v2.size()); 
    Fctor fctor(v2.begin(), v2.end(), v1.begin()); 
    generate(result.begin(), result.end(), fctor); 
    std::copy(result.begin(), result.end(), 
     std::ostream_iterator<T>(std::cout, " ")); 
    std::cout << std::endl; 
    // => 3 4 5 6 8 10 
} 

Answer 1

最大合計ペアは、各ベクトルからの最大値の合計にすぎません。すべての組み合わせまたは一時的なベクトルを生成する必要はありません。ここでは、標準ライブラリアルゴリズムを使用した非常に単純なO（n）実装を示します。

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

int main() 
{ 
    std::vector<int> v1{ 1,2 }; 
    std::vector<int> v2{ 3,4,5 }; 

    int max1 = *std::max_element(v1.begin(), v1.end()); 
    int max2 = *std::max_element(v2.begin(), v2.end()); 

    std::cout << "max sum = " << (max1 + max2) << '\n'; 
} 

// max sum = 7