Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
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;
}
};
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 ///:~
//: C06:Counted.cpp {O}
#include "Counted.h"
int Counted::count = 0;
///:~
The class Counted keeps a static count of the number
of Counted objects that have been created, and notifies you as they are
destroyed. 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 can see here:
//: C06:ForEach.cpp {-mwcc}
// Use of STL for_each() algorithm.
//{L} Counted
#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:
//: C06:Transform.cpp {-mwcc}
// Use of STL transform() algorithm.
//{L} Counted
#include <iostream>
#include <vector>
#include <algorithm>
#include "Counted.h"
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>());
} ///:~
This shows both approaches: using a template function or a
templatized function object. After the call to transform( ), the vector
contains five null 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 do the following:
for_each(a.begin(), a.end(), ptr_fun(operator delete));
This has the same problem as the call to destroy( )
did earlier: operator delete( ) takes a void*, but iterators
aren t pointers. Even if you could make it compile, what you d 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 to 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 into for_each( ). If the function is just a pointer
to a function, the return value is not very useful, but if it is a function
object, 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:
//: C06:Inventory.h
#ifndef INVENTORY_H
#define INVENTORY_H
#include <iostream>
#include <cstdlib>
using std::rand;
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) {
return os << inv.item << ": "
<< "quantity " <<
inv.quantity
<< ", value " << inv.value;
}
};
// A generator:
struct InvenGen {
Inventory operator()() {
static char c = 'a';
int q = rand() % 100;
int v = rand() % 500;
return Inventory(c++, q, v);
}
};
#endif // INVENTORY_H ///:~
Member functions get the item name and get and set quantity
and value. An operator<< prints the Inventory object to an ostream.
A generator creates objects that have sequentially labeled items and random quantities
and values.
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:
//: C06:CalcInventory.cpp
// More use of for_each().
#include <algorithm>
#include <ctime>
#include <vector>
#include "Inventory.h"
#include "PrintSequence.h"
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&
operator<<(ostream& os, const InvAccum&
ia) {
return os << "total quantity: "
<< ia.quantity
<< ", total value: " <<
ia.value;
}
};
int main() {
vector<Inventory> vi;
srand(time(0)); // Randomize
generate_n(back_inserter(vi), 15, InvenGen());
print(vi.begin(), vi.end(), "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 is printed.
You can do most things to the Inventory objects using
for_each( ). For example, for_each( ) can handily
increase all the prices by 10%. 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 needs to have something
to do ). So for_each( ) will not work here, but transform( )
will:
//: C06:TransformNames.cpp
// More use of transform().
#include <algorithm>
#include <cctype>
#include <ctime>
#include <vector>
#include "Inventory.h"
#include "PrintSequence.h"
using namespace std;
struct NewImproved {
Inventory operator()(const Inventory& inv) {
return Inventory(toupper(inv.getItem()),
inv.getQuantity(), inv.getValue());
}
};
int main() {
vector<Inventory> vi;
srand(time(0)); // Randomize
generate_n(back_inserter(vi), 15,
InvenGen());
print(vi.begin(), vi.end(),
"vi");
transform(vi.begin(),vi.end(),vi.begin(),NewImproved());
print(vi.begin(), vi.end(),
"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 any number of special lists need to be generated. 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( ):
//: C06:SpecialList.cpp
// Using the second version of transform().
#include <algorithm>
#include <ctime>
#include <vector>
#include "Inventory.h"
#include "PrintSequence.h"
using namespace std;
struct Discounter {
Inventory operator()(const Inventory& inv,
float discount) {
return Inventory(inv.getItem(), inv.getQuantity(),
int(inv.getValue() * (1 - discount)));
}
};
struct DiscGen {
float operator()() {
float r = float(rand() % 10);
return r / 100.0;
}
};
int main() {
vector<Inventory> vi;
srand(time(0)); // Randomize
generate_n(back_inserter(vi), 15, InvenGen());
print(vi.begin(), vi.end(), "vi");
vector<float> disc;
generate_n(back_inserter(disc), 15, DiscGen());
print(disc.begin(), disc.end(), "Discounts:");
vector<Inventory> discounted;
transform(vi.begin(),vi.end(), disc.begin(),
back_inserter(discounted), Discounter());
print(discounted.begin(),
discounted.end(),"discounted");
} ///:~
Given an Inventory object and a discount percentage,
the Discounter function object produces a new Inventory with the
discounted price. The DiscGen function object just generates random
discount values between 1% and 10% to use for testing. In main( ),
two vectors are created, one for Inventory and one for discounts.
These are passed to transform( ) along with a Discounter
object, and transform( ) fills a new vector<Inventory>
called discounted.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |