Standard Template Library Programmer's Guide

The two versions of set_intersection differ in how they define whether one element is less than another. The first version compares objects using operator< , and the second compares objects using a function object comp .

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h.

For the first version:

• InputIterator1 is a model of Input Iterator.

• InputIterator2 is a model of Input Iterator.

• OutputIterator is a model of Output Iterator.

• InputIterator1 and InputIterator2 have the same value type.

• InputIterator 's value type is a model of LessThan Comparable.

• The ordering on objects of InputIterator1 's value type is a strict weak ordering , as defined in the LessThan Comparable requirements.

• InputIterator 's value type is convertible to a type in OutputIterator 's set of value types.

For the second version:

• InputIterator1 is a model of Input Iterator.

• InputIterator2 is a model of Input Iterator.

• OutputIterator is a model of Output Iterator.

• StrictWeakOrdering is a model of Strict Weak Ordering.

• InputIterator1 and InputIterator2 have the same value type.

• InputIterator1 's value type is convertible to StrictWeakOrdering 's argument type.

• InputIterator 's value type is convertible to a type in OutputIterator 's set of value types.

For the first version:

• [first1, last1) is a valid range.

• [first2, last2) is a valid range.

• [first1, last1) is ordered in ascending order according to operator< . That is, for every pair of iterators i and j in [first1, last1) such that i precedes j , *j < *i is false .

• [first2, last2) is ordered in ascending order according to 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.

Linear. Zero comparisons if either [first1, last1) or [first2, last2) is empty, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.

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(cout, " "));

cout << endl << "Intersection of A3 and A4: ";

set_intersection(A3, A3 + N3, A4, A4 + N4, ostream_iterator(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

[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.

includes , set_union , set_difference , set_symmetric_difference , sort

Category: algorithms

Component type: function

Set_difference is an overloaded name; there are actually two set_difference functions.

template

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp);

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.