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.