Алгоритм lower_bound()
|
template< class ForwardIterator, class Type > ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const Type &value ); template< class ForwardIterator, class Type, class Compare > ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const Type &value, |
class Compare );
lower_bound()
возвращает итератор, указывающий на первую позицию в отсортированной последовательности, ограниченной диапазоном [first,last), в которую можно вставить значение value, не нарушая упорядоченности. В этой позиции находится значение, большее либо равное value. Например, если дана такая последовательность:
int ia = = {12,15,17,19,20,22,23,26,29,35,40,51};
то обращение к lower_bound() с аргументом value=21
возвращает итератор, указывающий на 23. Обращение с аргументом 22
возвращает тот же итератор. В первом варианте алгоритма используется оператор “меньше”, определенный для типа элементов контейнера, а во втором для упорядочения элементов применяется объект comp.
|
#include <algorithm> #include <vector> #include <iostream.h>
int main() { int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40}; sort( &ia[0], &ia[12] ); int search_value = 18; int *ptr = lower_bound( ia, ia+12, search_value ); // печатается: // Первый элемент, перед которым можно вставить 18, - это 19 // Предыдущее значение равно 17 cout << "Первый элемент, перед которым можно вставить " << search_value << ", – это " << *ptr << endl << "Предыдущее значение равно " << *(ptr-1) << endl;
vector< int, allocator > ivec( ia, ia+12 ); // отсортировать в порядке возрастания ... sort( ivec.begin(), ivec.end(), greater<int>() );
search_value = 26; vector< int, allocator >::iterator iter; // необходимо указать, как именно // осуществлялась сортировка ... iter = lower_bound( ivec.begin(), ivec.end(), search_value, greater<int>() ); // печатается: // Первый элемент, перед которым можно вставить 26, - это 26 // Предыдущее значение равно 29 cout << "Первый элемент, перед которым можно вставить " << search_value << ", - это " << *iter << endl << "Предыдущее значение равно " << *(iter-1) << endl;
return 0; |
}
