std::equal_range

ヘッダ `<algorithm>` で定義
	(1)
template< class ForwardIt, class T > std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );			(C++20以前)
template< class ForwardIt, class T > constexpr std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );			(C++20およびそれ以降)
		(2)
template< class ForwardIt, class T, class Compare > std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );				(C++20以前)
template< class ForwardIt, class T, class Compare > constexpr std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );				(C++20およびそれ以降)

範囲 [first, last) 内の value と同等なすべての要素を含む範囲を返します。

範囲 [first, last) は value との比較について分割されていなければなりません。つまり、以下の要件をすべて満たしていなければなりません。

element < value または comp(element, value) について分割されている。
!(value < element) または !comp(value, element) について分割されている。
すべての要素について、 element < value または comp(element, value) が true であれば、 !(value < element) または !comp(value, element) も true である。

完全にソートされた範囲はこれらの基準を満たします。

返された範囲は、 value より小さくない最初の要素を指すイテレータと value より大きい最初の要素を指すイテレータの、2つのイテレータによって定義されます。 1つめのイテレータは std::lower_bound() を用いても取得することができ、2つめのイテレータは std::upper_bound() を用いても取得することができます。

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

first, last	-	調べる要素の範囲
value	-	要素と比較する値
comp	-	第1引数が第2引数より小さい (つまり前に順序付けされる) 場合に true を返す二項述語。述語関数のシグネチャは以下と同等なものであるべきです。 bool pred(const Type1 &a, const Type2 &b); シグネチャが const & を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなりません。型 Type1 および Type2 は、 T 型のオブジェクトが Type1 と Type2 の両方に暗黙に変換可能であり、 ForwardIt 型のオブジェクトの逆参照が Type1 と Type2 の両方に暗黙に変換可能なものでなければなりません。
型の要件
- `ForwardIt` は `ForwardIterator` の要件を満たさなければなりません。
- `Compare` は `BinaryPredicate` の要件を満たさなければなりません。 `Compare` を満たす必要はありません。

[編集] 戻り値

所望の範囲を定義するイテレータの組を格納する std::pair。 1つめのイテレータは value より小さくない最初の要素を指し、2つめのイテレータは value より大きい最初の要素を指します。

value より小さくない要素がなければ、 last が1つめのイテレータとして返されます。同様に、 value より大きい要素がなければ、 last が2つめのイテレータとして返されます。

[編集] 計算量

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

[編集] 実装例

1つめのバージョン

template<class ForwardIt, class T>
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last,
                const T& value)
{
    return std::make_pair(std::lower_bound(first, last, value),
                          std::upper_bound(first, last, value));
}

2つめのバージョン

template<class ForwardIt, class T, class Compare>
std::pair<ForwardIt,ForwardIt> 
    equal_range(ForwardIt first, ForwardIt last,
                const T& value, Compare comp);
{
    return std::make_pair(std::lower_bound(first, last, value, comp),
                          std::upper_bound(first, last, value, comp));
}

[編集] 例

Run this code

#include <algorithm>
#include <vector>
#include <iostream>
 
struct S
{
    int number;
    char name;
    // note: name is ignored by this comparison operator
    bool operator< ( const S& s ) const { return number < s.number; }
};
 
int main()
{
    // note: not ordered, only partitioned w.r.t. S defined below
    std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4,'G'}, {3,'F'} };
 
    S value = {2, '?'};
 
    auto p = std::equal_range(vec.begin(), vec.end(), value);
 
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->name << ' ';
 
 
    // heterogeneous comparison:
    struct Comp
    {
        bool operator() ( const S& s, int i ) const { return s.number < i; }
        bool operator() ( int i, const S& s ) const { return i < s.number; }
    };
 
    auto p2 = std::equal_range(vec.begin(),vec.end(), 2, Comp{});
 
    for ( auto i = p2.first; i != p2.second; ++i )
        std::cout << i->name << ' ';
}

出力:

B C D B C D

[編集] 欠陥報告

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

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

[編集] 関連項目

lower_bound	指定された値より小さくない最初の要素を指すイテレータを返します (関数テンプレート) [edit]
upper_bound	指定された値より大きい最初の要素へのイテレータを返します (関数テンプレート) [edit]
binary_search	指定範囲に要素が存在するかどうか調べます (関数テンプレート) [edit]
partition	指定範囲の要素を2つのグループに分割します (関数テンプレート) [edit]

言語
ヘッダ
コンセプト
言語サポートライブラリ
診断ライブラリ
ユーティリティライブラリ
文字列ライブラリ
コンテナライブラリ
アルゴリズムライブラリ
イテレータライブラリ
数値演算ライブラリ
入出力ライブラリ
ローカライゼーションライブラリ
正規表現ライブラリ (C++11)
アトミック操作ライブラリ (C++11)
スレッドサポートライブラリ (C++11)
ファイルシステムライブラリ (C++17)
技術仕様書

cppreference.com

検索

名前空間

変種

表示

操作