std::equal_range
ヘッダ <algorithm> で定義 | ||
| (1) | ||
template<class ForwardIt, class T > std::pair<ForwardIt,ForwardIt> | (C++20以前) | |
template<class ForwardIt, class T > constexprstd::pair<ForwardIt,ForwardIt> | (C++20およびそれ以降) | |
| (2) | ||
template<class ForwardIt, class T, class Compare > std::pair<ForwardIt,ForwardIt> | (C++20以前) | |
template<class ForwardIt, class T, class Compare > constexprstd::pair<ForwardIt,ForwardIt> | (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& を持つ必要はありませんが、関数は渡されたオブジェクトを変更してはなりません。 |
| 型の要件 | ||
-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){returnstd::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);{returnstd::make_pair(std::lower_bound(first, last, value, comp), std::upper_bound(first, last, value, comp));} |
[編集]例
#include <algorithm>#include <vector>#include <iostream> struct S {int number;char name;// note: name is ignored by this comparison operatorbool operator<(const S& s )const{return number < s.number;}}; int main(){// note: not ordered, only partitioned w.r.t. S defined belowstd::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 |
[編集]関連項目
| 指定された値より小さくない最初の要素を指すイテレータを返します (関数テンプレート) | |
| 指定された値より大きい最初の要素へのイテレータを返します (関数テンプレート) | |
| 指定範囲に要素が存在するかどうか調べます (関数テンプレート) | |
| 指定範囲の要素を2つのグループに分割します (関数テンプレート) |
