C++ Primer Plus

              const T& old_value, const T& new_value);

This time the resulting data is copied to a new location, given by result, so the read-only input iterator is sufficient for specifying the range.

Note that replace_copy() has an OutputIterator return type. The convention for copying algorithms is that they return an iterator pointing to the location one past the last value copied.

Another common variation is that some functions have a version that performs an action conditionally, depending on the result of applying a function to a container element. These versions typically append _if to the function name. For example, replace_if() replaces an old value with a new value if applying a function to the old value returns the value true. Here’s the prototype:

template

void replace_if(ForwardIterator first, ForwardIterator last,

              Predicate pred, const T& new_value);

(Recall that a predicate is a unary function that returns a bool value.) There’s also a version called replace_copy_if(). You can probably figure out what it does and what its prototype is like.

As with InputIterator, Predicate is a template parameter name and could just as easily be called T or U. However, the STL chooses to use Predicate to remind the user that the actual argument should be a model of the Predicate concept. Similarly, the STL uses terms such as Generator and BinaryPredicate to identify arguments that should model other function object concepts. Keep in mind that although the documentation can remind you what the iterator or functor requirements are, these names are not something the compiler can check. If you use the wrong sort of iterator, you can expect to see a long list of error messages as the compiler tries to instantiate the template.

The STL and the string Class

The string class, although not part of the STL, is designed with the STL in mind. For example, it has begin(), end(), rbegin(), and rend() members. Thus, it can use the STL interface. Listing 16.17 uses the STL to show all the permutations you can form from the letters in a word. A permutation is a rearrangement of the order of the elements in a container. The next_permutation() algorithm transforms the contents of a range to the next permutation; in the case of a string, the permutations are arranged in ascending alphabetical order. The algorithm returns true if it succeeds and false if the range already is in the final sequence. To get all the permutations of a range, you should start with the elements in the earliest possible order, and the program uses the STL sort() algorithm for that purpose.

Listing 16.17. strgstl.cpp

// strgstl.cpp -- applying the STL to a string

#include

#include

#include

int main()

{

    using namespace std;

    string letters;

    cout << "Enter the letter grouping (quit to quit): ";

    while (cin >> letters && letters != "quit")

    {

        cout << "Permutations of " << letters << endl;

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

        cout << letters << endl;

        while (next_permutation(letters.begin(), letters.end()))

            cout << letters << endl;

        cout << "Enter next sequence (quit to quit): ";

    }

    cout << "Done.\n";

    return 0;

}

Here’s a sample run of the program in Listing 16.17:

Enter the letter grouping (quit to quit): awl

Permutations of awl

alw

awl

law

lwa

wal

wla

Enter next sequence (quit to quit): all

Permutations of all

all

lal

lla

Enter next sequence (quit to quit): quit

Done.

Note that the next_permutation() algorithm automatically provides only unique permutations, which is why the output shows more permutations for the word awl than for the word all, which has duplicate letters.

Functions Versus Container Methods

Sometimes you have a choice between using an STL method and an STL function. Usually, the method is the better choice. First, it should be better optimized for a particular container. Second, being a member function, it can use a template class’s memory management facilities and resize a container when needed.

Suppose, for example, that you have a list of numbers and you want to remove all instances of a certain value, say 4, from the list. If la is a list object, you can use the list remove() method:

la.remove(4);  // remove all 4s from the list

After this method call, all elements with the value 4 are removed from the list, and the list is automatically resized.

There is also an STL algorithm called remove() (see Appendix G). Instead of being invoked by an object, it takes range arguments. So if lb is a list object, a call to the function could look like this:

remove(lb.begin(), lb.end(), 4);