This could be thought of as the complement of make_heap( ), since 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 (but returns the function object that has been applied to each element), while 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 then 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 you should use an inserter to force insertions instead of assignments).

The first form of transform( ) simply calls f( ) and passes it each object from the input range as an argument. The second form passes an object from the first input range and one from the second input range as the two arguments to the binary function f (note 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 of those objects, these are fairly important algorithms and merit several illustrations.

Chapter 15: Multiple Inheritance

323

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. In Stlshape.cpp, for example:

for(Iter j = shapes.begin(); j != shapes.end(); j++)

delete *j;

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;

}

Function f looks at first like it must be a pointer to a function which takes, as an argument, an object of whatever InputIterator selects. However, the above template actually only says that you must be able to call f using parentheses and an argument. This is true for a function pointer, but it’s also true for a function object – any class that defines the appropriate operator( ). The following example shows several different 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:

//: C05: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;

}

};

Chapter 15: Multiple Inheritance

324

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. In addition, each Counted keeps a char* identifier to make tracking the output easier.

The CountedVector is inherited 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.

//: C05:ForEach.cpp

//Use of STL for_each() algorithm #include "Counted.h"

#include <iostream> #include <vector> #include <algorithm> using namespace std;

//Simple function:

void destroy(Counted* fp) { delete fp; }

//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 A("one");

for_each(A.begin(), A.end(), destroy);

Chapter 15: Multiple Inheritance

325

CountedVector B("two"); for_each(B.begin(),B.end(),DeleteT<Counted>()); CountedVector C("three");

for_each(C.begin(), C.end(), wipe<Counted>); } ///:~

In main( ), the first approach is the simple pointer-to-function, which works but has the drawback that you must write a new Destroy function for each different type. The obvious solution is to make a template, which is shown in the second approach with a templatized function object. On the other hand, approach three also makes sense: template functions work as well.

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? This was accomplished with the purge( ) template created in the previous chapter. However, that used explicitly-written code; here, we 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 the above example this would be especially useful since it’s more appropriate to assign each pointer to the safe value of zero after calling delete for that pointer. Transform( ) can easily do this:

//: C05:Transform.cpp

// Use of STL transform() algorithm #include "Counted.h"

#include <iostream> #include <vector> #include <algorithm> using namespace std;

template<class T>

T* deleteP(T* x) { delete x; return 0; }

template<class T> struct Deleter {

T* operator()(T* x) { delete x; return 0; }

};

int main() {

CountedVector cv("one"); transform(cv.begin(), cv.end(), cv.begin(),

deleteP<Counted>); CountedVector cv2("two");

transform(cv2.begin(), cv2.end(), cv2.begin(), Deleter<Counted>());

} ///:~

Chapter 15: Multiple Inheritance

326

This shows both approaches: using a template function or a templatized function object. After the call to transform( ), the vector contains zero pointers, which is safer since any duplicate deletes will have no effect.

One thing you cannot do is delete every pointer in a collection without wrapping the call to delete inside a function or an object. That is, you don’t want to say something like this:

for_each(a.begin(), a.end(), ptr_fun(operator delete));

You can say it, but what you’ll get is a sequence of calls to the function that releases the storage. You will not get the effect of calling delete for each pointer in a, however; the destructor will not be called. This is typically not what you want, so you will need wrap your calls to delete.

In the previous example of for_each( ), the return value of the algorithm was ignored. This return value is the function that is passed in to for_each( ). If the function is just a pointer to a function, then the return value is not very useful, but if it is a function object, then that function object may have internal member data that it uses to accumulate information about all the objects that it sees during for_each( ).

For example, consider a simple model of inventory. Each Inventory object has the type of product it represents (here, single characters will be used for product names), the quantity of that product and the price of each item:

//: C05:Inventory.h #ifndef INVENTORY_H #define INVENTORY_H #include <iostream> #include <cstdlib> #include <ctime>

