17

std::algorithm単純な配列でできる限りいつでも使用するのが好きです。今、私には 2 つの疑問があります。std::lower_bound引数として指定した値が見つからない場合に何が起こるかを使用したいとしますか?

int a[] = {1,2,3,4,5,6};
int* f = std::lower_bound(a,a+6,20);

*f を印刷したときの結果は 20 です。

を使用しても同じことが起こりますstd::find。

int a[] = {1,2,3,4,5,6};
int* f = std::find(a,a+6,20);

*f を印刷したときの結果は 20 です。

  1. これが見つからない場合、戻り値は常に元の引数であるということですか?
  2. バイナリ検索アルゴリズムを実装しているため、パフォーマンスの面では のstd::lower_bound方が優れています。std::find配列が大きい場合、たとえば最大 10 要素の場合、std::find のパフォーマンスは向上しますか? 舞台裏で std::lower_bound が std::advance と std::distance を呼び出します。これらの呼び出しも節約できるかもしれません。

どうもありがとう

AFG

4

4 に答える 4

19

私が持っている結果は20です。（後で編集：* fを印刷したときの結果は20です。）

いいえ、得られる結果はですa+6。未定義の動作を呼び出す間接参照。20を印刷するか、「シャーリーマクレーン」を印刷するか、車を爆破する可能性があります。

これが見つからない場合、戻り値が元の引数であるのは常に事実ですか？

20は配列内の他の値よりも大きいため、この場合、戻り値は常に2番目の引数になります。値が見つからないが、既存の値よりも小さい場合、戻り値は次に大きい項目を指します。

cppreference.comから、std :: lower_boundの戻り値は、「以上の最初の要素を指すイテレータvalue、またはlastそのような要素が見つからない場合」です。

パフォーマンスの面で...

それを測定します。ここで他のアドバイスはあなたの実際の経験的証拠に立ち向かうことはありません。

舞台裏でstd::lower_boundはstd::advanceとstd::distanceを呼び出します..多分私はこれらの呼び出しも節約するかもしれませんか？

ほぼ間違いなくそうではありません。これらの呼び出しは、ほぼ確実に、単一の（またはごく少数の）命令に最適化されています。

于 2012-06-01T15:56:20.390 に答える
7

とによって返される反復子には、1 つの大きな違いがありlower_boundますfind。アイテムが見つからない場合lower_boundは、ソート順を維持するためにアイテムを挿入するイテレータを返します。findアイテムが見つからない場合、終了イテレータ (つまり、 の 2 番目の引数find) を返します。あなたの例では、配列の最後から何かを見つけようとしているので、どちらも同じ反復子を返しますが、それは完全な偶然です。

于 2012-06-01T16:07:24.923 に答える
6

あなたの例ではf、 と等しいため、 を逆参照してはなりませんa+6。とにかく持っているので、UB の領域にいますが、値 20 がたまたま array の直後のスタックにあると思いますa。

確かに、十分に小さい配列の場合、線形検索は二分検索よりも高速になる可能性があります。10は「大きい」ではなく「小さい」です。小さな配列に対して多くの検索を行うプログラムがある場合は、それぞれの時間を計って見ることができます。

std::advanceandのオーバーヘッドは基本的にないはずですstd::distance- 中途半端な能力のある C++ コンパイラはすべてをインライン化し、ポインタの加算と減算に変わります。

于 2012-06-01T15:57:50.707 に答える
4

次の実装を使用できます

int a[] = {1,2,3,4,5,6};

int f = lower_bound(a,a+6,20)-a;

配列に 20 が存在する場合、配列 a 内の要素のインデックスが返されます (0 ベースのインデックスが使用されます)。配列に 20 が存在しない場合は、配列の長さである 6 が返されます。

最悪の場合、検索対象の項目は (n-1) 番目のインデックス (n は配列のサイズの場合) に存在します。その場合、f は n-1 になります。

f は、検索対象の項目が配列に存在しない場合にのみ、n または配列のサイズに等しくなります。

それがあなたの質問に答えることを願っています。

于 2018-06-04T04:59:33.563 に答える