Set operations on sorted sequences

Source code

Declaration

template <class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2);

template <class InputIterator1, class InputIterator2, class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2, InputIterator2 last2, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class Compare>
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1,
                         InputIterator2 first2, InputIterator2 last2,
                         OutputIterator result, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class Compare>
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class Compare>
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2,
                              OutputIterator result, Compare comp);

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1,
                                        InputIterator1 last1,
                                        InputIterator2 first2,
                                        InputIterator2 last2,
                                        OutputIterator result);

template <class InputIterator1, class InputIterator2, class OutputIterator,
          class Compare>
OutputIterator set_symmetric_difference(InputIterator1 first1,
                                        InputIterator1 last1,
                                        InputIterator2 first2,
                                        InputIterator2 last2,
                                        OutputIterator result, Compare comp);

Description The function includes returns true (i.e., 1) if the range [ first2, last2) , considered as a multiset, is a subset of the range [ first1, last1) , considered as a multiset.

For the function set_union, if the ranges [ first1, last1) and [ first2, last2) represent sets, each function generates the union of the two sets into the range [ result, l) and returns location l, the past-the-end location of the resulting sequence.

For the function set_intersection, if the ranges [ first1, last1) and [ first2, last2) represent sets, each function generates the intersection of the two sets into the range [ result, l) and returns location l, the past-the-end location of the resulting sequence.

For the function set_difference, if the ranges [ first1, last1) and [ first2, last2) represent sets, each function generates the difference of the two sets into the range [ result, l) and returns location l, the past-the-end location of the resulting sequence.

For the function set_symmetric_difference, if the ranges [ first1, last1) and [ first2, last2) represent sets, each function generates the symmetric difference of the two sets into the range [ result, l) \ and returns location l, the past-the-end location of the resulting sequence.

In the first function of each pair of functions, element comparisons are done using operator<, while in the second they are done using the function object comp .

Type requirements

• InputIterator1 and InputIterator2 must be at least input iterators .
• OutputIterator must be at least an output iterator .
• Compare must be a function object type that provides int operator()(S, S), where S is the dereference type of both InputIterator1 and InputIterator2.

Group Sorting and related operations.

Time complexity Linear.

The number of comparisons performed is one less than twice the size of the range [ first1, last1) plus twice the size of the range [ first2, last2) .

Space complexity Constant.

Mutative? The include functions are not mutative. The remaining set operation functions are mutative.

Details A multiset A is a subset of a multiset B if for each element x of A, the number of occurrences of x in A is less than or equal to the the number of occurrences of x in B.

Here, that a sequence ``represents a set '' means that it is in ascending order  with no duplicate  elements .

The union of sets A and B is a set that contains exactly those elements that are in either A or B.

The intersection of sets A and B is a set that contains exactly those elements that are in both A and B.

The difference of sets A and B is a set that contains exactly those elements that are in A but not in B.

The symmetric difference of sets A and B is a set that contains exactly those elements that are in A but not in B, or vice-versa.

Example Select here to view the source code for the example.

Implementation Select here to view source code (Copyright (C) 1994, Hewlett-Packard Company) for this algorithm.

Implementation notes The includes algorithm is based directly on the definition of the subset relation for multisets.