C++STLアルゴリズムlower_bound、upper_bound、equal_range
3905 ワード
参考『C++Primer』
//全ての容器適用(O(log(n))))シーケンシャル区間検索アルゴリズム
lower_bound()/最初に一致する要素を探して、位置反復器を返して、valが現れた最初の位置を返します
upper_bound()/最後の一致する要素を探して、位置反復器を返して、Valが現れた最後の位置の次の位置を返します
equal_range()/一対の反復器pair(<>,<>)を探し、lower_に等しいbound()とupper_bound(). 関連コンテナには等価なメンバー関数があり、パフォーマンスが向上します.
//全ての容器適用(O(log(n))))シーケンシャル区間検索アルゴリズム
lower_bound()/最初に一致する要素を探して、位置反復器を返して、valが現れた最初の位置を返します
upper_bound()/最後の一致する要素を探して、位置反復器を返して、Valが現れた最後の位置の次の位置を返します
equal_range()/一対の反復器pair(<>,<>)を探し、lower_に等しいbound()とupper_bound(). 関連コンテナには等価なメンバー関数があり、パフォーマンスが向上します.
#include
#include
#include
#include
#include
using namespace std;
/*************************************************************************************
std::lower_bound algorithm
--------------------------------------------------------------------------------------
template
ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last,
const T& value );
template
ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last,
const T& value, Compare comp );
//eg:
template
ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value )
{
ForwardIterator it;
iterator_traits::difference_type count, step;
count = distance(first,last);
while (count>0)
{
it = first; step=count/2; advance (it,step);
if (*it
ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last,
const T& value );
template
ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last,
const T& value, Compare comp );
//eg:
template
ForwardIterator upper_bound ( ForwardIterator first, ForwardIterator last, const T& value )
{
ForwardIterator it;
iterator_traits::difference_type count, step;
count = distance(first,last);
while (count>0)
{
it = first; step=count/2; advance (it,step);
if (!(value
pair
equal_range ( ForwardIterator first, ForwardIterator last, const T& value );
template
pair
equal_range ( ForwardIterator first, ForwardIterator last, const T& value,
Compare comp );
//eg:
template
pair
equal_range ( ForwardIterator first, ForwardIterator last, const T& value )
{
ForwardIterator it = lower_bound (first,last,value);
return make_pair ( it, upper_bound(it,last,value) );
}
*************************************************************************************/
bool mygreater (int i,int j){ return (i>j); }
int main()
{
int myints[] = {10,20,30,30,20,10,10,20};
vector v(myints,myints+8); // 10 20 30 30 20 10 10 20
vector::iterator low,up;
sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
cout<::iterator,vector::iterator> bounds;
// using default comparison:
// sort (v.begin(), v.end()); // 10 10 10 20 20 20 30 30
bounds=equal_range (v.begin(), v.end(), 20); // ^ ^
cout<