24

lower_bound とはどういう意味ですか。推測する必要がある場合、この関数は要求された値よりも小さい最後の要素で反復子を返すと答えます。しかし、lower_bound は upper_bound とほぼ同じであることがわかります。唯一の違いは、upper_bound の場合の厳密な不等式です。下限の通常の定義と一致する真の下限選択関数が stl にありますか。

編集:ドキュメント内の否定が多すぎて混乱しました。問題は、同じイテレータを取得したことです。lower_bound の戻り値から 1 を引いて解決しました。補間に使用します：

    float operator()(double f)
        {
        SpectrumPoint* l=std::lower_bound(beginGet(),endGet(),(SpectrumPoint){float(f),0.0f}
            ,SpectrumPoint::CompareFreqLessThan);
        if(l>beginGet())
            {--l;}

        SpectrumPoint* u=std::lower_bound(beginGet(),endGet(),(SpectrumPoint){float(f),0.0f}
            ,SpectrumPoint::CompareFreqLessThan);

        if(u==endGet())
            {u=beginGet();}

        if(l==u)
            {
            if(u==endGet())
                {return u->amp;}
            return l->amp;
            }

        double f_min=l->freq;
        double A_min=l->amp;
        double f_max=u->freq;
        double A_max=u->amp;

        double delta_f=f_max-f_min;
        double delta_A=A_max-A_min;

        return A_min + delta_A*(f-f_min)/delta_f;
        }

この混乱をお詫び申し上げます:-(

4

7 に答える 7

131

  • 下限：大きいか等しい最初の要素。

  • 上限：厳密に大きい最初の要素。

例：

+- lb(2) == ub(2)       +- lb(6)        +- lb(8)
|        == begin()     |  == ub(6)     |   +- ub(8) == end()
V                       V               V   V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
    ^               ^                       ^
    |               |                       |
    +- lb(4)        +- ub(4)                +- lb(9) == ub(9) == end()

    |- eq-range(4) -|

ご覧のとおり、nのハーフオープン等範囲は[lb（n）、ub（n））です。

両方の境界は、順序が維持されるように目的の値の要素に意味のある挿入位置を提供しますが、要素がすでに存在する場合は、実際にその要素を指すイテレーターを取得するというlower_bound特徴的な機能があることに注意してください。したがって、順序付けられた範囲で使用して、独自のメンバーシップまたは複数メンバーシップのコンテナーを実装できます。lower_bound

void insert(Container & c, T const & t)
{
    auto it = std::lower_bound(c.begin(), c.end(), t);

    // if unique container:
    if (it != c.end() && *it == t) { /* error, element exists! */ return; }

    c.insert(it, t);
}
于 2012-08-28T12:23:07.017 に答える
8

要求された値よりも小さい最後の要素の 1 つ後ろの反復子を返します。これは、挿入位置として役立ちます (関数がイテレータを返すのはそのためです)。半開範囲first, lower_bound(first, last, value)が 未満のすべての値を指定することも役立ちますvalue。

upper_bound要求された値の最後の要素 [以下/以下] の 1 つ後ろの反復子を返します。または厳密には、どちらのアルゴリズムも小なりコンパレータのみを扱うため、値が小なりでない最後の要素です。

によって返される反復子の前に反復子が必要な場合はlower_bound、1 を減算する (ランダム アクセス反復子の場合)、デクリメントする (双方向反復子の場合)、または使用する代わりに線形検索を行うことlower_boundができます (これらのいずれでもない前方反復子の場合)。 .

要求された値よりも小さい要素がないというエッジケースに注意してください。この場合、必要なものが存在しないため、必要なものを取得できません。lower_boundもちろん、その場合は範囲​​の先頭を返すため、特別なケースの戻り値は必要ありません。

于 2012-08-28T12:16:40.790 に答える
8

これは再開されたので、コメントを回答にしようと思います。

名前lower_boundは数学的に正しくありません。より適切な名前は かもしれませんがleast_upper_bound、それはおそらく数学に興味のない人々を混乱させるでしょう。（そして、あなたは何と呼んでいますupper_boundかalmost_least_upper_bound？ ええ！）

私のアドバイス: 名前lower_boundと名前upper_boundが技術的に間違っているという事実を乗り越えてください。定義された 2 つの関数は非常に便利です。これらの関数は、表記の有用な乱用と考えてください。

C++ の反復子の概念に準拠した数学的に正しいlower_bound関数を作成するには、関数は順方向反復子ではなく逆方向反復子を返す必要があります。lower_bound逆イテレータを返すことは、おそらく誤った名前のandがとるアプローチほど有用ではありません。upper_bound逆イテレータを返すという概念は、すべてのコンテナが元に戻せるわけではないという事実に反しています。

なぜ逆イテレータなのか? コンテナーに上限が存在するという保証がないのと同様に、下限が存在するという保証もありません。既存の値lower_boundとupper_bound戻りend()値は、検索対象の値がスケール外の高さであることを示します。rend()検索対象の値がスケール外の低さであることを示すために、真の下限が返される必要があります。

前方反復子の形式で真の下限を実装する方法がありますが、end()「下限がない」という意味を乱用するという代償が伴います。この表記法の乱用の問題は、関数の一部のユーザーが同等のことを行う可能性があることtrue_lower_bound(off_scale_low_search_value)-1です。1 つは、セット内の最大の要素へのポインターを持ちます。

とは言っても、やり方はこうです。end()コンテナーが空の場合、または検索対象の値がコンテナー内の最初の値より小さい場合は、真の下限関数が返されます。それ以外の場合は戻りupper_bound()-1ます。

于 2012-08-28T14:27:49.673 に答える
2

lower_bound、upper_boundおよびequal_rangeは、ソートされた順序で二分探索を実行する関数です。3つの関数の必要性は、要素がシーケンスで繰り返される可能性があるという事実から来ています。

1, 2, 3, 4, 4, 4, 5, 6, 7

この場合、値4を検索すると、値4lower_boundの3つの要素の最初の要素をupper_bound指すイテレーターが返され、値5の要素を指すイテレーターが返され、equal_rangeこれら2つのイテレーターを含むペアが返されます。

于 2012-08-28T12:22:49.907 に答える
1

lower_boundおよびの別の使用法はupper_bound、コンテナ内の等しい要素の範囲を見つけることです。

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);
auto upper = std::upper_bound(lower, data.end(), 4);

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
于 2012-08-28T12:19:23.167 に答える
1

ああ！

元のコードを変更しましたか、それともコピーと貼り付けのエラーが最初からありましたか?

float operator()(double f)
{
    SpectrumPoint* l=std::lower_bound//...
...
    SpectrumPoint* u=std::lower_bound//...
...
}

今日読んだコードでは、lower_bound を「l」と「u」の両方に割り当てています。

于 2014-03-11T11:27:49.967 に答える