home | help 
std::partition_point(3)        C++ Standard Libary	 std::partition_point(3)

NAME
     std::partition_point - std::partition_point

Synopsis
	Defined in header <algorithm>
	template<  class  ForwardIt,  class  UnaryPred	>		  (since
     C++11)
	ForwardIt partition_point( ForwardIt first, ForwardIt last,   (constexpr
     since C++20)
	UnaryPred p );

	Examines  the partitioned range [first, last) and locates the end of the
     first
	partition, that is, the first element that does not satisfy p or last if
     all
	elements satisfy p.

	If the elements elem of [first, last) are not partitioned  with  respect
     to the
	expression bool(p(elem)), the behavior is undefined.

Parameters
	first, last - the partitioned range of elements to examine
		      unary  predicate which returns true for the elements found
     in the
		      beginning of the range.

		      The expression p(v) must be convertible to bool for  every
     argument v
	p	    - of type (possibly const) VT, where VT is the value type of
     ForwardIt,
		      regardless of value category, and must not modify v. Thus,
     a parameter
		      type of VT&is not allowed
		      , nor is VT unless for VT a move is equivalent to a copy
		      (since C++11).

Type requirements
	-
	ForwardIt must meet the requirements of LegacyForwardIterator.
	-
	UnaryPred must meet the requirements of Predicate.

Return value
	The iterator past the end of the first partition within [first, last) or
     last if all
	elements satisfy p.

Complexity
	Given	\(\scriptsize	N\)N  as  std::distance(first,	last),	performs
     \(\scriptsize
	O(log(N))\)O(log(N)) applications of the predicate p.

Notes
	This algorithm is a more general form of std::lower_bound, which can  be
     expressed in
	terms  of  std::partition_point  with the predicate [&](const auto& e) {
     return e <
	value; });.

Possible implementation
	template<class ForwardIt, class UnaryPred>
	constexpr //< since C++20
	ForwardIt partition_point(ForwardIt first, ForwardIt last, UnaryPred p)
	{
	    for (auto length = std::distance(first, last); 0 < length; )
	    {
		auto half = length / 2;
		auto middle = std::next(first, half);
		if (p(*middle))
		{
		    first = std::next(middle);
		    length -= (half + 1);
		}
		else
		    length = half;
	    }

	    return first;
	}

Example
     // Run this code

      #include <algorithm>
      #include <array>
      #include <iostream>
      #include <iterator>

      auto print_seq = [](auto rem, auto first, auto last)
      {
	  for (std::cout << rem; first != last; std::cout << *first++ << ' ') {}
	  std::cout << '\n';
      };

      int main()
      {
	  std::array v{1, 2, 3, 4, 5, 6, 7, 8, 9};

	  auto is_even = [](int i) { return i % 2 == 0; };

	  std::partition(v.begin(), v.end(), is_even);
	  print_seq("After partitioning, v: ", v.cbegin(), v.cend());

	  const auto pp = std::partition_point(v.cbegin(), v.cend(), is_even);
	  const auto i = std::distance(v.cbegin(), pp);
	  std::cout << "Partition point is at " << i << "; v[" << i << "] = " <<
     *pp << '\n';

	  print_seq("First partition (all even elements): ", v.cbegin(), pp);
	  print_seq("Second partition (all odd elements): ", pp, v.cend());
      }

Possible output:
      After partitioning, v: 8 2 6 4 5 3 7 1 9
      Partition point is at 4; v[4] = 5
      First partition (all even elements): 8 2 6 4
      Second partition (all odd elements): 5 3 7 1 9

See also
	find
	find_if 		finds the first element satisfying specific cri-
     teria
	find_if_not		(function template)
	(C++11)
	is_sorted		checks whether a range is sorted into  ascending
     order
	(C++11) 		(function template)
				returns  an  iterator  to  the first element not
     less than the
	lower_bound		given value
				(function template)
	ranges::partition_point locates the partition  point  of  a  partitioned
     range
	(C++20) 		(niebloid)

http://cppreference.com 	   2024.06.10		 std::partition_point(3)
home | help