Алгоритм upper_bound()
template< class ForwardIterator, class Type >
ForwardIterator
upper_bound( ForwardIterator first,
ForwardIterator last, const Type &value );
template< class ForwardIterator, class Type, class Compare >
ForwardIterator
upper_bound( ForwardIterator first,
ForwardIterator last, const Type &value,
Compare comp );
upper_bound() возвращает итератор, указывающий на последнюю позицию в отсортированной последовательности [first,last), в которую еще можно вставить значение value, не нарушая упорядоченности. Значения всех элементов, начиная с этой позиции и далее, будут больше, чем value. Например, если дана последовательность:
int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};
то обращение к upper_bound() с value=21 вернет итератор, указывающий на значение 22, а обращение с value=22 – на значение 23. В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера; во втором – заданная программистом операция comp.
#include <algorithm>
#include <vector>
#include <assert.h>
#include <iostream.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
vector<int,allocator> vec(ia,ia+12);
sort(ia,ia+12);
int *iter = upper_bound(ia,ia+12,19);
assert( *iter == 20 );
sort( vec.begin(), vec.end(), greater<int>() );
vector<int,allocator>::iterator iter_vec;
iter_vec = upper_bound( vec.begin(), vec.end(),
27, greater<int>() );
assert( *iter_vec == 26 );
// печатается: 51 40 35 29 27 26 23 22 20 19 17 15 12
vec.insert( iter_vec, 27 );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
}
