Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

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

NAME
       std::inplace_merge - std::inplace_merge

Synopsis
	  Defined in header <algorithm>
	  template<		   class	       BidirIt		     >
       (1)
	  void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );
	  template< class ExecutionPolicy, class BidirIt >
	  void	inplace_merge(	ExecutionPolicy&&   policy,   BidirIt	first,
       (2) (since C++17)
	  BidirIt middle, BidirIt last );
	  template< class BidirIt, class Compare>
	  void	inplace_merge(	BidirIt	 first,	 BidirIt middle, BidirIt last,
       (3)
	  Compare comp );
	  template< class ExecutionPolicy, class BidirIt, class	Compare>

	  void	inplace_merge(	ExecutionPolicy&&   policy,   BidirIt	first,
       (4) (since C++17)
	  BidirIt middle, BidirIt last,

	  Compare comp );

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

	  A sequence [first, last) is said to be sorted	with respect to	a com-
       parator comp if
	  for any iterator it pointing to the sequence	and  any  non-negative
       integer n such
	  that	it  +  n is a valid iterator pointing to an element of the se-
       quence, comp(*(it +
	  n), *it) evaluates to	false.

	  This merge 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 or-
       der).

	  1) Elements are compared using operator<  and	 the  ranges  must  be
       sorted with respect
	  to the same.
	  3)  Elements are compared using the given binary comparison function
       comp and	the
	  ranges must be sorted	with respect to	the same.
	  2,4) Same as (1,3), but executed according to	 policy.  These	 over-
       loads do	not
	  participate in overload resolution unless
	  std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
	  (until C++20)
	  std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
	  (since C++20)	is true.

Parameters
	  first	  -  the beginning of the first	sorted range
	  middle   -   the  end	of the first sorted range and the beginning of
       the second
	  last	  -  the end of	the second sorted range
	  policy  -  the execution policy to use. See execution	policy for de-
       tails.
		     comparison	function object	(i.e. an object	that satisfies
       the
		     requirements of Compare) which returns true if the	 first
       argument	is
		     less than (i.e. is	ordered	before)	the second.

		     The signature of the comparison function should be	equiv-
       alent to	the
		     following:

		     bool cmp(const Type1 &a, const Type2 &b);
	  comp	  -
		     While  the	 signature  does not need to have const	&, the
       function	must not
		     modify the	objects	passed to it and must be able  to  ac-
       cept all	values of
		     type (possibly const) Type1 and Type2 regardless of value
       category	(thus,
		     Type1 & is	not allowed
		     , nor is Type1 unless for Type1 a move is equivalent to a
       copy
		     (since C++11)).
		     The  types	Type1 and Type2	must be	such that an object of
       type BidirIt can
		     be	dereferenced and then implicitly converted to both  of
       them.

Type requirements
	  -
	  BidirIt must meet the	requirements of	ValueSwappable and
	  LegacyBidirectionalIterator.
	  -
	  The type of dereferenced BidirIt must	meet the requirements of Move-
       Assignable and
	  MoveConstructible.

Return value
	  (none)

Complexity
	  Given	N = std::distance(first, last)},

	  1,3)	Exactly	 N-1 comparisons if enough additional memory is	avail-
       able. If	the memory
	  is insufficient, O(N log N) comparisons.
	  2,4) O(N log N) comparisons.

Exceptions
	  The overloads	with a template	parameter named	ExecutionPolicy	report
       errors as
	  follows:

	    * If execution of a	function invoked  as  part  of	the  algorithm
       throws an exception
	      and ExecutionPolicy is one of the	standard policies, std::termi-
       nate is called.
	      For  any	other ExecutionPolicy, the behavior is implementation-
       defined.
	    * If the algorithm fails to	 allocate  memory,  std::bad_alloc  is
       thrown.

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

Possible implementation
	  See the implementations in libstdc++ and libc++.

Example
	  The following	code is	an implementation of merge sort.

       // Run this code

	#include <vector>
	#include <iostream>
	#include <algorithm>

	template<class Iter>
	void merge_sort(Iter first, Iter last)
	{
	    if (last - first > 1) {
		Iter middle = first + (last - first) / 2;
		merge_sort(first, middle);
		merge_sort(middle, last);
		std::inplace_merge(first, middle, last);
	    }
	}

	int main()
	{
	    std::vector<int> v{8, 2, -2, 0, 11,	11, 1, 7, 3};
	    merge_sort(v.begin(), v.end());
	    for(auto n : v) {
		std::cout << n << ' ';
	    }
	    std::cout << '\n';
	}

Output:
	-2 0 1 2 3 7 8 11 11

See also
	  merge			merges two sorted ranges
				(function template)
	  sort			sorts a	range into ascending order
				(function template)
				sorts a	range of elements while	preserving or-
       der between equal
	  stable_sort		elements
				(function template)
	  ranges::inplace_merge	merges two ordered ranges in-place
	  (C++20)		(niebloid)

http://cppreference.com		  2022.07.31		 std::inplace_merge(3)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::inplace_merge&sektion=3&manpath=FreeBSD+Ports+15.0>

home | help