3

でstd::vector<unsigned int>、特定の数より小さい最大数の要素の位置を見つけたいです。例えば：

v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

8 より小さい最大の数を見つけたいと思います。その数は 7 です。

次のコードは正しくありませんが、それはおそらく私が取得したいものです。

std::vector<unsigned int>::iterator pnt = std::find_if (v.begin(), v.end(), [](const unsigned int& x) { return x < 8; && x == MAX; });
4

2 に答える 2

6

ベクトルが常にソートされている場合は、対数の複雑さで実行できます

auto it = std::lower_bound(v.begin(), v.end(), 8); // first value >= 8
auto m = *((it != v.begin())? --it : it);

ベクトルがソートされていないが、変更できる場合は、2 つの手順で実行できます。

auto it = std::partition(v.begin(), v.end(), [](int x) { x < 8 });
auto m = *(it != v.begin())? std::max_element(v.begin(), it) : it);

ベクトルを変更できない場合は、手動で変更できます

auto max = 0;
for (elem: v) {
   if (elem < 8) 
       m = std::max(elem, m);
}
// m is now the max of all elements < 8

最後の 2 つのアプローチはどちらも線形の複雑さを持ちます。後者は、Boost.Iteratorライブラリのfilter_iteratorを使用して一般化できますが、テンプレートの土地にすでに深く入っているため、そのような魔法が繰り返し必要になる場合にのみ行ってください。

于 2013-07-17T21:12:37.447 に答える
0

ベクトル内に値があるかどうかをチェックする関数を作成し、そうでない場合はエラーをスローします。次に、遭遇した最大値よりも低いが、現在見つかった最大値よりも高いすべての値を保存します。これが私がそれを実装する方法です。

unsigned smaller_than ( const std::vector<unsigned int>& v, unsigned max) {

    bool intial_found = false;
    unsigned largest;
    unsigned i;
    for ( i = 0; i < v.size() ;++i){
        if ( v [i] < max ){
            largest = v[i];
            intial_found = true;
            break;
        }
    }
    if ( ! intial_found ) {
        throw "oops";/*of course you make a Nice std::exception for this case*/
    }
    for (  ; i < v.size(); i++ ) {
        if ( v[i] < max && v [i] > largest){
            largest = v[i];
        }
    }
    return largest;
}
于 2013-07-17T21:23:12.857 に答える