} ///:~

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 vectors v3, v4, v5 and v6 are created to hold 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

The heap operations in the STL are primarily concerned with the creation of the STL priority_queue, which provides efficient access to the “largest” element, whatever “largest” happens to mean for your program. These were discussed in some detail in the previous chapter, and you can find an example there.

As with the “sort” operations, there are two versions of each function, the first that uses the object’s own operator< to perform the comparison, the second that 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. A heap is just a range that is organized in a particular way.

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). Yes, it seems like an odd way to do things but remember that the priority_queue container presents the nice interface to a heap, as shown in the previous chapter.

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 nextlargest 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);

Chapter 15: Multiple Inheritance

322