Standard Template Library Programmer's Guide

• [first2, last2) and [result, result + n) do not overlap.

For the second version:

• [first1, last1) is a valid range.

• [first2, last2) is a valid range.

• [first1, last1) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first1, last1) such that i precedes j, comp(*j, *i) is false.

• [first2, last2) is ordered in ascending order according to comp. That is, for every pair of iterators i and j in [first2, last2) such that i precedes j, comp(*j, *i) is false.

• There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + n) is a valid range, where n is the number of elements in the union of the two input ranges.

• [first1, last1) and [result, result + n) do not overlap.

• [first2, last2) and [result, result + n) do not overlap.

Complexity

Linear. Zero comparisons if either [first1, last1) or [first2, last2) is empty, otherwise at most 2 * ((last1 – first1) + (last2 – first2)) – 1 comparisons.

Example

inline bool lt_nocase(char c1, char c2) { return tolower(c1) < tolower(c2); }
int main() {
 int A1[] = {1, 3, 5, 7, 9, 11};
 int A2[] = {1, 1, 2, 3, 5, 8, 13};
 char A3[] = {'a', 'b', 'b', 'B', 'B', 'f', 'g', 'h', 'H'};
 char A4[] = {'A', 'B', 'B', 'C', 'D', 'F', 'F', 'H' };
 const int N1 = sizeof(A1) / sizeof(int);
 const int N2 = sizeof(A2) / sizeof(int);
 const int N3 = sizeof(A3);
 const int N4 = sizeof(A4);
 cout << 'Symmetric difference of A1 and A2: ';
 set_symmetric_difference(A1, A1 + N1, A2, A2 + N2, ostream_iterator<int>(cout, ' '));
 cout << endl << 'Symmetric difference of A3 and A4: ';
 set_symmetric_difference(A3, A3 + N3, A4, A4 + N4, ostream_iterator<char>(cout, ' '), lt_nocase);
 cout << endl;
}

The output is

Symmetric difference of A1 and A2: 1 2 7 8 9 11 13
Symmetric difference of A3 and A4: B B C D F g H

Notes

[1] Even this is not a completely precise description, because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x) but not equal. See the LessThan Comparable requirements for a more complete discussion. The output range consists of those elements from [first1, last1) for which equivalent elements do not exist in [first2, last2), and those elements from [first2, last2) for which equivalent elements do not exist in [first1, last1). Specifically, suppose that the range [first1, last1) contains m elements that are equivalent to each other and the range [first2, last2) contains n elements from that equivalence class (where either m or n may be zero). If m > n then the output range contains the lastm – n of these elements elements from [first1, last1), and if m < n then the output range contains the last n – m of these elements elements from [first2, last2) .

See also

includes, set_union, set_intersection, set_difference, sort

Heap operations

push_heap

Category: algorithms

Component type: function

Prototype

Push_heap is an overloaded name; there are actually two push_heap functions.

template <class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class StrictWeakOrdering>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering comp);

Description

Push_heap adds an element to a heap [1]. It is assumed that [first, last – 1) is already a heap; the element to be added to the heap is *(last – 1) .

The two versions of push_heap differ in how they define whether one element is less than another. The first version compares objects using operator<, and the second compares objects using a function object comp. The postcondition for the first version is that is_heap (first, last) is true, and the postcondition for the second version is that is_heap(first, last, comp) is true.