# set_intersection

Processes the sorted intersection of two ranges

## Definition

The**set_intersection()**algorithm is defined in the standard header

**<algorithm>**and in the nonstandard backward-compatibility header

**<algo.h>**.

## Interface

#include <algorithm> template < class InputIterator1, class InputIterator2, class OutputIterator > OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result ); template < class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate > OutputIterator set_intersection( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, BinaryPredicate comp );

**Parameters:**

Parameter | Description |
---|---|

first1 | An input iterator addressing the position of the first element in the first of two sorted source ranges to be united and sorted into a single range representing the intersection of the two source ranges |

last1 | An input iterator addressing the position one past the last element in the first of two sorted source ranges to be united and sorted into a single range representing the intersection of the two source ranges |

first2 | An input iterator addressing the position of the first element in second of two consecutive sorted source ranges to be united and sorted into a single range representing the intersection of the two source ranges |

last2 | An input iterator addressing the position one past the last element in second of two consecutive sorted source ranges to be united and sorted into a single range representing the intersection of the two source ranges |

result | An output iterator addressing the position of the first element in the destination range where the two source ranges are to be united into a single sorted range representing the intersection of the two source ranges |

comp | User-defined predicate function object that defines the sense in which one element is greater than another. The binary predicate takes two arguments and should return `true` when the first element is less than the second element and `false` otherwise |

## Description

**Set_intersection**function creates a sorted range beginning at result consisting of all elements present in one or both sorted ranges

`[first1, last1)`

and `[first2, last2)`

.
If an element is found `m`

times in `[first1, last1)`

and `n`

times in `[first2, last2)`

(where `m`

or `n`

may be zero), then it will appear `min(m, n)`

times in the output range.
The first version compares objects using `operator<`

, and the second compares objects using a function object `comp`

.## Complexity

The complexity is**linear;**performs at most

`2 * ((last1 - first1) + (last2 - first2)) - 1`

comparisons.Example:

##### Example - set_intersection algorithm

Problem

This program illustrates the use of the STL

**set_intersection()**algorithm (default version) to find the values that are in a first vector of integers and also in a second vector of integers, and write them out to a third vector of integers.Workings

#include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { int a1[] = {11, 12, 12, 12, 12, 13, 14, 15}; vector<int> v1(a1, a1+8); cout <<"\nHere are the values in the vector v1:\n"; for (vector<int>::size_type i=0; i<v1.size(); i++) cout <<v1.at(i)<<" "; int a2[] = {11, 12, 12, 13, 13, 16, 17, 18}; vector<int> v2(a2, a2+8); cout <<"\nHere are the values in the vector v2:\n"; for (vector<int>::size_type i=0; i<v2.size(); i++) cout <<v2.at(i)<<" "; int a3[] = {101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115}; vector<int> v3(a3, a3+15); cout <<"\nHere are the values in the vector v3:\n"; for (vector<int>::size_type i=0; i<v3.size(); i++) cout <<v3.at(i)<<" "; cout <<"\nNow we find the values that are in v1 and also in v2, " "and\nwrite them out to v3, starting at the beginning of v3"; vector<int>::iterator p; p = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); cout <<"\nHere are the revised contents of v3:\n"; for (vector<int>::size_type i=0; i<v3.size(); i++) cout <<v3.at(i)<<" "; cout <<"\nThe iterator returned by the algorithm is pointing at the value "<<*p<<"."; return 0; }

Solution

**Output:**Here are the values in the vector v1:

11 12 12 12 12 13 14 15 Here are the values in the vector v2:

11 12 12 13 13 16 17 18 Here are the values in the vector v3:

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 Now we find the values that are in v1 and also in v2, and

write them out to v3, starting at the beginning of v3. Here are the revised contents of v3:

11 12 12 13 105 106 107 108 109 110 111 112 113 114 115 The iterator returned by the algorithm is pointing at the value 105.

References