C++ Primer Plus

4       Warriors of Wonk

8       Quantum Manners

More Things to Do to Vectors

There are many things programmers commonly do with arrays, such as search them, sort them, randomize the order, and so on. Does the vector template class have methods for these common operations? No! The STL takes a broader view, defining nonmember functions for these operations. Thus, instead of defining a separate find() member function for each container class, it defines a single find() nonmember function that can be used for all container classes. This design philosophy saves a lot of duplicate work. For example, suppose you had 8 container classes and 10 operations to support. If each class had its own member function, you’d need 8×10, or 80, separate member function definitions. But with the STL approach, you’d need just 10 separate nonmember function definitions. And if you defined a new container class, provided that you followed the proper guidelines, it too could use the existing 10 nonmember functions to find, sort, and so on.

On the other hand, the STL sometimes defines a member function even if it also defines a nonmember function for the same task. The reason is that for some actions, there is a class-specific algorithm that is more efficient than the more general algorithm. Therefore, the vector swap() will be more efficient than the nonmember swap(). On the other hand, the nonmember version will allow you swap contents between two different kinds of containers.

Let’s examine three representative STL functions: for_each(), random_shuffle(), and sort(). The for_each() function can be used with any container class. It takes three arguments. The first two are iterators that define a range in the container, and the last is a pointer to a function. (More generally, the last argument is a function object; you’ll learn about function objects shortly.) The for_each() function then applies the pointed-to function to each container element in the range. The pointed-to function must not alter the value of the container elements. You can use the for_each() function instead of a for loop. For example, you can replace the code

vector::iterator pr;

for (pr = books.begin(); pr != books.end(); pr++)

    ShowReview(*pr);

with the following:

for_each(books.begin(), books.end(), ShowReview);

This enables you to avoid dirtying your hands (and code) with explicit use of iterator variables.

The random_shuffle() function takes two iterators that specify a range and rearranges the elements in that range in random order. For example, the following statement randomly rearranges the order of all the elements in the books vector:

random_shuffle(books.begin(), books.end());

Unlike for_each, which works with any container class, this function requires that the container class allow random access, which the vector class does.

The sort() function, too, requires that the container support random access. It comes in two versions. The first version takes two iterators that define a range, and it sorts that range by using the < operator defined for the type element stored in the container. For example, the following sorts the contents of coolstuff in ascending order, using the built-in < operator to compare values:

vector coolstuff;

...

sort(coolstuff.begin(), coolstuff.end());

If the container elements are user-defined objects, then there has to be an operator<() function defined that works with that type of object in order to use sort(). For example, you could sort a vector containing Review objects if you provided either a Review member function or a nonmember function for operator<(). Because Review is a structure, its members are public, and a nonmember function like this would serve:

bool operator<(const Review & r1, const Review & r2)

{

    if (r1.title < r2.title)

        return true;

    else if (r1.title == r2.title && r1.rating < r2.rating)

        return true;

    else

        return false;

}

With a function like this in place, you could then sort a vector of Review objects (such as books):

sort(books.begin(), books.end());

This version of the operator<() function sorts in lexicographic order of the title members. If two objects have the same title members, they are then sorted in ratings order. But suppose you want to sort in decreasing order or in order of ratings instead of titles. In such a case, you can use the second form of sort(). It takes three arguments. The first two, again, are iterators that indicate the range. The final argument is a pointer to a function (more generally, a function object) to be used instead of operator<() for making the comparison. The return value should be convertible to bool, with false meaning the two arguments are in the wrong order. Here’s an example of such a function:

bool WorseThan(const Review & r1, const Review & r2)

{

    if (r1.rating < r2.rating)

        return true;

    else

        return false;

}