45

二分探索を使用する関数はありますが、特定の述語に従って最後の項目以下lower_boundを返しますか?

lower_boundは次のように定義されています。

順序付けられた範囲内で、指定された値以上の値を持つ最初の要素の位置を検索します。順序付け基準はバイナリ述語で指定できます。

とupper_bound:

順序付けられた範囲内で、指定された値より大きい値を持つ最初の要素の位置を検索します。順序付け基準はバイナリ述語で指定できます。

具体的には、時間順のイベントのコンテナーがあり、特定の時間について、その時点またはその前に発生した最後のアイテムを見つけたいと考えています。上限/下限、逆反復子、および or を使用してこれを実現できますstd::greaterかstd::greater_equal?

編集:配列の開始前にポイントを要求する場合に対処するために、user763305 の提案に微調整が必​​要でした:

iterator it=upper_bound(begin(), end(), val, LessThanFunction());
if (it!=begin()) {
  it--; // not at end of array so rewind to previous item
} else {
  it=end(); // no items before this point, so return end()
}
return it;
4

5 に答える 5

47

並べ替えられたコンテナーでは、 より小さいか等しい最後の要素はx、 より大きい最初の要素の前の要素ですx。

したがって、 を呼び出しstd::upper_boundて、返されたイテレータを 1 回デクリメントすることができます。(デクリメントする前に、もちろんそれが begin イテレータでないことを確認する必要があります。そうである場合は、 より小さいか同等の要素はありませんx。)

于 2012-04-03T08:35:03.807 に答える
8

これはupper_boundのラッパー関数で、指定された値以下のコンテナーまたは配列の最大数を返します。

template <class ForwardIterator, class T>
  ForwardIterator largest_less_than_or_equal_to ( ForwardIterator first, 
                                                  ForwardIterator last,
                                                  const T& value)
{
  ForwardIterator upperb = upper_bound(first, last, value);

  // First element is >, so none are <=
  if(upperb == first)
    return NULL;

  // All elements are <=, so return the largest.
  if(upperb == last)
    return --upperb;

  return upperb - 1;
}

これが何をしているのか、そしてこの関数の使い方のより良い説明については、以下をチェックしてください：

C ++ STL —配列またはコンテナ内の特定の要素以下の最後の数値を検索します

于 2012-09-14T20:23:41.053 に答える
7

逆反復子ソリューションをテストしましたが、正しいです。

与えられvたものは「<」でソートされます

x より小さい最後の要素を見つける:

auto iter = std::upper_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

等しい x より小さい最後の要素を見つける:

auto iter = std::lower_bound(v.rbegin(), v.rend(), x, std::greater<int>());
if(iter == v.rend())
    std::cout<<"no found";
else
    std::cout<<*iter;

iter -= 1これはバージョンよりも優れています

于 2018-05-08T03:09:42.433 に答える
2

std::prev: https://en.cppreference.com/w/cpp/iterator/prev

#include <iostream>
#include <map>

int main()
{
    std::map<int, char> m{{2, 'a'}, {4, 'b'}, {6, 'c'}, {8, 'd'}, {10, 'e'}};

    int num = 3;
    auto it = m.upper_bound(num);
    auto pv = std::prev(it);

    std::cout << "upper bound of " << num << ": "
        << it->first << ", " << it->second << '\n';
    std::cout << "lower than or equal of " << num << ": "
        << pv->first << ", " << pv->second << '\n';
}

出力：

upper bound of 3: 4, b
lower than or equal than 3: 2, a
于 2020-04-28T18:27:34.993 に答える