Mastering STL Algorithms and Function Objects

MinAndMax func;
func = for_each(myVector.begin(),	myVector.end(), func);
cout << “The max is “ << func.max	<< endl;
cout << “The min is “ << func.min	<< endl;
return (0);

}

You might be tempted to ignore the return value of for_each(), yet still try to read information from func after the call. However, that doesn’t work because func is not necessarily passed-by-reference into for_each(). You must capture the return value in order to ensure correct behavior.

A final point about for_each() is that your callback is allowed to take its argument by reference and modify it. That has the effect of changing values in the actual iterator range. The voter registration example later in this chapter shows a use of this capability.

Modifying Algorithms

The STL provides a variety of modifying algorithms that perform tasks such as copying elements from one range to another, removing elements, or reversing the order of elements in a range.

The modifying algorithms all have the concept of source and destination ranges. The elements are read from the source range and added to or modified in the destination range. The source and destination ranges can often be the same, in which case the algorithm is said to operate in place.

Ranges from maps and multimaps cannot be used as destinations of modifying algorithms. These algorithms overwrite entire elements, which in a map consist of key/value pairs. However, maps and multimaps mark the key const, so it cannot be assigned to. Similarly, many implementations of set and multiset provide only const iteration over the elements, so you cannot generally use ranges from these containers as destinations of modifying algorithms either. Your alternative is to use an insert iterator, described in Chapter 23.

Transform

The transform() algorithm is similar to for_each(), in that it applies a callback to each element in a range. The difference is that transform() expects the callback to generate a new element for each call, which it stores in the destination range specified. The source and destination ranges can be the same if you want transform to replace each element in a range with the result from the call to the callback. For example, you could add 100 to each element in a vector like this:

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

639

Chapter 22

//The populateContainer() function is identical to the one shown above for

//comparison alglorithms, so is omitted here.

void print(int elem)

{

cout << elem << “ “;

}

int main(int argc, char** argv)

{

vector<int> myVector;

populateContainer(myVector);

cout << “The vector contents are:\n”; for_each(myVector.begin(), myVector.end(), &print); cout << endl;

transform(myVector.begin(), myVector.end(), myVector.begin(), bind2nd(plus<int>(), 100));

cout << “The vector contents are:\n”; for_each(myVector.begin(), myVector.end(), &print); cout << endl;

return (0);

}

Another form of transform() calls a binary function on pairs of elements in the range. See the Standrad Library Reference resource on the Web site. Interestingly, by writing the right functors for transform(), you could use it to achieve the functionality of many of the other modifying algorithms, such as copy() and replace(). However, it is usually more convenient to use the simpler algorithms when possible.

transform() and the other modifying algorithms often return an iterator referring to the past-the-end value of the destination range. The examples in this book usually ignore that return value. Consult the Standard Library Reference resource on the Web site for the specifics.

Copy

The copy() algorithm allows you to copy elements from one range to another. The source and destination ranges must be different, but they can overlap. Note that copy() doesn’t insert elements into the destination range. It just overwrites whatever elements were there already. Thus, you can’t use copy() directly to insert elements into a container, only to overwrite elements that were previously in a container.

Chapter 23 describes how to use iterator adapters to insert elements into a container or stream with copy().

Here is a simple example of copy() that exploits the resize() method on vectors to ensure that there is enough space in the destination container:

640

Mastering STL Algorithms and Function Objects

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

//The populateContainer() and print() functions are identical to those

//in the previous example, so are omitted here.

int main(int argc, char** argv)

{

vector<int> vectOne, vectTwo;

populateContainer(vectOne);

vectTwo.resize(vectOne.size());

copy(vectOne.begin(), vectOne.end(), vectTwo.begin()); for_each(vectTwo.begin(), vectTwo.end(), &print);

return (0);

}

Replace

The replace() and replace_if() algorithms replace elements in a range matching a value or predicate, respectively, with a new value. For example, you could force all elements in an integer range to be between 0 and 100 by replacing all values less than 0 with 0 and replacing all values greater than 100 with 100:

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

//The populateContainer() and print() functions are identical to those

//in the previous example, so are omitted here.

int main(int argc, char** argv)

{

vector<int> myVector; populateContainer(myVector);

replace_if(myVector.begin(), myVector.end(), bind2nd(less<int>(), 0), 0); replace_if(myVector.begin(), myVector.end(), bind2nd(greater<int>(), 100),

100);

for_each(myVector.begin(), myVector.end(), &print); cout << endl;

return (0);

}

There are also variants of replace() called replace_copy() and replace_copy_if() that copy the results to a different destination range.

641

Chapter 22

Remove

The remove() and remove_if() algorithms remove certain elements from a range. The elements to remove can be specified by either a specific value or with a predicate. It is important to remember that these elements are not removed from the underlying container, because the algorithms have access only to the iterator abstraction, not to the container. Instead, the removed elements are copied to the end of the range, and the new end of the (shorter) range is returned. If you want to actually erase the removed elements from the container, you must use the remove() algorithm, then call erase() on the container. Here is an example of a function that removes empty strings from a vector of strings. It is similar to the function findEmptyString() shown earlier in the chapter.

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

void removeEmptyStrings(vector<string>& strings)

{

vector<string>::iterator it = remove_if(strings.begin(), strings.end(), mem_fun_ref(&string::empty));

// Erase the removed elements. strings.erase(it, strings.end());

}

void printString(const string& str)

{

cout << str << “ “;

}

int main(int argc, char** argv)

{

vector<string> myVector; myVector.push_back(“”); myVector.push_back(“stringone”); myVector.push_back(“”); myVector.push_back(“stringtwo”); myVector.push_back(“stringthree”); myVector.push_back(“stringfour”);

removeEmptyStrings(myVector);

cout << “Size is “ << myVector.size() << endl; for_each(myVector.begin(), myVector.end(), &printString); cout << endl;

return (0);

}

The remove_copy() and remove_copy_if() variations of remove() do not change the source range. Instead they copy all unremoved elements to a different destination range. They are similar to copy(), in that the destination range must already be large enough to hold the new elements.

642