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)について分割されている (つまり、その式がtrueとなるすべての要素が、その式がfalseとなるすべての要素よりも前にある)。!(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 を返す二項述語。 述語関数のシグネチャは以下と同等なものであるべきです。
シグネチャが |
| 型の要件 | ||
-ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。
| ||
-Compare は BinaryPredicate の要件を満たさなければなりません。 Compare を満たす必要はありません。
| ||
戻り値
所望の範囲を定義するイテレータの組を格納する std::pair。 1つめのイテレータは value より小さくない最初の要素を指し、2つめのイテレータは value より大きい最初の要素を指します。
value より小さくない要素がなければ、 last が1つめのイテレータとして返されます。 同様に、 value より大きい要素がなければ、 last が2つめのイテレータとして返されます。
計算量
行われる比較の回数は first と last の距離の対数です (多くとも 2 * log
2(last - first) + O(1) 回の比較)。 しかし、 LegacyRandomAccessIterator でない場合、イテレータのインクリメント回数は線形になります。
実装例
| 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));
}
|
例
#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 |
関連項目
| 指定された値より小さくない最初の要素を指すイテレータを返します (関数テンプレート) | |
| 指定された値より大きい最初の要素へのイテレータを返します (関数テンプレート) | |
| 指定範囲に要素が存在するかどうか調べます (関数テンプレート) | |
| 指定範囲の要素を2つのグループに分割します (関数テンプレート) |
