Node:Set operations on sorted structures, Next:, Previous:Merge, Up:Sorting and related operations

Set operations on sorted structures

This section defines all the basic set operations on sorted structures. They even work with multisets containing multiple copies of equal elements. The semantics of the set operations is generalized to multisets in a standard way by defining union to contain the maximum number of occurrences of every element,intersection to contain the minimum, and so on.

 bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2) Function bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp) Function
 ```template bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp); ``` `includes` returns `true` if every element in the range `[first2, last2)` is contained in the range `[first1, last1)`. It returns `false` otherwise. At most `((last1 - first1) + (last2 - first2)) * 2 - 1` comparisons are performed.

 OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) Function OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) Function
 ```template OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); ``` `set_union` constructs a sorted union of the elements from the two ranges. It returns the end of the constructed range. `set_union` is stable, that is, if an element is present in both ranges, the one from the first range is copied. At most `((last1 - first1) + (last2 - first2)) * 2 - 1` comparisons are performed. The result of `set_union` is undefined if the resulting range overlaps with either of the original ranges.

 OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) Function OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) Function
 ```template OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); ``` `set_intersection` constructs a sorted intersection of the elements from the two ranges. It returns the end of the constructed range. `set_intersection` is guaranteed to be stable, that is, if an element is present in both ranges, the one from the first range is copied. At most `((last1 - first1) + (last2 - first2)) * 2 - 1` comparisons are performed. The result of `set_intersection` is undefined if the resulting range overlaps with either of the original ranges.

 OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) Function OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) Function
 ```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, Compare comp); ``` `set_difference` constructs a sorted difference of the elements from the two ranges. It returns the end of the constructed range. At most `((last1 - first1) + (last2 - first2)) * 2 - 1` comparisons are performed. The result of `set_difference` is undefined if the resulting range overlaps with either of the original ranges.

 OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) Function OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp) Function
 ```template OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); ``` `set_symmetric_difference` constructs a sorted symmetric difference of the elements from the two ranges. It returns the end of the constructed range. At most `((last1 - first1) + (last2 - first2)) * 2 - 1` comparisons are performed. The result of `set_symmetric_difference` is undefined if the resulting range overlaps with either of the original ranges.