Заголовок "partition_point.hpp" содержит два варианта одного алгоритма: partition_point. Учитывая разделенную последовательность и предикат, алгоритм находит точку раздела; т.е. первый элемент в последовательности, который не удовлетворяет предикату.

Процедура partition_point занимает разделенную последовательность и предикат. Он возвращает итератор, который «назначает» первый элемент в последовательности, который не удовлетворяет предикату. Если все элементы в последовательности удовлетворяют предикату, то он возвращает один из последних элементов в последовательности.

partition_point приходят в двух формах; первый берет два итератора для определения диапазона. Вторая форма имеет один параметр диапазона и использует Boost. Чтобы пересечь его.

interface

Есть две версии; одна занимает два итератора, а другая занимает ряд.

template<typename ForwardIterator, typename Predicate>
	ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p );
template<typename Range, typename Predicate>
	boost::range_iterator<Range> partition_point ( const Range &r, Predicate p );

Examples

Учитывая контейнер c, содержащий { 0, 1, 2>, 3, 14, 15 }, затем

bool lessThan10 ( int i ) { return i < 10; }
bool isOdd ( int i ) { return i % 2 == 1; }
partition_point ( c, lessThan10 ) --> c.begin () + 4  (pointing at 14)
partition_point ( c.begin (), c.end (), lessThan10 ) --> c.begin () + 4  (pointing at 14)
partition_point ( c.begin (), c.begin () + 3, lessThan10 ) -> c.begin () + 3 (end)
partition_point ( c.end (), c.end (), isOdd ) --> c.end ()  // empty range

Iterator Requirements

partition_point требует передних итераторов или лучше; он не будет работать над входными итераторами или выходными итераторами.

Complexity

Оба варианта partition_point работают в O( log (N)) (логарифмическое) время; то есть, предикат будет применяться приблизительно log(N) раз. Однако для этого алгоритм должен знать размер последовательности. Для передних и двухнаправленных итераторов расчет размера последовательности составляет операцию O(N).

Exception Safety

Оба варианта partition_point принимают свои параметры по стоимости или константной ссылке и не зависят от какого-либо глобального состояния. Поэтому все процедуры в этом файле обеспечивают сильную гарантию исключения.

Notes