Once ranges have been sorted, you can perform mathematical set operations on them.
bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering binary_pred);
Returns true if [first2, last2) is a subset of [first1, last1). Neither range is required to hold only unique elements, but if [first2, last2) holds n elements of a particular value, [first1, last1) must also hold at least n elements if the result is to be true.
OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
Creates the mathematical union of two sorted ranges in the result range, returning the end of the output range. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets, the resulting set will contain the larger number of identical values.
OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
Produces, in result, the intersection of the two input sets, returning the end of the output range—that is, the set of values that appear in both input sets. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets, the resulting set will contain the smaller number of identical values.
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
Produces, in result, the mathematical set difference, returning the end of the output range. All the elements that are in [first1, last1) but not in [first2, last2) are placed in the result set. Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets (n times in set 1 and m times in set 2), the resulting set will contain max(n-m, 0) copies of that value.
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering binary_pred);
Constructs, in result, the set containing:.
1.All the elements in set 1 that are not in set 2
2.All the elements in set 2 that are not in set 1.
Neither input range is required to hold only unique elements, but if a particular value appears multiple times in both input sets (n times in set 1 and m times in set 2), the resulting set will contain abs(n-m) copies of that value, in which abs( ) is the absolute value. The return value is the end of the output range.
Example
It’s easiest to see the set operations demonstrated using simple vectors of characters, so you view the sets more easily. These characters are randomly generated and then sorted, but the duplicates are not removed so you can see what the set operations do when duplicates are involved.
//: C06:SetOperations.cpp
// Set operations on sorted ranges
#include <vector>
#include <algorithm>
#include "PrintSequence.h"
#include "Generators.h"
using namespace std;
int main() {
const int sz = 30;
char v[sz + 1], v2[sz + 1];
CharGen g;
generate(v, v + sz, g);
generate(v2, v2 + sz, g);
sort(v, v + sz);
sort(v2, v2 + sz);
print(v, v + sz, "v", "");
print(v2, v2 + sz, "v2", "");
bool b = includes(v, v + sz, v + sz/2, v + sz);
cout.setf(ios::boolalpha);
cout << "includes: " << b << endl;
char v3[sz*2 + 1], *end;
end = set_union(v, v + sz, v2, v2 + sz, v3);
print(v3, end, "set_union", "");
end = set_intersection(v, v + sz,
v2, v2 + sz, v3);
print(v3, end, "set_intersection", "");
end = set_difference(v, v + sz, v2, v2 + sz, v3);
print(v3, end, "set_difference", "");
end = set_symmetric_difference(v, v + sz,
v2, v2 + sz, v3);
print(v3, end, "set_symmetric_difference","");
} ///:~
After v and v2 are generated, sorted, and printed, the includes( ) algorithm is tested by seeing if the entire range of v contains the last half of v, which of course it does; so the result should always be true. The array v3 holds the output of set_union( ), set_intersection( ), set_difference( ), and set_symmetric_difference( ), and the results of each are displayed so you can ponder them and convince yourself that the algorithms do indeed work as promised.
Heap operations
A heap is an array-like data structure used to implement a "priority queue", which is just a range that is organized in a way that accommodates retrieving elements by priority according to some comparison function. The heap operations in the standard library allow a sequence to be treated as a "heap" data structure, which always efficiently returns the element of highest priority, without fully ordering the entire sequence.
As with the "sort" operations, there are two versions of each function. The first uses the object’s own operator< to perform the comparison; the second uses an additional StrictWeakOrdering object’s operator( )(a, b) to compare two objects for a < b.
void make_heap(RandomAccessIterator first, RandomAccessIterator last); void make_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
Turns an arbitrary range into a heap.
void push_heap(RandomAccessIterator first, RandomAccessIterator last); void push_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);
Adds the element *(last-1) to the heap determined by the range [first, last-1). In other words, it places the last element in its proper location in the heap.