73

STL は二分探索関数 std::lower_bound と std::upper_bound を提供しますが、私はそれらのコントラクトが完全に不可解に見えるため、それらが何をするのか思い出せなかったので、それらを使用しない傾向があります。

名前を見るだけで、「lower_bound」は「最後の下限」、
つまり、指定された val (存在する場合) <= であるソートされたリストの最後の要素の略であると推測できます。
同様に、「upper_bound」は「最初の上限」、
つまりソートされたリストの最初の要素で、指定された val (存在する場合) >= の略であると思います。

しかし、ドキュメンテーションによると、彼らはそれとはかなり異なることを行っているとのことです。ドキュメントを言い換えると:
- lower_bound は >= val で
ある最初の要素を見つけます - upper_bound は > val である最初の要素を見つけます

したがって、lower_bound は下限をまったく検出しません。最初の上限を見つける!? そして upper_bound は、最初の厳密な上限を見つけます。

これって意味あるの？？どのように覚えていますか？

4

10 に答える 10

92

値が検索対象の値と等しい範囲 [ first, )に複数の要素がある場合、範囲 [ , )lastvallu

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

val正確には、範囲 [ first, ) 内に等しい要素の範囲ですlast。lとは、等しい範囲uの「下限」と「上限」です。半開間隔で考えることに慣れていれば、それは理にかなっています。

std::equal_range(は、1 回の呼び出しで下限と上限の両方をペアで返すことに注意してください。)

于 2014-05-08T23:57:41.517 に答える
32 
std::lower_bound

[first, last) の範囲内で value より小さくない (つまり、より大きいか等しい) 最初の要素を指す反復子を返します。

std::upper_bound

[first, last) の範囲内で valueより大きい最初の要素を指す反復子を返します。

したがって、下限と上限の両方を混合することで、範囲の開始位置と終了位置を正確に記述することができます。

これって意味あるの？？

はい。

例：

ベクトルを想像する

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

auto lower = std::lower_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                  // ^ lower

auto upper = std::upper_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                           // ^ upper

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

プリント: 4 4 4

http://en.cppreference.com/w/cpp/algorithm/lower_bound

http://en.cppreference.com/w/cpp/algorithm/upper_bound

于 2014-05-08T23:50:53.297 に答える
14

この場合、一枚の絵は千の言葉に値すると思います。それらを使用して2、次のコレクションを検索するとします。矢印は、2 つが返すイテレータを示しています。

ここに画像の説明を入力

したがって、その値を持つオブジェクトがコレクションに既に存在するlower_bound場合、 はそれらの最初upper_boundのオブジェクトを参照する反復子を提供し、それらの最後のオブジェクトの直後のオブジェクトを参照する反復子を提供します。

これにより、返されたイテレータがhintへのパラメータとして使用できるようになりますinsert。

したがって、これらをヒントとして使用すると、挿入するアイテムは、その値を持つ新しい最初のアイテム ( を使用した場合lower_bound) またはその値を持つ最後のアイテム ( を使用した場合upper_bound) になります。以前にその値を持つ項目がコレクションに含まれていなかった場合でも、コレクションhint内の正しい位置に挿入するために として使用できる反復子を取得できます。

もちろん、ヒントなしで挿入することもできますが、ヒントを使用すると、イテレータが指す項目の直前に挿入する新しい項目を挿入できる場合、挿入が一定の複雑さで完了することが保証されます (これらの両方の場合)。

于 2014-05-09T00:43:48.017 に答える
7

私はブライアンの答えを受け入れましたが、それについて明確にする別の役立つ考え方に気付いたので、参考のためにこれを追加します。

返された反復子は、要素 *iter ではなく、その要素の直前、つまりその要素とリスト内の前の要素がある場合はその要素の間を指していると考えてください。そう考えると、2 つの関数のコントラクトは対称になります。lower_bound は <val から >=val への遷移の位置を見つけ、upper_bound は <=val から >val への遷移の位置を見つけます。別の言い方をすれば、lower_bound は val と等しい項目の範囲 (つまり、std::equal_range が返す範囲) の始まりであり、upper_bound はそれらの終わりです。

ドキュメントで、彼らがこのように（または与えられた他の良い答えのいずれかで）話してくれることを願っています。それはそれをはるかに神秘的にするでしょう！

于 2014-05-10T09:53:14.280 に答える
6

順序を考える

1 2 3 4 5 6 6 6 7 8 9

6 の下限は、最初の 6 の位置です。

6 の上限は 7 の位置です。

これらの位置は、一連の 6 つの値を指定する共通の (開始、終了) ペアとして機能します。

例：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

auto main()
    -> int
{
    vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};
    auto const pos1 = lower_bound( v.begin(), v.end(), 6 );
    auto const pos2 = upper_bound( v.begin(), v.end(), 6 );
    for( auto it = pos1; it != pos2; ++it )
    {
        cout << *it;
    }
    cout << endl;
}
于 2014-05-08T23:54:13.710 に答える
1

両方の関数は、並べ替えを保持する並べ替えられたシーケンス内の挿入ポイントを見つけるという点で非常に似ています。シーケンス内に検索項目と等しい既存の要素がない場合、それらは同じ反復子を返します。

シーケンス内で何かを見つけようとしている場合は、lower_bound- を使用します。見つかった場合、要素を直接指します。

シーケンスに挿入する場合は、upper_bound- を使用して、重複の元の順序を保持します。

于 2016-08-04T20:35:07.003 に答える