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

NAME
     std::ranges::inplace_merge - std::ranges::inplace_merge

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::bidirectional_iterator I, std::sentinel_for<I>
	S,

		  class   Comp	 =  ranges::less,  class  Proj	=  std::identity
     (since C++20)
	>								     (1)
     (constexpr since
	requires	     std::sortable<I,		  Comp, 	   Proj>
     C++26)
	    I inplace_merge( I first, I middle, S last,

			     Comp comp = {}, Proj proj = {} );
	template< ranges::bidirectional_range R, class Comp =
	ranges::less,

		  class 	Proj	     =		std::identity	       >
     (since C++20)
	requires   std::sortable<ranges::iterator_t<R>,  Comp,	Proj>	     (2)
     (constexpr since
	ranges::borrowed_iterator_t<R>
     C++26)
	    inplace_merge( R&& r, ranges::iterator_t<R> middle,

			   Comp comp = {}, Proj proj = {} );

	Merges two consecutive sorted ranges [first, middle) and [middle,  last)
     into one
	sorted range [first, last).

	A  sequence is said to be sorted with respect to the comparator comp and
     projection
	proj if for any iterator it pointing to the sequence and  any  non-nega-
     tive integer n
	such  that  it + n is a valid iterator pointing to an element of the se-
     quence,
	std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)))
     evaluates
	to false.

	This merge function is stable, which means that for equivalent	elements
     in the
	original two ranges, the elements from the first range (preserving their
     original
	order)	precede  the  elements	from  the second range (preserving their
     original order).

	1) Elements are compared using the given binary comparison function comp
     and
	projection object proj, and the ranges must be sorted  with  respect  to
     the same.
	2) Same as (1), but uses r as the range, as if using ranges::begin(r) as
     first, and
	ranges::end(r) as last.

	The  function-like  entities  described on this page are niebloids, that
     is:

	  * Explicit template argument lists cannot be	specified  when  calling
     any of them.
	  * None of them are visible to argument-dependent lookup.
	  *  When any of them are found by normal unqualified lookup as the name
     to the left
	    of the function-call operator, argument-dependent lookup  is  inhib-
     ited.

	In  practice,  they may be implemented as function objects, or with spe-
     cial compiler
	extensions.

Parameters
	first  - the beginning of the first sorted range
	middle - the end of the first range and  the  beginning  of  the  second
     range
	last   - the end of the second sorted range
	r      - the range of elements to merge inplace
	comp   - comparison to apply to the projected elements
	proj   - projection to apply to the elements in the range

Return value
	An iterator equal to last.

Complexity
	Exactly  N  a  1  comparisons, if additional memory buffer is available,
     where N =
	ranges::distance(first, last). Otherwise, \(\scriptsize
	\mathcal{O}(N\cdot\log{(N)})\)dh(N*log(N))  comparisons.   Additionally,
     twice as many
	projections as comparisons in both cases.

Notes
	This function attempts to allocate a temporary buffer. If the allocation
     fails, the
	less efficient algorithm is chosen.

	      Feature-test macro	Value  Std	   Feature
	__cpp_lib_constexpr_algorithms 202306L	   constexpr stable sorting

