4

並べ替えられたベクトルの配列がありますが、

vector< int> b[1000009];

ここで、行 b[factor] で x と y の間の範囲を検索する必要があります。
'factor'、'x'、'y' はすべて整数です。
私は次のアプローチを使用しました：

        int lb,ub;
        if(b[factor][0]>=x){lb=0;}
        else
            {
                lb=upper_bound(b[factor].begin(),b[factor].end(),x)-b[factor].begin();
                while(b[factor][lb-1]>=x)lb--;
            }
        if(b[factor][sz2-1]<=y)
            {
                ub=sz2-1;
            }
        else {
                ub=lower_bound(b[factor].begin(),b[factor].end(),y)-b[factor].begin();
                while(b[factor][ub]>y)ub--;
            }

しかし、このアプローチでは常に正しい答えが得られるわけではありません。それに加えて、同じことを達成するためにいくつかのコンパレータ関数を使用したいと思います。lower_bound()とupper_bound( ) を使用するのはこれが初めてです。そこで、ここでコンパレータ機能を実装する方法を教えてください。

4

1 に答える 1

5

std::lower_bound値が引数以上の最初の要素の位置を返します。 std::upper_bound引数より大きい最初の要素の位置を返します。これらを使用して、次のように x と y の間の値の範囲を反復処理できます。

  auto vb = b[factor].begin();
  auto ve = b[factor].end();
  auto lb = lower_bound(vb,ve,x);
  auto ub = upper_bound(vb,ve,y);
  for (auto i=lb; i!=ub; ++i) {
    // Do something with *i
  }

この例を見てみましょう。ベクトルに次の値が含まれているとします。

1 3 4 7 9

そして、x=3 と y=7 としましょう。 std::lower_bound(vb,ve,x)は、3 以上の最初の値の位置を返します。3 に等しい値があるため、その位置が下限として取得されます。

std::upper_bound(vb,be,y)7 より大きい最初の値の位置を返します。この場合は 9 の位置になります。

したがって、ループは 3 の位置から 9 の位置まで進みますが、9 の位置は含まれません。これはまさに必要な値の範囲です。

x=5 で y=6 の場合はどうなるでしょうか。その範囲に値はありません。それは何をしますか？

5 以上の最初の値は 7 です。6 より大きい最初の値も 7 です。したがってlb、ub同じ位置になります。範囲内に要素がないため、ループはすぐに終了します。

于 2014-03-15T03:25:36.333 に答える