class Inventory { char item;

int quantity; int value;

public:

Inventory(char it, int quant, int val)

:item(it), quantity(quant), value(val) {}

//Synthesized operator= & copy-constructor OK char getItem() const { return item; }

int getQuantity() const { return quantity; } void setQuantity(int q) { quantity = q; } int getValue() const { return value; }

void setValue(int val) { value = val; } friend std::ostream& operator<<(

std::ostream& os, const Inventory& inv) {

Chapter 15: Multiple Inheritance

327

return os << inv.item << ": "

<<"quantity " << inv.quantity

<<", value " << inv.value;

}

};

// A generator: struct InvenGen {

InvenGen() { std::srand(std::time(0)); } Inventory operator()() {

static char c = 'a';

int q = std::rand() % 100; int v = std::rand() % 500; return Inventory(c++, q, v);

}

};

#endif // INVENTORY_H ///:~

There are member functions to get the item name, and to get and set quantity and value. An operator<< prints the Inventory object to an ostream. There’s also a generator that creates objects that have sequentially-labeled items and random quantities and values. Note the use of the return value optimization in operator( ).

To find out the total number of items and total value, you can create a function object to use with for_each( ) that has data members to hold the totals:

//: C05:CalcInventory.cpp

//More use of for_each() #include "Inventory.h" #include "PrintSequence.h" #include <vector>

#include <algorithm> using namespace std;

//To calculate inventory totals: class InvAccum {

int quantity; int value;

public:

InvAccum() : quantity(0), value(0) {} void operator()(const Inventory& inv) {

quantity += inv.getQuantity();

value += inv.getQuantity() * inv.getValue();

}

friend ostream&

Chapter 15: Multiple Inheritance

328

operator<<(ostream& os, const InvAccum& ia) { return os << "total quantity: "

<<ia.quantity

<<", total value: " << ia.value;

}

};

int main() { vector<Inventory> vi;

generate_n(back_inserter(vi), 15, InvenGen()); print(vi, "vi");

InvAccum ia = for_each(vi.begin(),vi.end(), InvAccum());

cout << ia << endl; } ///:~

InvAccum’s operator( ) takes a single argument, as required by for_each( ). As for_each( ) moves through its range, it takes each object in that range and passes it to InvAccum::operator( ), which performs calculations and saves the result. At the end of this process, for_each( ) returns the InvAccum object which you can then examine; in this case it is simply printed.

You can do most things to the Inventory objects using for_each( ). For example, if you wanted to increase all the prices by 10%, for_each( ) could do this handily. But you’ll notice that the Inventory objects have no way to change the item value. The programmers who designed Inventory thought this was a good idea, after all, why would you want to change the name of an item? But marketing has decided that they want a “new, improved” look by changing all the item names to uppercase; they’ve done studies and determined that the new names will boost sales (well, marketing has to have something to do …). So for_each( ) will not work here, but transform( ) will:

//: C05:TransformNames.cpp // More use of transform() #include "Inventory.h"

#include "PrintSequence.h" #include <vector>

#include <algorithm> #include <cctype> using namespace std;

struct NewImproved {

Inventory operator()(const Inventory& inv) { return Inventory(toupper(inv.getItem()), inv.getQuantity(), inv.getValue());

}

Chapter 15: Multiple Inheritance

329

};

int main() { vector<Inventory> vi;

generate_n(back_inserter(vi), 15, InvenGen()); print(vi, "vi");

transform(vi.begin(), vi.end(), vi.begin(), NewImproved());

print(vi, "vi"); } ///:~

Notice that the resulting range is the same as the input range, that is, the transformation is performed in-place.

Now suppose that the sales department needs to generate special price lists with different discounts for each item. The original list must stay the same, and there need to be any number of generated special lists. Sales will give you a separate list of discounts for each new list. To solve this problem we can use the second version of transform( ):

//: C05:SpecialList.cpp

// Using the second version of transform() #include "Inventory.h"

#include "PrintSequence.h" #include <vector>

#include <algorithm> #include <cstdlib> #include <ctime> using namespace std;

struct Discounter {

Inventory operator()(const Inventory& inv, float discount) {

return Inventory(inv.getItem(), inv.getQuantity(),

inv.getValue() * (1 - discount));

}

};

struct DiscGen {

DiscGen() { srand(time(0)); } float operator()() {

float r = float(rand() % 10); return r / 100.0;

}

};

Chapter 15: Multiple Inheritance

330