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.)
The first form of transform( ) simply calls f(*first), where first ranges through the input sequence. Similarly, the second form calls f(*first1, *first2). (Note that the length of the second input range is determined by the length of the first.) The return value in both cases is the past-the-end iterator for the resulting output range.
Examples
Since much of what you do with objects in a container is to apply an operation to all those objects, these are fairly important algorithms and merit several illustrations.
First, consider for_each( ). This sweeps through the range, pulling out each element and passing it as an argument as it calls whatever function object it’s been given. Thus, for_each( ) performs operations that you might normally write out by hand. If you look in your compiler’s header file at the template defining for_each( ), you’ll see something like this:.
template <class InputIterator, class Function>
Function for_each(InputIterator first,
InputIterator last,
Function f) {
while (first != last) f(*first++);
return f;
}
The following example shows several ways this template can be expanded. First, we need a class that keeps track of its objects so we can know that it’s being properly destroyed:.
//: C06:Counted.h
// An object that keeps track of itself
#ifndef COUNTED_H
#define COUNTED_H
#include <vector>
#include <iostream>
class Counted {
static int count;
char* ident;
public:
Counted(char* id) : ident(id) { count++; }
~Counted() {
std::cout << ident << " count = "
<< --count << std::endl;
}
};
int Counted::count = 0;
class CountedVector :
public std::vector<Counted*> {
public:
CountedVector(char* id) {
for(int i = 0; i < 5; i++)
push_back(new Counted(id));
}
};
#endif // COUNTED_H ///:~
The class Counted keeps a static count of how many Counted objects have been created and tells you as they are destroyed.[89] In addition, each Counted keeps a char* identifier to make tracking the output easier.
The CountedVector is derived from vector<Counted*>, and in the constructor it creates some Counted objects, handing each one your desired char*. The CountedVector makes testing quite simple, as you’ll see.
//: C06:ForEach.cpp
// Use of STL for_each() algorithm
#include <algorithm>
#include <iostream>
#include "Counted.h"
using namespace std;
// Function object:
template<class T>
class DeleteT {
public:
void operator()(T* x) { delete x; }
};
// Template function:
template <class T>
void wipe(T* x) { delete x; }
int main() {
CountedVector B("two");
for_each(B.begin(),B.end(),DeleteT<Counted>());
CountedVector C("three");
for_each(C.begin(), C.end(), wipe<Counted>);
} ///:~
Since this is obviously something you might want to do a lot, why not create an algorithm to delete all the pointers in a container? You could use transform( ). The value of transform( ) over for_each( ) is that transform( ) assigns the result of calling the function object into a resulting range, which can actually be the input range. That case means a literal transformation for the input range, since each element would be a modification of its previous value. In this example, this approach would be especially useful since it’s more appropriate to assign to each pointer the safe value of zero after calling delete for that pointer. Transform( ) can easily do this:.