C++ In a Nutshell

Name

set_intersection function template — Computes intersection of sorted ranges

Synopsis

template<typename InIter1, typename InIter2, typename OutIter>
  OutIter set_intersection(InIter1 first1, InIter1 last1, InIter2 first2, 
                           InIter2 last2, OutIter result);
template<typename InIter1, typename InIter2, typename OutIter, typename Compare>
  OutIter set_intersection(InIter1 first1, InIter1 last1, InIter2 first2, 
                           InIter2 last2, OutIter result, Compare comp);

The set_intersection function template copies elements from the sorted range [first1, last1) to the range starting at result. Only those elements that are also present in the sorted range [first2, last2) are copied. An iterator that points to one past the end of the result range is returned.

The result range must not overlap either source range.

The first version compares items using the < operator. The second version uses comp(X, Y) to test whether X < Y.

Figure 13-18 shows an example of intersection using multisets.

Figure 13-18. Intersecting two sets

Technical Notes

Precondition: !(*(i + 1) < *i) for all i in [first1, last1 - 1) and !(*(j + 1) < *j) for all j in [first2, last2 - 1).

Postcondition: !(*(i + 1) < *i) for all i in [result, return - 1).

The set_intersection function template assigns *(result + n++) = *(first1 + m) for all m in [first1, last1), in which *(first1 + m) is in [first2, last2). It returns result + n.

Complexity is linear: ...