operator<. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, *j < *i is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
For the second version:
• [first1, last1) is a valid range.
• [first2, last2) is a valid range.
• [first1, last1) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.
• [first2, last2) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.
• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.
• [first1, last1) and [result, result + n) do not overlap.
• [first2, last2) and [result, result + n) do not overlap.
Complexity Linear. Zero comparisons if either [first1, last1) or [first2, last2) is empty, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.
Example inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
int A1[] = {1, 3, 5, 7, 9, 11};
int A2[] = {1, 1, 2, 3, 5, 8, 13};
char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'h', 'H'};
char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
const int N1 = sizeof(A1) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
const int N3 = sizeof(A3);
const int N4 = sizeof(A4);
cout << 'Intersection of A1 and A2: ';
set_intersection(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, ' '));
cout << endl << 'Intersection of A3 and A4: ';
set_intersection(A3, A3 + N3, A4, A4 + N4, ostream_iterator<char>(cout, ' '), lt_nocase);
cout << endl;
}
The output is
Intersection of A1 and A2: 1 3 5
Intersection of A3 and A4: a b b f h
Notes [1] Even this is not a completely precise description, because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x ) but not equal. See the LessThan Comparable requirements for a fuller discussion. The output range consists of those elements from [first1, last1) for which equivalent elements exist in [first2, last2). Specifically, if the range [first1, last1) contains n elements that are equivalent to each other and the range [first1, last1) contains m elements from that equivalence class (where either m or n may be zero), then the output range contains the first min(m, n) of these elements from [first1, last1). Note that this precision is only important if elements can be equivalent but not equal. If you're using a total ordering (if you're using strcmp, for example, or if you're using ordinary arithmetic comparison on integers), then you can ignore this technical distinction: for a total ordering, equality and equivalence are the same.
See also includes, set_union, set_difference, set_symmetric_difference, sort
Category: algorithms
Component type: function
Prototype Set_difference is an overloaded name; there are actually two set_difference functions.
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
template <class InputIterator1, class InputIterator2, class OutputIterator, class StrictWeakOrdering>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);
Description Set_difference constructs a sorted range that is the set difference of the sorted ranges [first1, last1) and [first2, last2). The return value is the end of the output range.
In the simplest case, set_difference performs the 'difference' operation from set theory: the output range contains a copy of every element that is contained in [first1, last1) and not contained in [first2, last2). The general case is more complicated,
