Thinking In C++. Volume 2: Practical Programming

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.

void pop_heap(RandomAccessIterator first, RandomAccessIterator last); void pop_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);

Places the largest element (which is actually in *first, before the operation, because of the way heaps are defined) into the position *(last-1) and reorganizes the remaining range so that it’s still in heap order. If you simply grabbed *first, the next element would not be the next-largest element; so you must use pop_heap( ) if you want to maintain the heap in its proper priority-queue order.

void sort_heap(RandomAccessIterator first, RandomAccessIterator last); void sort_heap(RandomAccessIterator first, RandomAccessIterator last, StrictWeakOrdering binary_pred);

This could be thought of as the complement of make_heap( ). It takes a range that is in heap order and turns it into ordinary sorted order, so it is no longer a heap. That means that if you call sort_heap( ), you can no longer use push_heap( ) or pop_heap( ) on that range. (Rather, you can use those functions, but they won’t do anything sensible.) This is not a stable sort.

Applying an operation to each element in a range

These algorithms move through the entire range and perform an operation on each element. They differ in what they do with the results of that operation: for_each( ) discards the return value of the operation, and transform( ) places the results of each operation into a destination sequence (which can be the original sequence).

UnaryFunction for_each(InputIterator first, InputIterator last, UnaryFunction f);^.

Applies the function object f to each element in [first, last), discarding the return value from each individual application of f. If f is just a function pointer, you are typically not interested in the return value; but if f is an object that maintains some internal state, it can capture the combined return value of being applied to the range. The final return value of for_each( ) is f.

OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryFunction f); OutputIterator transform(InputIterator1 first, InputIterator1 last, InputIterator2 first2, OutputIterator result, BinaryFunction f);

Like for_each( ), transform( ) applies a function object f to each element in the range [first, last). However, instead of discarding the result of each function call, transform( ) copies the result (using operator=) into *result, incrementing result after each copy. (The sequence pointed to by result must have enough storage; otherwise, use an inserter to force insertions instead of assignments.)