Next : , Previous : Merge, Top : Table of  Contents

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