On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

### 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;
}
};

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.[97] 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

 Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire