С++ для начинающих

       

Алгоритм 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 );

           // отсортировать в порядке возрастания ...



Содержание раздела