◐ Shell
clean mode source ↗

std::upper_bound - cppreference.com

提供: cppreference.com

<tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody> <tbody class="t-dcl-rev t-dcl-rev-num "> </tbody><tbody> </tbody>

ヘッダ <algorithm> で定義

(1)

template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

 (C++20未満)

template< class ForwardIt, class T > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );

 (C++20以上)
(2)

template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

 (C++20未満)

template< class ForwardIt, class T, class Compare > constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

 (C++20以上)

範囲 [first, last) 内の value より大きい最初の要素を指すイテレータ、またはそのような要素が見つからない場合は last を返します。

範囲 [first, last) は式 !(value < element) または !comp(value, element) について分割されていなければなりません。 すなわち、その式が true となるすべての要素が、その式が false となるすべての要素よりも前になければなりません。 完全にソートされた範囲はこの基準を満たします。

1つめのバージョンは要素の比較に operator< を使用し、2つめのバージョンは指定された比較関数 comp を使用します。

引数

first, last - 調べる要素の範囲
value - 要素と比較する値
comp - 第1引数が第2引数より小さい (つまり前に順序付けされる) 場合に ​true を返す二項述語。

述語関数のシグネチャは以下と同等なものであるべきです。

bool pred(const Type1 &a, const Type2 &b);

シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなならず、値カテゴリに関わらず Type1 および Type2 型 (およびそれらの const 修飾された型) のすべての値を受理できなければなりません (そのため Type1 & は許されません。 また Type1 に対してムーブがコピーと同等でなければ Type1 も許されません (C++11以上))。
型 Type1 は、 T 型のオブジェクトから暗黙に変換可能なものでなければなりません。 型 Type2 は、 ForwardIt 型のオブジェクトの逆参照から暗黙に変換可能なものでなければなりません。 ​

型の要件
-ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。
-Compare は BinaryPredicate の要件を満たさなければなりません。 Compare を満たす必要はありません。

戻り値

value より大きい最初の要素を指すイテレータ、またはそのような要素が見つからない場合は last。

計算量

行われる比較の回数は first と last の距離の対数です (多くとも log
2(last - first) + O(1) 回の比較)。 しかし、 LegacyRandomAccessIterator でない場合、イテレータのインクリメント回数は線形になります。

実装例

1つめのバージョン 
template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);

    while (count > 0) {
        it = first; 
        step = count / 2; 
        std::advance(it, step);
        if (!(value < *it)) {
            first = ++it;
            count -= step + 1;
        } 
        else
            count = step;
    }
    return first;
}
2つめのバージョン 
template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);

    while (count > 0) {
        it = first; 
        step = count / 2;
        std::advance(it, step);
        if (!comp(value, *it)) {
            first = ++it;
            count -= step + 1;
        } 
        else
            count = step;
    }
    return first;
}

例

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    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(data.begin(), data.end(), 4);
    
    std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
}

出力:

欠陥報告

以下の動作変更欠陥報告は以前に発行された C++ 標準に遡って適用されました。

DR 適用先 発行時の動作 正しい動作
LWG 270 C++98 Compare was required to be a strict weak ordering only a partitioning is needed; heterogeneous comparisons permitted

関連項目