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

FreeBSD Manual Pages

  
 
  

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

NAME
       std::set_intersection - std::set_intersection

Synopsis
	  Defined in header <algorithm>
	  template< class InputIt1, class InputIt2, class
	  OutputIt >

	  OutputIt   set_intersection(	InputIt1  first1,		(until
       C++20)
	  InputIt1 last1,
	  InputIt2 first2, InputIt2 last2,

	  OutputIt d_first );
	  template< class InputIt1, class InputIt2, class
	  OutputIt >

	  constexpr  OutputIt  set_intersection(  InputIt1		(since
       C++20)
	  first1, InputIt1 last1,
	  InputIt2 first2, InputIt2 last2,

	  OutputIt d_first );
	  template< class ExecutionPolicy, class
	  ForwardIt1, class ForwardIt2,	class ForwardIt3 >

	  ForwardIt3   set_intersection(  ExecutionPolicy&&	   (2)	(since
       C++17)
	  policy, ForwardIt1 first1, ForwardIt1	last1,
	  ForwardIt2 first2, ForwardIt2	last2,

	  ForwardIt3 d_first );
	  template< class InputIt1, class InputIt2, class  (1)
	  OutputIt, class Compare >

	  OutputIt	   set_intersection(	     InputIt1	       first1,
       (until C++20)
	  InputIt1 last1,
	  InputIt2 first2, InputIt2 last2,

	  OutputIt d_first, Compare comp );
	  template< class InputIt1, class InputIt2, class
	  OutputIt, class Compare >

	  constexpr	    OutputIt	     set_intersection(	      InputIt1
       (since C++20)
	  first1, InputIt1 last1,			       (3)
	  InputIt2 first2, InputIt2 last2,

	  OutputIt d_first, Compare comp );
	  template< class ExecutionPolicy, class
	  ForwardIt1, class ForwardIt2,

	  class	ForwardIt3, class Compare >
	  ForwardIt3   set_intersection(    ExecutionPolicy&&		   (4)
       (since C++17)
	  policy, ForwardIt1 first1, ForwardIt1	last1,
	  ForwardIt2 first2, ForwardIt2	last2,

	  ForwardIt3 d_first, Compare comp );

	  Constructs  a	 sorted	 range beginning at d_first consisting of ele-
       ments that are found
	  in both sorted ranges	[first1, last1)	and [first2, last2).  If  some
       element is found
	  m times in [first1, last1) and n times in [first2, last2), the first
       std::min(m, n)
	  elements  will  be  copied  from  the	first range to the destination
       range. The order	of
	  equivalent elements is preserved. The	resulting range	cannot overlap
       with either of
	  the input ranges.

	  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
	  first1, last1	- the first range of elements to examine
	  first2, last2	- the second range of elements to examine
	  d_first	- the beginning	of the destination range
	  policy	 -  the	 execution policy to use. See execution	policy
       for details.
			  comparison function object (i.e. an object that sat-
       isfies 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
       equivalent 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 accept all
			  values  of type (possibly const) Type1 and Type2 re-
       gardless	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  objects
       of types
			  InputIt1  and	 InputIt2 can be dereferenced and then
       implicitly
			  converted to both Type1 and Type2.

Type requirements
	  -
	  InputIt1, InputIt2 must meet the requirements	 of  LegacyInputItera-
       tor.
	  -
	  OutputIt must	meet the requirements of LegacyOutputIterator.
	  -
	  ForwardIt1, ForwardIt2, ForwardIt3 must meet the requirements	of
	  LegacyForwardIterator.

Return value
	  Iterator past	the end	of the constructed range.

Complexity
	  At most \(\scriptsize	2\cdot(N_1+N_2)-1\)2(N
	  1+N
	  2)-1 comparisons, where \(\scriptsize	N_1\)N
	  1 and	\(\scriptsize N_2\)N
	  2 are	std::distance(first1, last1) and std::distance(first2, last2),
       respectively.

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.

Possible implementation
First version
	  template<class InputIt1, class InputIt2, class OutputIt>
	  OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
				    InputIt2 first2, InputIt2 last2,
				    OutputIt d_first)
	  {
	      while (first1 != last1 &&	first2 != last2) {
		  if (*first1 <	*first2) {
		      ++first1;
		  } else  {
		      if (!(*first2 < *first1))	{
			  *d_first++ = *first1++; // *first1 and  *first2  are
       equivalent.
		      }
		      ++first2;
		  }
	      }
	      return d_first;
	  }

Second version
	  template<class InputIt1, class InputIt2,
		   class OutputIt, class Compare>
	  OutputIt set_intersection(InputIt1 first1, InputIt1 last1,
				    InputIt2 first2, InputIt2 last2,
				    OutputIt d_first, Compare comp)
	  {
	      while (first1 != last1 &&	first2 != last2) {
		  if (comp(*first1, *first2)) {
		      ++first1;
		  } else {
		      if (!comp(*first2, *first1)) {
			  *d_first++  =	 *first1++; // *first1 and *first2 are
       equivalent.
		      }
		      ++first2;
		  }
	      }
	      return d_first;
	  }

Example
       // Run this code

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <iterator>
	int main()
	{
	    std::vector<int> v1{1,2,3,4,5,6,7,8};
	    std::vector<int> v2{	5,  7,	9,10};
	    std::sort(v1.begin(), v1.end());
	    std::sort(v2.begin(), v2.end());

	    std::vector<int> v_intersection;

	    std::set_intersection(v1.begin(), v1.end(),
				  v2.begin(), v2.end(),
				  std::back_inserter(v_intersection));
	    for(int n :	v_intersection)
		std::cout << n << ' ';
	}

Output:
	5 7

See also
	  set_union		   computes the	union of two sets
				   (function template)
	  ranges::set_intersection computes the	intersection of	two sets
	  (C++20)		   (niebloid)

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

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

home | help