Possible implementation
	This  implementation  only shows the slower algorithm used when no addi-
     tional memory
	is available. See also the implementation in MSVC STL and libstdc++.

     struct inplace_merge_fn {
	 template<std::bidirectional_iterator I, std::sentinel_for<I> S,
		  class Comp = ranges::less, class Proj = std::identity>
	 requires std::sortable<I, Comp, Proj>
	 constexpr I operator()(I first, I middle, S last, Comp comp = {},  Proj
     proj = {}) const
	 {
	     I last_it = ranges::next(middle, last);
	     inplace_merge_slow(first, middle, last_it,
				ranges::distance(first, middle),
				ranges::distance(middle, last_it),
				std::ref(comp), std::ref(proj));
	     return last_it;
	 }

	 template<ranges::bidirectional_range R, class Comp = ranges::less,
		  class Proj = std::identity>
	 requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
	 constexpr ranges::borrowed_iterator_t<R>
	     operator()(R&& r, ranges::iterator_t<R> middle,
			Comp comp = {}, Proj proj = {}) const
	 {
	     return (*this)(ranges::begin(r), std::move(middle), ranges::end(r),
			    std::move(comp), std::move(proj));
	 }

     private:
	 template<class I, class Comp, class Proj>
	 static constexpr void inplace_merge_slow(I first, I middle, I last,
						  std::iter_difference_t<I> n1,
						  std::iter_difference_t<I> n2,
						  Comp comp, Proj proj)
	 {
	     if (n1 == 0 || n2 == 0)
		 return;
	     if (n1 + n2 == 2 && comp(proj(*middle), proj(*first)))
	     {
		 ranges::iter_swap(first, middle);
		 return;
	     }

	     I cut1 = first, cut2 = middle;
	     std::iter_difference_t<I> d1{}, d2{};

	     if (n1 > n2)
	     {
		 d1 = n1 / 2;
		 ranges::advance(cut1, d1);
		 cut2 = ranges::lower_bound(middle, last, *cut1,
					    std::ref(comp), std::ref(proj));
		 d2 = ranges::distance(middle, cut2);
	     }
	     else
	     {
		 d2 = n2 / 2;
		 ranges::advance(cut2, d2);
		 cut1 = ranges::upper_bound(first, middle, *cut2,
					    std::ref(comp), std::ref(proj));
		 d1 = ranges::distance(first, cut1);
	     }

	     I new_middle = ranges::rotate(cut1, middle, cut2);
	     inplace_merge_slow(first, cut1, new_middle, d1, d2,
				std::ref(comp), std::ref(proj));
	     inplace_merge_slow(new_middle, cut2, last, n1 - d1, n2 - d2,
				std::ref(comp), std::ref(proj));
	 } };

     inline constexpr inplace_merge_fn inplace_merge {};

Example
     // Run this code

      #include <algorithm>
      #include <complex>
      #include <functional>
      #include <iostream>
      #include <iterator>
      #include <vector>

      void print(auto const& v, auto const& rem, int middle = -1)
      {
	  for (int i{}; auto n : v)
	      std::cout << (i++ == middle ? "a " : "") << n << ' ';
	  std::cout << rem << '\n';
      }

      template<std::random_access_iterator I, std::sentinel_for<I> S>
      requires std::sortable<I>
      void merge_sort(I first, S last)
      {
	  if (last - first > 1)
	  {
	      I middle{first + (last - first) / 2};
	      merge_sort(first, middle);
	      merge_sort(middle, last);
	      std::ranges::inplace_merge(first, middle, last);
	  }
      }

      int main()
      {
	  // custom merge-sort demo
	  std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
	  print(v, ": before sort");
	  merge_sort(v.begin(), v.end());
	  print(v, ": after sort\n");

	  // merging with comparison function object and projection
	  using CI = std::complex<int>;
	  std::vector<CI> r{{0,1}, {0,2}, {0,3}, {1,1}, {1,2}};
	  const auto middle{std::ranges::next(r.begin(), 3)};
	  auto comp{std::ranges::less{}};
	  auto proj{[](CI z) { return z.imag(); }};

	  print(r, ": before merge", middle - r.begin());
	  std::ranges::inplace_merge(r, middle, comp, proj);
	  print(r, ": after merge");
      }

Output:
      8 2 0 4 9 8 1 7 3 : before sort
      0 1 2 3 4 7 8 8 9 : after sort

      (0,1) (0,2) (0,3) a (1,1) (1,2) : before merge
      (0,1) (1,1) (0,2) (1,2) (0,3) : after merge

See also
	ranges::merge	  merges two sorted ranges
	(C++20) 	  (niebloid)
	ranges::set_union computes the union of two sets
	(C++20) 	  (niebloid)
	ranges::is_sorted checks whether a range is sorted into ascending order
	(C++20) 	  (niebloid)
	ranges::sort	  sorts a range into ascending order
	(C++20) 	  (niebloid)
	inplace_merge	  merges two ordered ranges in-place
			  (function template)

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